Dlaczego ta implementacja jest złym wystąpieniem składanej typeklasy?

Question

Pracuję nad wspaniałą książką Haskella . Pod koniec rozdziału Traversable (21) muszę napisać instancję dla następującego drzewa:

data Tree a =
    Empty
  | Leaf a
  | Node (Tree a) a (Tree a)

Oto link do pełnego kodu mojego rozwiązania. Ćwiczenia zalecają próbę wdrożenia obu foldMapi foldr. Oto jak zaimplementowałem foldr(bez poświęcania wiele uwagi kolejności wywołań):

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  f x $ foldr f (foldr f z left) right

Następnie wdrożyłem foldMapw następujący sposób:

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

Kiedy uruchamiam foldablepartię testową QuickCheck, pojawiają się błędy. Zmiana mojej foldrimplementacji na następującą sprawia, że ​​wszystkie testy przechodzą:

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left

Próbowałem samodzielnie uruchomić przypadek testowy, który kończy się niepowodzeniem, ale nie mogłem odtworzyć błędu:

*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}

Podejrzewam, że jest coś, czego nie wiem o foldfunkcji ing, której używa QuickCheck.

Pytania:

1. Dlaczego występują awarie?
2. Czy istnieje sposób na uzyskanie funkcji używanej w teście przez QuickCheck?

Answer 1

foldrmożna uzyskać foldMap za pomocą Endomonoidu , przy czym a -> b -> bfunkcja zamienia awartości w b -> bfunkcje, które można (monoidalnie) składać. W związku z tym, jeśli jesteś foldMap...

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

... odpowiedni foldrmusi być:

foldr f z Empty = id z  -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) = 
  ((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z  -- (<>) amounts to (.)

Jeśli trochę to uporządkujemy ...

foldr f z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left)

... otrzymujemy poprawną definicję, foldrjak napisano w Twoim pytaniu. Ponieważ różnica między implementacjami ma związek z kolejnością kompozycji, wypróbowanie nieprzemiennego monoidu łatwo prowadzi do przypadku niepowodzenia, jak się przekonałeś .

W pytaniu podrzędnym QuickCheck odkładam odpowiedź DDub. .

Answer 2

Jak już wywnioskowałeś, przyczyną niepowodzeń jest to, że te dwie implementacje są rozróżnialne, co można zaobserwować, używając nieprzemiennego monoidu.

---

Uzyskanie funkcji używanej przez quickcheck nie jest takie proste. Zobacz na przykład to pytanie / odpowiedź na temat Showfunkcji generowanych przez quickcheck, aby uzyskać trochę więcej informacji.

Sposób, aby uzyskać Showfunkcje zdolnych z QuickCheck jest zawinąć funkcję w tym Funrodzaju . To powiedziawszy, kod, który wywołujesz ( znaleziony tutaj ) po prostu używa funkcji bezpośrednio, więc nigdy nie można ich wyświetlić. Jedną z opcji, którą możesz wypróbować, jest utworzenie własnej wersji foldablefunkcji, w której użyjesz typu Fun a bzamiast a -> bi applyFunjeśli to konieczne, aby zastosować funkcje.

Answer 3

Właśnie zdałem sobie sprawę, że użyłem przemiennego Monoida ... Byłem w stanie odtworzyć awarię za pomocą nieprzemiennego Monoida:

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

To prawdopodobnie prosty przypadek. Wyobrażam sobie, że w kodzie produkcyjnym z rzeczywistymi typami danych może to być znacznie bardziej skomplikowane.