Haskell QuickBatch: le test de ZipList Monoid chez mconcat entraîne un débordement de pile

Question

J'ai créé des instances orphelines pour ZipList Semigroup et Monoid. Cependant, lorsque j'exécute les tests de quickBatch sur monoïde, au test mconcat, il y a une erreur de débordement de pile. Comment résoudre cette erreur? Pourquoi une telle erreur? Est-ce dû à pure mempty, ce que je ne comprends pas tout à fait car je l'ai obtenu principalement de HaskellBook Chapitre 17 Section applicative 17.8 ZipList Monoid?

zl :: ZipList (Sum Int)
zl = ZipList [1,1 :: Sum Int]
instance Semigroup a 
  => Semigroup (ZipList a) where
    (<>) = liftA2 (<>)
instance (Eq a, Monoid a)
  => Monoid (ZipList a) where
    mempty = pure mempty 
    mappend = (<>)
    mconcat as = 
      foldr mappend mempty as
main :: IO ()
main = do 
  quickBatch $ monoid zl

Answer 1

Oui, l'erreur est due à pure mempty, mais cela ne veut pas dire que pure memptyc'est faux. Regardons-y d'abord.

Il est très utile de regarder les types impliqués dans la définition mempty = pure mempty:

mempty :: ZipList a
mempty = (pure :: a -> ZipList a) (mempty :: a)

Fondamentalement, nous allons utiliser l' pureopération pour créer un ZipListhors memptydu type a. À partir de là, il est utile de regarder la définition de purepourZipList :

pure :: a -> ZipList a
pure x = ZipList (repeat x)

Au total, memptyfor ZipList ava être un ZipListcontenant la liste infiniment répétée de memptyvaleurs du type sous-jacent a.

---

Revenez à cette erreur que vous obtenez. Lorsque vous essayez d'exécuter le test monoidsur ZipList (Sum Int), QuickCheck va tester une séquence de propriétés.

• Les deux premiers vérifient l'identité de gauche et les propriétés d'identité de droite. Ils génèrent des valeurs de type x :: ZipList (Sum Int)et vérifient cela x <> mempty = mempty <> x = x.
• Le troisième vérifie que pour deux valeurs quelconques x, y :: ZipList (Sum Int), nous avons ce x mappend y = x <> y.
• Le quatrième vérifie que, pour toute liste de valeurs x :: [ZipList (Sum Int)], les plier avec mappendest identique à mconcatleur création.

Avant de continuer, il est vraiment important de noter que lorsque je dis "pour n'importe quelle valeur", je veux vraiment dire que QuickCheck utilise l' Arbitraryinstance dudit type pour générer des valeurs de ce type. De plus, l' Arbitraryinstance de ZipList aest la même que celle Arbitraryde [a]mais est ensuite encapsulée ZipList. Enfin, l' Arbitraryinstance de [a]ne produira jamais une liste infinie (parce que celles-ci poseront des problèmes lorsque vous vérifiez l'égalité, comme entrer dans une boucle infinie ou déborder de la pile), donc ces "pour toutes les valeurs" de type ZipList (Sum Int)ne seront jamais infinies Soit.

Plus précisément, cela signifie que QuickCheck ne générera jamais arbitrairement la valeur mempty :: ZipList acar il s'agit d'une liste infinie.

---

Alors pourquoi les 3 premiers passent mais le dernier échoue avec un débordement de pile? Dans les trois premiers tests, nous n'essayons jamais de comparer une liste infinie à une liste infinie. Voyons pourquoi pas.

• Dans les deux premiers tests, nous examinons x <> mempty == xet mempty <> x == x. Dans les deux cas, xest l'une de nos valeurs "arbitraires", qui ne sera jamais infinie, donc cette égalité n'entrera jamais dans une boucle infinie.
• Dans le troisième test, nous générons deux ZipLists finis xet yet mappendles ing ensemble. Rien de tout cela ne sera infini.
• Dans le troisième cas, nous générons une liste de ZipLists et mconcatactivons la liste. Mais que se passe-t-il si la liste est vide? Eh bien, mconcat [] = memptyet le pliage d'une liste vide produit mempty. Cela signifie que si la liste vide est générée comme entrée arbitraire (ce qui est parfaitement possible), alors le test tentera de confirmer qu'une liste infinie est égale à une autre liste infinie, ce qui entraînera toujours un débordement de pile ou un trou noir.

---

Comment peux-tu réparer cela? Je peux proposer deux méthodes:

1. Vous pouvez définir votre propre version de EqPropfor ZipListafin qu'elle ne compare l'égalité que sur un préfixe fini de la liste. Cela impliquerait probablement de créer un wrapper newtype (peut-être newtype MonZipList a = MonZipList (ZipList a)), de dériver un groupe d'instances, puis d'en écrire une EqPropà la main. Cela fonctionnera probablement mais est un peu inélégant.

2. Vous pouvez écrire votre propre version monoidqui utilise une version différente du quatrième test. Par exemple, si vous le restreignez pour que le test n'utilise que des listes non vides, vous n'aurez aucun problème. Pour ce faire, vous devez commencer par regarder la définition des monoidtests de propriété . Notez qu'il définit actuellement la propriété "mconcat" comme property mconcatPoù

mconcatP :: [a] -> Property
mconcatP as = mconcat as =-= foldr mappend mempty as

En utilisant la propre NonEmptyListclasse de QuickCheck , vous pouvez réécrire ceci à vos fins comme:

mconcatP :: NonEmptyList a -> Property
mconcatP (NonEmptyList as) = mconcat as =-= foldr mappend mempty as

Évidemment, c'est une condition légèrement plus faible, mais au moins c'est une condition qui ne se bloquera pas.