Haskell quickBatch: Menguji ZipList Monoid di mconcat menghasilkan stack overflow
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
Ya, kesalahannya memang karena pure mempty
, tapi bukan berarti pure mempty
itu 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 pure
operasi untuk membuat ZipList
keluar dari mempty
jenis a
. Akan membantu dari sini untuk melihat definisi pureuntukZipList :
pure :: a -> ZipList a
pure x = ZipList (repeat x)
Secara total, mempty
for ZipList a
akan menjadi yang ZipList
berisi daftar mempty
nilai berulang yang tak terbatas dari tipe yang mendasarinya a
.
Kembali ke kesalahan ini yang Anda dapatkan. Ketika Anda mencoba untuk menjalankan tes monoid
lebih 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 itux <> mempty = mempty <> x = x
. - Pemeriksaan ketiga bahwa untuk setiap dua nilai
x, y :: ZipList (Sum Int)
, kita memilikix
mappendy = x <> y
. - Pemeriksaan keempat bahwa untuk daftar nilai apa pun
x :: [ZipList (Sum Int)]
, melipatnyamappend
samamconcat
dengan memasukkannya.
Sebelum saya melanjutkan, sangat penting untuk dicatat bahwa ketika saya mengatakan "untuk nilai apa pun", maksud saya QuickCheck menggunakan Arbitrary
contoh jenis tersebut untuk menghasilkan nilai jenis itu. Selanjutnya, Arbitrary
instance untuk ZipList a
sama dengan Arbitrary
instance untuk [a]
tetapi kemudian dibungkus ZipList
. Terakhir, Arbitrary
instance 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 a
karena 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 == x
danmempty <> x == x
. Dalam kedua kasus,x
adalah 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
x
dany
danmappend
ing mereka bersama-sama. Tidak ada tentang ini yang tidak terbatas. - Dalam kasus ketiga, kami membuat daftar ZipLists dan
mconcat
mengaktifkan daftarnya. Tapi, apa yang terjadi jika daftarnya kosong? Nah,,mconcat [] = mempty
dan melipat daftar kosong menghasilkanmempty
. 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:
Anda dapat menentukan versi
EqProp
untuk Anda sendiriZipList
sehingga hanya membandingkan persamaan pada beberapa awalan terbatas dari daftar. Ini kemungkinan akan melibatkan pembuatan pembungkus tipe baru (mungkinnewtype MonZipList a = MonZipList (ZipList a)
), mendapatkan banyak contoh, dan kemudian menulisEqProp
satu dengan tangan. Ini mungkin akan berhasil tetapi sedikit tidak elegan.Anda dapat menulis versi Anda sendiri
monoid
yang 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" sebagaiproperty mconcatP
where
mconcatP :: [a] -> Property
mconcatP as = mconcat as =-= foldr mappend mempty as
Menggunakan NonEmptyList
kelas 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.