Haskell quickBatch: Das Testen von ZipList Monoid bei mconcat führt zu einem Stapelüberlauf

Jan 14 2021

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

1 DDub Jan 18 2021 at 01:54

Ja, der Fehler ist darauf zurückzuführen pure mempty, aber das bedeutet nicht, dass er pure memptyfalsch 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 pureOperation verwenden, um einen ZipListOut-of- memptyof-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 memptyfor ZipList aeine ZipListListe mit unendlich wiederholten memptyWerten 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 dies x <> mempty = mempty <> x = x.
  • Der dritte prüft, ob für zwei beliebige Werte x, y :: ZipList (Sum Int)diese x Zuordnung vorliegt y = x <> y.
  • Der vierte prüft, ob für eine Liste von Werten das x :: [ZipList (Sum Int)]Falten mit denen mappendidentisch ist, mit denen sie mconcatgefaltet werden.

Bevor ich fortfahre, ist es wirklich wichtig zu beachten, dass wenn ich "für jeden Wert" sage, ich wirklich meine, dass QuickCheck die ArbitraryInstanz dieses Typs verwendet, um Werte dieses Typs zu generieren. Darüber hinaus ist die ArbitraryInstanz für ZipList adieselbe wie die ArbitraryInstanz für [a], wird dann jedoch eingepackt ZipList. Schließlich wird die ArbitraryInstanz 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 ada 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 == xund mempty <> x == x. In beiden Fällen xist 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 xund yund mappending sie zusammen. Nichts davon wird unendlich sein.
  • Im dritten Fall generieren wir eine Liste von ZipLists und mconcataktivieren die Liste. Aber was passiert, wenn die Liste leer ist? Nun, mconcat [] = memptyund das Falten einer leeren Liste ergibt mempty. 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:

  1. Sie können Ihre eigene Version von EqPropfor definieren, ZipListsodass die Gleichheit nur mit einem endlichen Präfix der Liste verglichen wird. Dies würde wahrscheinlich beinhalten, einen Newtype-Wrapper (vielleicht newtype MonZipList a = MonZipList (ZipList a)) zu erstellen , eine Reihe von Instanzen abzuleiten und dann EqPropeinen von Hand zu schreiben . Dies wird wahrscheinlich funktionieren, ist aber etwas unelegant.

  2. 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 als property mconcatPwo

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

Mit der eigenen NonEmptyListKlasse 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.