Warum ist diese Implementierung eine schlechte Instanz der faltbaren Typklasse?

Question

Ich arbeite mich durch das wundervolle Haskell-Buch . Am Ende des Kapitels Traversable (21) muss ich eine Instanz für den folgenden Baum schreiben:

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

Hier ist ein Link zum vollständigen Code meiner Lösung. In den Übungen wird empfohlen, sowohl foldMapund als auch zu implementieren foldr. So habe ich implementiert foldr(ohne viel über die Aufrufreihenfolge nachzudenken):

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

Ich habe dann foldMapwie folgt implementiert :

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

Wenn ich den Teststapel von QuickCheck ausführe, foldabletreten einige Fehler auf. Wenn Sie meine foldrImplementierung wie folgt ändern, bestehen alle Tests:

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

Ich habe versucht, den fehlgeschlagenen Testfall selbst auszuführen, konnte den Fehler jedoch nicht wiederherstellen:

*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}

Ich vermute, dass ich etwas über die von foldQuickCheck verwendete Funktion nicht herausfinden kann .

Fragen:

1. Warum treten Fehler auf?
2. Gibt es eine Möglichkeit, die im Test verwendete Funktion von QuickCheck zu erhalten?

Answer 1

foldrkann foldMap durch Verwendung des EndoMonoids erhalten werden , wobei die a -> b -> bFunktion aWerte in b -> bFunktionen umwandelt, die (monoidal) zusammengesetzt werden können. Das ist so, wenn Sie 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

... das entsprechende foldrmuss sein:

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 (.)

Wenn wir das ein wenig aufräumen ...

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)

... wir bekommen die korrekte Definition von foldrwie in Ihrer Frage geschrieben. Da der Unterschied zwischen den Implementierungen mit der Reihenfolge der Zusammensetzung zusammenhängt, führt das Ausprobieren eines nicht kommutativen Monoids leicht zu einem Fehlschlag, wie Sie herausgefunden haben .

Bei der QuickCheck-Unterfrage verzichte ich auf die Antwort von DDub. .

Answer 2

Wie Sie bereits festgestellt haben, liegt der Grund für Fehler darin, dass die beiden Implementierungen unterscheidbar sind, was Sie mithilfe eines nicht kommutativen Monoids beobachten können.

---

Es ist nicht so einfach, die von Quickcheck verwendete Funktion zu erhalten. Weitere Informationen finden Sie beispielsweise in dieser Frage / Antwort zu ShowFunktionen, die durch Quickcheck generiert wurden.

Die Möglichkeit, ShowFunktionen aus QuickCheck herauszuholen, besteht darin, die Funktion in den FunTyp einzuschließen . Der Code, den Sie aufrufen ( hier zu finden ), verwendet jedoch nur Funktionen direkt, sodass sie niemals angezeigt werden können. Eine Möglichkeit, die Sie versuchen können, besteht darin, eine eigene Version der foldableFunktion zu erstellen, in der Sie den Typ Fun a banstelle a -> bund applyFunnach Bedarf verwenden, um die Funktionen anzuwenden.

Answer 3

Ich habe gerade festgestellt, dass ich ein kommutatives Monoid verwendet habe ... Ich konnte den Fehler mit einem nicht kommutativen Monoid nachbilden:

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

Dies ist wahrscheinlich ein einfacher Fall. Ich würde mir vorstellen, dass dies im Produktionscode mit realen Datentypen viel komplizierter sein könnte.