Haskell quickBatch: probar ZipList Monoid en mconcat da como resultado un desbordamiento de pila

Question

He creado instancias huérfanas para ZipList Semigroup y Monoid. Sin embargo, cuando ejecuto las pruebas de quickBatch en monoid, en la prueba mconcat, hay un error de desbordamiento de pila. ¿Cómo resuelvo este error? ¿Por qué existe tal error? ¿Se debe a pure memptyque no entiendo del todo, ya que obtuve esto principalmente de HaskellBook Capítulo 17 Sección aplicable 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

Sí, el error se debe a pure mempty, pero eso no significa que pure memptyesté mal. Miremos allí primero.

Es de gran ayuda observar los tipos involucrados en la definición mempty = pure mempty:

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

Básicamente, usaremos la pureoperación para crear un tipo ZipListfuera memptydel tipo a. A partir de aquí, es útil ver la definición de pureparaZipList :

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

En total, memptyfor ZipList ava a ZipListcontener la lista infinitamente repetida de memptyvalores del tipo subyacente a.

---

De vuelta a este error que está recibiendo. Cuando intenta ejecutar la prueba monoidmás ZipList (Sum Int), QuickCheck se va a probar una secuencia de propiedades.

• Los dos primeros comprueban las propiedades de identidad izquierda y derecha. Lo que hacen es generar valores de tipo x :: ZipList (Sum Int)y verificarlo x <> mempty = mempty <> x = x.
• El tercero comprueba que para dos valores cualesquiera x, y :: ZipList (Sum Int), tenemos ese x mappend y = x <> y.
• El cuarto comprueba que para cualquier lista de valores x :: [ZipList (Sum Int)], doblarlos con mappendes lo mismo que mconcathacerlo.

Antes de continuar, es muy importante tener en cuenta que cuando digo "para cualquier valor", realmente me refiero a que QuickCheck está utilizando la Arbitraryinstancia de dicho tipo para generar valores de ese tipo. Además, la Arbitraryinstancia de ZipList aes la misma que la Arbitraryinstancia de [a]pero luego se incluye ZipList. Por último, la Arbitraryinstancia de [a]nunca producirá una lista infinita (porque causarán problemas cuando verifique la igualdad, como entrar en un bucle infinito o desbordar la pila), por lo que estos "para cualquier valor" de tipo ZipList (Sum Int)nunca serán infinitos ya sea.

Específicamente, esto significa que QuickCheck nunca generará arbitrariamente el valor mempty :: ZipList aporque esta es una lista infinita.

---

Entonces, ¿por qué pasan los primeros 3 pero el último falla con un desbordamiento de pila? En las primeras tres pruebas, nunca terminamos tratando de comparar una lista infinita con una lista infinita. Veamos por qué no.

• En las dos primeras pruebas, miramos x <> mempty == xy mempty <> x == x. En ambos casos, xes uno de nuestros valores "arbitrarios", que nunca será infinito, por lo que esta igualdad nunca entrará en un bucle infinito.
• En la tercera prueba, estamos generando dos ZipLists finitos xy y, y mappendde todas ellas. Nada de esto será infinito.
• En el tercer caso, estamos generando una lista de ZipLists y mconcatcompletando la lista. Pero, ¿qué pasa si la lista está vacía? Bueno, mconcat [] = memptyy doblar una lista vacía produce mempty. Esto significa que, si la lista vacía se genera como entrada arbitraria (lo cual es perfectamente posible), entonces la prueba intentará confirmar que una lista infinita es igual a otra lista infinita, lo que siempre resultará en un desbordamiento de pila o un agujero negro.

---

¿Cómo puede arreglarlo? Puedo pensar en dos métodos:

1. Puede definir su propia versión de EqPropfor ZipListpara que solo compare la igualdad en algún prefijo finito de la lista. Esto probablemente implicaría hacer un contenedor de tipo nuevo (quizás newtype MonZipList a = MonZipList (ZipList a)), derivar un montón de instancias y luego escribir una EqPropa mano. Esto probablemente funcionará, pero es un poco poco elegante.

2. Puede escribir su propia versión monoidusando una versión diferente de la cuarta prueba. Por ejemplo, si lo restringe para que la prueba solo use listas no vacías, entonces no tendrá ningún problema. Para hacer esto, debe comenzar mirando la definición de las monoidpruebas de propiedad . Tenga en cuenta que actualmente define la propiedad "mconcat" como property mconcatPdonde

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

Usando la propia NonEmptyListclase de QuickCheck , puede reescribir esto para sus propósitos como:

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

Obviamente, esta es una condición un poco más débil, pero al menos es una que no se bloquea.