Pourquoi cette implémentation est-elle une mauvaise instance de la classe de types pliable?
Je travaille sur le merveilleux livre Haskell . À la fin du chapitre Traversable (21), je dois écrire une instance pour l'arbre suivant:
data Tree a =
Empty
| Leaf a
| Node (Tree a) a (Tree a)
Voici un lien vers le code complet de ma solution. Les exercices recommandent d'essayer de mettre en œuvre à la fois foldMap
et foldr
. Voici comment j'ai implémenté foldr
(sans trop réfléchir à l'ordre d'invocation):
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
J'ai ensuite implémenté foldMap
comme suit:
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
Lorsque j'exécute le foldable
lot de tests de QuickCheck , j'obtiens des échecs. Changer mon foldr
implémentation pour que tous les tests passent:
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
J'ai essayé d'exécuter le cas de test échoué par moi-même, mais je n'ai pas pu recréer l'échec:
*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}
Je soupçonne qu'il y a quelque chose que je ne comprends pas à propos de la fold
fonction ing utilisée par QuickCheck.
Des questions:
- Pourquoi des échecs se produisent-ils?
- Existe-t-il un moyen d'obtenir la fonction utilisée dans le test par QuickCheck?
Réponses
foldr
peut être obtenu à partir foldMap
de l'utilisation du Endomonoïde , la a -> b -> b
fonction transformant les a
valeurs en b -> b
fonctions pouvant être composées (de manière monoïdale). Cela étant, si vous foldMap
êtes ...
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
... le correspondant foldr
doit être:
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 (.)
Si on range ça un peu ...
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)
... nous obtenons la définition correcte de foldr
tel qu'écrit dans votre question. Comme la différence entre les implémentations a à voir avec l'ordre de composition, essayer un monoïde non commutatif conduit facilement à un cas d'échec, comme vous l'avez découvert .
Sur la sous-question QuickCheck, je m'en remets à la réponse de DDub. .
Comme vous l'avez déjà déduit, la raison pour laquelle vous obtenez des échecs est que les deux implémentations sont distinguables, ce que vous pouvez observer en utilisant un monoïde non commutatif.
Obtenir la fonction utilisée par quickcheck n'est pas si simple. Voir, par exemple, cette question / réponse sur Show
les fonctions ing générées par quickcheck pour un peu plus d'informations.
La façon d'obtenir des Show
fonctions capables de QuickCheck est d'encapsuler la fonction dans le Funtype . Cela dit, le code que vous appelez ( trouvé ici ) utilise simplement des fonctions directement, donc elles ne peuvent jamais être affichées. Une option que vous pouvez essayer est de créer votre propre version de la foldable
fonction dans laquelle vous utilisez le type Fun a b
à la place a -> b
et applyFun
si nécessaire pour appliquer les fonctions.
Je viens de réaliser que j'ai utilisé un Monoïde commutatif ... J'ai pu recréer l'échec en utilisant un Monoïde non commutatif:
> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}
C'est probablement un cas simple. J'imagine que dans le code de production avec des types de données réels, cela pourrait être beaucoup plus compliqué.