Haskell quickBatch: il test di ZipList Monoid su mconcat genera un overflow dello stack
ho creato istanze orfane per ZipList Semigroup e Monoid. Tuttavia, quando eseguo i test da quickBatch su monoid, al test mconcat, si verifica un errore di overflow dello stack. Come risolvo questo errore? Perché c'è un tale errore? È a causa di pure mempty
ciò che non capisco perché l'ho ottenuto principalmente da HaskellBook Capitolo 17 Sezione applicativa 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
Risposte
Sì, l'errore è dovuto a pure mempty
, ma ciò non significa che pure mempty
sia sbagliato. Diamo prima un'occhiata lì.
Aiuta molto guardare i tipi coinvolti nella definizione mempty = pure mempty
:
mempty :: ZipList a
mempty = (pure :: a -> ZipList a) (mempty :: a)
Fondamentalmente, useremo l' pure
operazione per creare un ZipList
out of the mempty
type a
. Da qui è utile esaminare la definizione di pureperZipList :
pure :: a -> ZipList a
pure x = ZipList (repeat x)
In totale, mempty
for ZipList a
sarà a ZipList
contenente l'elenco ripetuto all'infinito di mempty
valori del tipo sottostante a
.
Torna a questo errore che stai ricevendo. Quando si tenta di eseguire il test monoid
sopra ZipList (Sum Int)
, QuickCheck sta per testare una sequenza di proprietà.
- I primi due controllano le proprietà identità sinistra e identità destra. Ciò che fanno è generare valori di tipo
x :: ZipList (Sum Int)
e verificarlox <> mempty = mempty <> x = x
. - Il terzo controlla che per due valori qualsiasi
x, y :: ZipList (Sum Int)
, abbiamo quellax
mappaturay = x <> y
. - Il quarto controlla che per qualsiasi elenco di valori
x :: [ZipList (Sum Int)]
, piegarli conmappend
sia lo stesso chemconcat
inserirli.
Prima di continuare, è molto importante notare che quando dico "per qualsiasi valore", intendo davvero che QuickCheck sta usando l' Arbitrary
istanza di detto tipo per generare valori di quel tipo. Inoltre, l' Arbitrary
istanza per ZipList a
è la stessa Arbitrary
dell'istanza per [a]
ma poi è racchiusa ZipList
. Infine, l' Arbitrary
istanza di [a]
non produrrà mai un elenco infinito (perché questi causeranno problemi quando verifichi l'uguaglianza, come entrare in un ciclo infinito o traboccare lo stack), quindi questi "per qualsiasi valore" di tipo ZipList (Sum Int)
non saranno mai infiniti o.
In particolare, ciò significa che QuickCheck non genererà mai arbitrariamente il valore mempty :: ZipList a
perché si tratta di un elenco infinito.
Allora perché il primo passaggio 3 ma l'ultimo fallisce con uno stack overflow? Nei primi tre test, non si finisce mai per provare a confrontare una lista infinita con una lista infinita. Vediamo perché no.
- Nei primi due test, stiamo esaminando
x <> mempty == x
emempty <> x == x
. In entrambi i casi,x
è uno dei nostri valori "arbitrari", che non sarà mai infinito, quindi questa uguaglianza non entrerà mai in un ciclo infinito. - Nella terza prova, stiamo generando due ZipLists finite
x
edy
emappend
li ing insieme. Niente di tutto questo sarà infinito. - Nel terzo caso, stiamo generando un elenco di ZipList e
mconcat
enfatizzando l'elenco. Ma cosa succede se l'elenco è vuoto? Bene,mconcat [] = mempty
e piegare una lista vuota producemempty
. Ciò significa che, se l'elenco vuoto viene generato come input arbitrario (il che è perfettamente possibile), il test proverà a confermare che un elenco infinito è uguale a un altro elenco infinito, il che si tradurrà sempre in un overflow dello stack o in un buco nero.
Come puoi risolvere questo problema? Posso trovare due metodi:
Puoi definire la tua versione di
EqProp
for inZipList
modo che confronti l'uguaglianza solo su alcuni prefissi finiti della lista. Ciò probabilmente implicherebbe la creazione di un wrapper newtype (forsenewtype MonZipList a = MonZipList (ZipList a)
), la derivazione di un gruppo di istanze e quindi la scrittura diEqProp
uno a mano. Probabilmente funzionerà, ma è un po 'inelegante.Puoi scrivere la tua versione
monoid
che utilizza una versione diversa del quarto test. Ad esempio, se lo limiti in modo che il test utilizzi solo elenchi non vuoti, non avrai alcun problema. Per fare ciò, dovresti iniziare guardando la definizione dei monoidtest di proprietà . Si noti che attualmente definisce la proprietà "mconcat" comeproperty mconcatP
dove
mconcatP :: [a] -> Property
mconcatP as = mconcat as =-= foldr mappend mempty as
Utilizzando la NonEmptyList
classe di QuickCheck , puoi riscriverlo per i tuoi scopi come:
mconcatP :: NonEmptyList a -> Property
mconcatP (NonEmptyList as) = mconcat as =-= foldr mappend mempty as
Ovviamente, questa è una condizione leggermente più debole, ma almeno è una che non si bloccherà.