Haskell quickBatch: Teste ZipList Monoid no mconcat resulta em estouro de pilha

Question

Eu criei instâncias órfãs para ZipList Semigroup e Monoid. No entanto, quando executo os testes do quickBatch no monóide, no teste mconcat, ocorre um erro de estouro de pilha. Como faço para resolver esse erro? Por que existe esse erro? É devido a pure mempty, o que eu não entendo muito bem, já que obtive isso principalmente de HaskellBook Capítulo 17 Seção aplicável 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

Sim, o erro é devido a pure mempty, mas isso não significa que pure memptyesteja errado. Vamos ver primeiro.

Ajuda muito olhar para os tipos envolvidos na definição mempty = pure mempty:

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

Basicamente, vamos usar a pureoperação para criar um ZipListfora memptydo tipo a. Ele ajuda daqui a olhar para a definição de pureparaZipList :

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

No total, memptypara ZipList ase vai ser um ZipListque contém a lista infinitamente repetição de memptyvalores do tipo subjacente a.

---

De volta a este erro que você está obtendo. Quando você tenta executar o teste monoidnovamente ZipList (Sum Int), o QuickCheck testa uma sequência de propriedades.

• Os dois primeiros verificam as propriedades de identidade esquerda e direita. O que eles fazem é gerar valores do tipo x :: ZipList (Sum Int)e verificar isso x <> mempty = mempty <> x = x.
• O terceiro verifica se, para quaisquer dois valores x, y :: ZipList (Sum Int), temos esse x mappend y = x <> y.
• A quarta verifica se, para qualquer lista de valores x :: [ZipList (Sum Int)], dobrá-los com mappendé o mesmo que dobrá mconcat-los.

Antes de continuar, é muito importante notar que quando digo "para qualquer valor", realmente quero dizer que o QuickCheck está usando a Arbitraryinstância do referido tipo para gerar valores desse tipo. Além disso, a Arbitraryinstância de ZipList aé igual à Arbitraryinstância de, [a]mas depois incluída ZipList. Por último, a Arbitraryinstância de [a]nunca produzirá uma lista infinita (porque isso vai causar problemas quando você está verificando a igualdade, como entrar em um loop infinito ou estourar a pilha), então esses "para quaisquer valores" do tipo ZipList (Sum Int)nunca serão infinitos qualquer.

Especificamente, isso significa que QuickCheck nunca gerará o valor arbitrariamente, mempty :: ZipList aporque esta é uma lista infinita.

---

Então, por que os 3 primeiros passam, mas o último falha com um estouro de pilha? Nos três primeiros testes, nunca acabamos tentando comparar uma lista infinita com uma lista infinita. Vamos ver porque não.

• Nos primeiros dois testes, estamos observando x <> mempty == xe mempty <> x == x. Em ambos os casos, xé um de nossos valores "arbitrários", que nunca será infinito, portanto, essa igualdade nunca entrará em um loop infinito.
• No terceiro teste, nós estamos gerando dois ZipLists finitos xe ye mappending-los juntos. Nada sobre isso será infinito.
• No terceiro caso, estamos gerando uma lista de ZipLists e mconcataumentando a lista. Mas, o que acontece se a lista estiver vazia? Bem, mconcat [] = memptye dobrar uma lista vazia produz mempty. Isso significa que, se a lista vazia for gerada como entrada arbitrária (o que é perfeitamente possível), o teste tentará confirmar que uma lista infinita é igual a outra lista infinita, o que sempre resultará em estouro de pilha ou buraco negro.

---

Como você pode consertar isso? Posso inventar dois métodos:

1. Você pode definir sua própria versão de EqPropfor ZipListpara que compare apenas a igualdade em algum prefixo finito da lista. Isso provavelmente envolveria fazer um wrapper newtype (talvez newtype MonZipList a = MonZipList (ZipList a)), derivar um grupo de instâncias e, em seguida, escrever uma EqPropà mão. Isso provavelmente funcionará, mas é um pouco deselegante.

2. Você pode escrever sua própria versão do monoidque usa uma versão diferente do quarto teste. Por exemplo, se você restringir para que o teste use apenas listas não vazias, você não terá nenhum problema. Para fazer isso, você deve começar examinando a definição dos monoidtestes de propriedade . Observe que atualmente define a propriedade "mconcat" como property mconcatPonde

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

Usando a própria NonEmptyListclasse do QuickCheck , você pode reescrever isso para seus propósitos como:

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

Obviamente, esta é uma condição um pouco mais fraca, mas pelo menos não trava.