Haskell quickBatch: Das Testen von ZipList Monoid bei mconcat führt zu einem Stapelüberlauf
Ich habe verwaiste Instanzen für ZipList Semigroup und Monoid erstellt. Wenn ich jedoch die Tests von quickBatch auf Monoid ausführe, tritt beim mconcat-Test ein Stapelüberlauffehler auf. Wie behebe ich diesen Fehler? Warum gibt es so einen Fehler? Liegt es an pure mempty
, was ich nicht ganz verstehe, da ich dies hauptsächlich aus HaskellBook Kapitel 17 Anwendbarer Abschnitt 17.8 ZipList Monoid erhalten habe?
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

Antworten
Ja, der Fehler ist darauf zurückzuführen pure mempty
, aber das bedeutet nicht, dass er pure mempty
falsch ist. Schauen wir uns zuerst dort um.
Es ist sehr hilfreich, die an der Definition beteiligten Typen zu betrachten mempty = pure mempty
:
mempty :: ZipList a
mempty = (pure :: a -> ZipList a) (mempty :: a)
Grundsätzlich werden wir die pure
Operation verwenden, um einen ZipList
Out-of- mempty
of-Typ zu erstellen a
. Von hier aus hilft es, die Definition von purefor zu betrachtenZipList :
pure :: a -> ZipList a
pure x = ZipList (repeat x)
Insgesamt wird mempty
for ZipList a
eine ZipList
Liste mit unendlich wiederholten mempty
Werten des zugrunde liegenden Typs enthalten a
.
Zurück zu diesem Fehler, den Sie erhalten. Wenn Sie versuchen , den Test zu laufen monoid
über ZipList (Sum Int)
, wird Quick Check geht eine Folge von Eigenschaften zu testen.
- Die ersten beiden überprüfen die Eigenschaften der linken und rechten Identität. Diese generieren Werte vom Typ
x :: ZipList (Sum Int)
und überprüfen diesx <> mempty = mempty <> x = x
. - Der dritte prüft, ob für zwei beliebige Werte
x, y :: ZipList (Sum Int)
diesex
Zuordnung vorliegty = x <> y
. - Der vierte prüft, ob für eine Liste von Werten das
x :: [ZipList (Sum Int)]
Falten mit denenmappend
identisch ist, mit denen siemconcat
gefaltet werden.
Bevor ich fortfahre, ist es wirklich wichtig zu beachten, dass wenn ich "für jeden Wert" sage, ich wirklich meine, dass QuickCheck die Arbitrary
Instanz dieses Typs verwendet, um Werte dieses Typs zu generieren. Darüber hinaus ist die Arbitrary
Instanz für ZipList a
dieselbe wie die Arbitrary
Instanz für [a]
, wird dann jedoch eingepackt ZipList
. Schließlich wird die Arbitrary
Instanz für [a]
niemals eine unendliche Liste erzeugen (da diese Probleme verursachen, wenn Sie auf Gleichheit prüfen, z. B. in eine Endlosschleife gehen oder den Stapel überlaufen), sodass diese "für beliebige Werte" vom Typ ZipList (Sum Int)
niemals unendlich sein werden entweder.
Dies bedeutet insbesondere, dass QuickCheck den Wert niemals willkürlich generiert, mempty :: ZipList a
da dies eine unendliche Liste ist.
Warum scheitern die ersten 3, aber der letzte mit einem Stapelüberlauf? In den ersten drei Tests versuchen wir nie, eine unendliche Liste mit einer unendlichen Liste zu vergleichen. Mal sehen warum nicht.
- In den ersten beiden Tests, freuen wir uns
x <> mempty == x
undmempty <> x == x
. In beiden Fällenx
ist einer unserer "willkürlichen" Werte, der niemals unendlich sein wird, so dass diese Gleichheit niemals in eine Endlosschleife geraten wird. - Im dritten Test sind zu erzeugen wir zwei endliche ZipLists
x
undy
undmappend
ing sie zusammen. Nichts davon wird unendlich sein. - Im dritten Fall generieren wir eine Liste von ZipLists und
mconcat
aktivieren die Liste. Aber was passiert, wenn die Liste leer ist? Nun,mconcat [] = mempty
und das Falten einer leeren Liste ergibtmempty
. Das heißt, wenn die leere Liste als willkürliche Eingabe generiert wird (was durchaus möglich ist), versucht der Test zu bestätigen, dass eine unendliche Liste einer anderen unendlichen Liste entspricht, was immer zu einem Stapelüberlauf oder einem Schwarzen Loch führt.
Wie können Sie das beheben? Ich kann mir zwei Methoden einfallen lassen:
Sie können Ihre eigene Version von
EqProp
for definieren,ZipList
sodass die Gleichheit nur mit einem endlichen Präfix der Liste verglichen wird. Dies würde wahrscheinlich beinhalten, einen Newtype-Wrapper (vielleichtnewtype MonZipList a = MonZipList (ZipList a)
) zu erstellen , eine Reihe von Instanzen abzuleiten und dannEqProp
einen von Hand zu schreiben . Dies wird wahrscheinlich funktionieren, ist aber etwas unelegant.Sie können eine eigene Version davon schreiben
monoid
, die eine andere Version des vierten Tests verwendet. Wenn Sie es beispielsweise so einschränken, dass der Test nur nicht leere Listen verwendet, haben Sie kein Problem. Dazu sollten Sie sich zunächst die Definition der monoidEigenschaftstests ansehen . Beachten Sie, dass es definiert derzeit die „mconcat“ Eigenschaft alsproperty mconcatP
wo
mconcatP :: [a] -> Property
mconcatP as = mconcat as =-= foldr mappend mempty as
Mit der eigenen NonEmptyList
Klasse von QuickCheck können Sie diese für Ihre Zwecke wie folgt umschreiben:
mconcatP :: NonEmptyList a -> Property
mconcatP (NonEmptyList as) = mconcat as =-= foldr mappend mempty as
Offensichtlich ist dies ein etwas schwächerer Zustand, aber zumindest ist es einer, der nicht hängen bleibt.