Haskell quickBatch: ZipList Monoid'i mconcat'ta test etmek yığın taşmasına neden olur

Question

ZipList Semigroup ve Monoid için artık örnekler oluşturdum. Bununla birlikte, testleri mconcat testinde monoid üzerinde quickBatch'ten çalıştırdığımda, bir yığın taşma hatası oluşuyor. Bu hatayı nasıl çözerim? Neden böyle bir hata var? O nedeniyle mi pure memptyben HaskellBook Bölüm 17 Uygulamalı bölüm 17.8 ZipList Monoid bu çoğunlukla var ben oldukça anlamıyorum, hangi?

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

Evet, hata nedenidir pure mempty, ancak bu pure memptyyanlış olduğu anlamına gelmez . Önce oraya bakalım.

Tanımda yer alan türlere bakmak çok yardımcı olur mempty = pure mempty:

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

Temel olarak, biz kullanacağız purebir yaratmak için operasyon ZipListait out memptyÇeşidi a. Buradan , purefor 'ZipList un tanımına bakmak yardımcı olur :

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

Toplam olarak, memptyiçin ZipList abir olacak ZipListsonsuz tekrar listesini ihtiva eden memptyaltta yatan Çeşidi değerleri a.

---

Bu hataya geri dönüyorsunuz. Testi çalıştırmayı denediğinizde monoidüzerinde ZipList (Sum Int), QuickCheck özelliklerinin bir diziyi test etmek için gidiyor.

• İlk ikisi sol kimlik ve sağ kimlik özelliklerini kontrol eder. Bunların yaptığı şey, türden değerler oluşturmak x :: ZipList (Sum Int)ve bunu doğrulamaktır x <> mempty = mempty <> x = x.
• Üçüncüsü, herhangi iki değer x, y :: ZipList (Sum Int)için bu x haritaya sahip olduğumuzu kontrol eder y = x <> y.
• Dördüncüsü, herhangi bir değer listesi için x :: [ZipList (Sum Int)], bunları katlamakla katlamanın mappendaynı olup olmadığını kontrol eder mconcat.

Devam etmeden önce, "herhangi bir değer için" dediğimde, gerçekten QuickCheck'in Arbitrarysöz konusu türden değerler üretmek için söz konusu türün örneğini kullandığını belirtmek istiyorum . Bundan başka, Arbitraryiçin, örneğin ZipList aile aynıdır Arbitraryiçin, örneğin [a], ancak daha sonra sarılmış ZipList. Son olarak, Arbitraryörneği [a]asla sonsuz bir liste oluşturmayacaktır (çünkü bunlar, sonsuz bir döngüye girme veya yığının taşması gibi eşitliği kontrol ederken sorunlara neden olacaktır), bu nedenle, türdeki "herhangi bir değer için" ZipList (Sum Int)bunlar asla sonsuz olmayacaktır. ya.

Spesifik olarak, bu, QuickCheck'in değeri hiçbir zaman keyfi olarak üretmeyeceği anlamına gelir, mempty :: ZipList açünkü bu sonsuz bir listedir.

---

Öyleyse neden ilk 3 pas geçiyor ama sonuncusu yığın taşmasıyla başarısız oluyor? İlk üç testte, sonsuz bir listeyi sonsuz bir listeyle karşılaştırmaya asla çalışmayız. Bakalım neden olmasın.

• İlk iki testlerde, baktığımız x <> mempty == xve mempty <> x == x. Her iki durumda da, xasla sonsuz olmayacak olan "keyfi" değerlerimizden biridir, bu nedenle bu eşitlik asla sonsuz bir döngüye girmeyecektir.
• Üçüncü testte, iki sonlu ZipLists üretiyorsun xve yve mappendonları bir arada ing. Bununla ilgili hiçbir şey sonsuz olmayacak.
• Üçüncü durumda, ZipListlerin bir listesini oluşturuyor ve mconcatlisteyi oluşturuyoruz. Peki liste boşsa ne olur? Eh, mconcat [] = memptyve boş bir listeyi katlamak üretir mempty. Bu, boş liste rastgele girdi olarak üretilirse (ki bu tamamen mümkündür), o zaman test sonsuz bir listenin başka bir sonsuz listeye eşit olduğunu doğrulamaya çalışacak ve bu da her zaman yığın taşması veya kara delik ile sonuçlanacaktır.

---

Bunu nasıl düzeltebilirsin? İki yöntem bulabilirim:

1. Sadece listenin bazı sonlu öneklerinde eşitliği karşılaştırması EqPropiçin kendi for sürümünüzü tanımlayabilirsiniz ZipList. Bu muhtemelen yeni bir tür sarmalayıcı (belki newtype MonZipList a = MonZipList (ZipList a)) yapmayı , bir grup örnek türetmeyi ve ardından bir EqProptanesini elle yazmayı içerir . Bu muhtemelen işe yarayacaktır, ancak biraz uygunsuzdur.

2. monoidDördüncü testin farklı bir versiyonunu kullanan kendi versiyonunuzu yazabilirsiniz . Örneğin, testin yalnızca boş olmayan listeler kullanmasını sağlayacak şekilde kısıtlarsanız herhangi bir sorun yaşamazsınız. Bunu yapmak için , monoidmülk testlerinin tanımına bakarak başlamalısınız . Şu anda "mconcat" özelliğini property mconcatPnerede olarak tanımladığına dikkat edin

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

QuickCheck'in kendi NonEmptyListsınıfını kullanarak , bunu aşağıdaki amaçlarınız için yeniden yazabilirsiniz:

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

Açıkçası, bu biraz daha zayıf bir durum, ama en azından takılmayacak bir durum.