Pourquoi cette implémentation est-elle une mauvaise instance de la classe de types pliable?

Jan 02 2021

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 foldMapet 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é foldMapcomme 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 foldablelot de tests de QuickCheck , j'obtiens des échecs. Changer mon foldrimplé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 foldfonction ing utilisée par QuickCheck.

Des questions:

  1. Pourquoi des échecs se produisent-ils?
  2. Existe-t-il un moyen d'obtenir la fonction utilisée dans le test par QuickCheck?

Réponses

4 duplode Jan 02 2021 at 06:30

foldrpeut être obtenu à partir foldMap de l'utilisation du Endomonoïde , la a -> b -> bfonction transformant les avaleurs en b -> bfonctions 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 foldrdoit ê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 foldrtel 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. .

3 DDub Jan 02 2021 at 05:40

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 Showles fonctions ing générées par quickcheck pour un peu plus d'informations.

La façon d'obtenir des Showfonctions 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 foldablefonction dans laquelle vous utilisez le type Fun a bà la place a -> bet applyFunsi nécessaire pour appliquer les fonctions.

2 javinor Jan 02 2021 at 03:00

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é.