Haskell quickBatch: Menguji ZipList Monoid di mconcat menghasilkan stack overflow

Jan 14 2021

Saya telah membuat instance yatim piatu untuk ZipList Semigroup dan Monoid. Namun, ketika saya menjalankan tes dari quickBatch pada monoid, pada tes mconcat, ada kesalahan stack overflow. Bagaimana cara mengatasi kesalahan ini? Mengapa ada kesalahan seperti itu? Apakah karena pure mempty, yang saya tidak begitu mengerti karena saya mendapatkannya sebagian besar dari HaskellBook Bab 17 Aplikatif bagian 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

Jawaban

1 DDub Jan 18 2021 at 01:54

Ya, kesalahannya memang karena pure mempty, tapi bukan berarti pure memptyitu salah. Mari kita lihat dulu.

Sangat membantu untuk melihat jenis yang terlibat dalam definisi mempty = pure mempty:

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

Pada dasarnya, kita akan menggunakan pureoperasi untuk membuat ZipListkeluar dari memptyjenis a. Akan membantu dari sini untuk melihat definisi pureuntukZipList :

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

Secara total, memptyfor ZipList aakan menjadi yang ZipListberisi daftar memptynilai berulang yang tak terbatas dari tipe yang mendasarinya a.


Kembali ke kesalahan ini yang Anda dapatkan. Ketika Anda mencoba untuk menjalankan tes monoidlebih ZipList (Sum Int), QuickCheck akan menguji urutan properti.

  • Dua yang pertama memeriksa identitas kiri dan properti identitas kanan. Apa yang dilakukan ini adalah menghasilkan nilai tipe x :: ZipList (Sum Int)dan memverifikasi itu x <> mempty = mempty <> x = x.
  • Pemeriksaan ketiga bahwa untuk setiap dua nilai x, y :: ZipList (Sum Int), kita memiliki x mappend y = x <> y.
  • Pemeriksaan keempat bahwa untuk daftar nilai apa pun x :: [ZipList (Sum Int)], melipatnya mappendsama mconcatdengan memasukkannya.

Sebelum saya melanjutkan, sangat penting untuk dicatat bahwa ketika saya mengatakan "untuk nilai apa pun", maksud saya QuickCheck menggunakan Arbitrarycontoh jenis tersebut untuk menghasilkan nilai jenis itu. Selanjutnya, Arbitraryinstance untuk ZipList asama dengan Arbitraryinstance untuk [a]tetapi kemudian dibungkus ZipList. Terakhir, Arbitraryinstance untuk [a]tidak akan pernah menghasilkan daftar tanpa batas (karena hal itu akan menyebabkan masalah saat Anda memeriksa kesetaraan, seperti masuk ke loop tanpa batas atau memenuhi tumpukan), jadi jenis "untuk nilai apa pun" ZipList (Sum Int)ini tidak akan pernah terbatas antara.

Secara khusus, ini berarti QuickCheck tidak akan pernah menghasilkan nilai secara sewenang-wenang mempty :: ZipList akarena ini adalah daftar yang tidak terbatas.


Jadi mengapa 3 yang pertama lolos tetapi yang terakhir gagal dengan stack overflow? Dalam tiga pengujian pertama, kami tidak pernah mencoba membandingkan daftar tak terbatas dengan daftar tak terbatas. Mari kita lihat mengapa tidak.

  • Dalam dua pengujian pertama, kami melihat x <> mempty == xdan mempty <> x == x. Dalam kedua kasus, xadalah salah satu nilai "sewenang-wenang" kami, yang tidak akan pernah tak terbatas, jadi persamaan ini tidak akan pernah masuk ke putaran tak hingga.
  • Dalam tes ketiga, kita menghasilkan dua ZipLists terbatas xdan ydan mappending mereka bersama-sama. Tidak ada tentang ini yang tidak terbatas.
  • Dalam kasus ketiga, kami membuat daftar ZipLists dan mconcatmengaktifkan daftarnya. Tapi, apa yang terjadi jika daftarnya kosong? Nah,, mconcat [] = memptydan melipat daftar kosong menghasilkan mempty. Ini berarti, jika daftar kosong dibuat sebagai masukan arbitrer (yang sangat mungkin), maka pengujian akan mencoba untuk memastikan bahwa daftar tak terbatas sama dengan daftar tak terbatas lainnya, yang akan selalu menghasilkan tumpukan melimpah atau lubang hitam.

Bagaimana Anda memperbaikinya? Saya dapat menemukan dua metode:

  1. Anda dapat menentukan versi EqPropuntuk Anda sendiri ZipListsehingga hanya membandingkan persamaan pada beberapa awalan terbatas dari daftar. Ini kemungkinan akan melibatkan pembuatan pembungkus tipe baru (mungkin newtype MonZipList a = MonZipList (ZipList a)), mendapatkan banyak contoh, dan kemudian menulis EqPropsatu dengan tangan. Ini mungkin akan berhasil tetapi sedikit tidak elegan.

  2. Anda dapat menulis versi Anda sendiri monoidyang menggunakan versi berbeda dari tes keempat. Misalnya, jika Anda membatasinya sehingga pengujian hanya menggunakan daftar yang tidak kosong, Anda tidak akan mendapat masalah. Untuk melakukan ini, Anda harus mulai dengan melihat definisi monoidpengujian properti . Perhatikan bahwa saat ini mendefinisikan properti "mconcat" sebagai property mconcatPwhere

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

Menggunakan NonEmptyListkelas QuickCheck sendiri , Anda dapat menulis ulang ini untuk tujuan Anda sebagai:

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

Jelas, ini adalah kondisi yang sedikit lebih lemah, tetapi setidaknya itu tidak akan menggantung.