Haskell quickBatch: Testowanie ZipList Monoid w mconcat powoduje przepełnienie stosu

Question

utworzyłem osierocone instancje dla ZipList Semigroup i Monoid. Jednak gdy uruchamiam testy z quickBatch na monoidzie, podczas testu mconcat pojawia się błąd przepełnienia stosu. Jak rozwiązać ten błąd? Dlaczego jest taki błąd? Czy jest to spowodowane pure mempty, czego nie do końca rozumiem, ponieważ dostałem to głównie z HaskellBook Rozdział 17 Zastosowanie sekcja 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

Tak, błąd jest spowodowany pure mempty, ale to nie znaczy, że pure memptyjest zły. Spójrzmy najpierw tam.

Bardzo pomaga przyjrzenie się typom związanym z definicją mempty = pure mempty:

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

Zasadniczo zamierzamy użyć tej pureoperacji do utworzenia ZipListout of the memptytype a. Pomaga stąd spojrzeć na definicję puredlaZipList :

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

W sumie memptyfor ZipList abędzie ZipListzawierać nieskończenie powtarzającą się listę memptywartości typu bazowego a.

---

Wróć do tego błędu, który otrzymujesz. Podczas próby uruchomienia testu monoidna ZipList (Sum Int), QuickCheck zamierza przetestować sekwencję właściwości.

• Pierwsze dwa sprawdzają lewą tożsamość i prawą tożsamość. To, co robią, to generowanie wartości typu x :: ZipList (Sum Int)i weryfikacja tego x <> mempty = mempty <> x = x.
• Trzeci sprawdza, czy dla dowolnych dwóch wartości x, y :: ZipList (Sum Int)mamy to x mappend y = x <> y.
• Czwarty sprawdza, czy w przypadku dowolnej listy wartości x :: [ZipList (Sum Int)]złożenie ich za pomocą mappendjest takie samo jak mconcatich złożenie .

Zanim przejdę dalej, naprawdę ważne jest, aby zauważyć, że kiedy mówię „dla dowolnej wartości”, naprawdę mam na myśli, że funkcja QuickCheck używa Arbitrarywystąpienia wspomnianego typu do generowania wartości tego typu. Ponadto Arbitraryinstancja for ZipList ajest taka sama jak Arbitraryinstancja for, [a]ale jest następnie opakowana ZipList. Na koniec Arbitraryinstancja for [a]nigdy nie utworzy nieskończonej listy (ponieważ będą one powodować problemy podczas sprawdzania równości, np. Wchodzenie w nieskończoną pętlę lub przepełnienie stosu), więc te typy „dla dowolnych wartości” ZipList (Sum Int)nigdy nie będą nieskończone zarówno.

W szczególności oznacza to, że funkcja QuickCheck nigdy nie wygeneruje arbitralnie wartości, mempty :: ZipList aponieważ jest to nieskończona lista.

---

Dlaczego więc pierwsze 3 pasują, a ostatnie kończy się niepowodzeniem z przepełnieniem stosu? W pierwszych trzech testach nigdy nie próbujemy porównać nieskończonej listy z nieskończoną listą. Zobaczmy, dlaczego nie.

• W pierwszych dwóch testach przyglądamy się x <> mempty == xi mempty <> x == x. W obu przypadkach xjest to jedna z naszych „arbitralnych” wartości, która nigdy nie będzie nieskończona, więc ta równość nigdy nie wejdzie w nieskończoną pętlę.
• W trzecim badaniu, jesteśmy generując dwa skończone ZipLists xi yi mappending je razem. Nic w tym nie będzie nieskończone.
• W trzecim przypadku tworzymy listę ZipLists i mconcatuzupełniamy ją. Ale co się stanie, jeśli lista jest pusta? Cóż, mconcat [] = memptya zwinięcie pustej listy daje mempty. Oznacza to, że jeśli pusta lista jest generowana jako dowolne dane wejściowe (co jest całkowicie możliwe), test spróbuje potwierdzić, że nieskończona lista jest równa innej nieskończonej liście, co zawsze spowoduje przepełnienie stosu lub czarną dziurę.

---

Jak możesz to naprawić? Mogę wymyślić dwie metody:

1. Możesz zdefiniować własną wersję EqPropfor, ZipListtak aby porównywała równość tylko na jakimś skończonym przedrostku listy. Prawdopodobnie wymagałoby to stworzenia opakowania nowego typu (być może newtype MonZipList a = MonZipList (ZipList a)), wyprowadzenia kilku instancji, a następnie EqPropręcznego napisania jednego. To prawdopodobnie zadziała, ale jest trochę nieeleganckie.

2. Możesz napisać własną wersję, monoidktóra korzysta z innej wersji czwartego testu. Na przykład, jeśli ograniczysz to tak, aby test używał tylko niepustych list, nie będziesz mieć żadnego problemu. Aby to zrobić, należy zacząć od przyjrzenia się definicji monoidtestów właściwości . Zauważ, że obecnie definiuje on właściwość „mconcat” jako property mconcatPwhere

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

Korzystając z własnej NonEmptyListklasy QuickCheck , możesz przepisać to do swoich celów jako:

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

Oczywiście jest to nieco słabszy stan, ale przynajmniej taki, który się nie zawiesza.