Mengapa penerapan ini merupakan contoh yang buruk dari Kelas Jenis Lipat?

Question

Saya sedang mengerjakan Buku Haskell yang luar biasa . Di akhir bab Traversable (21), saya perlu menulis sebuah instance untuk Tree berikut:

data Tree a =
    Empty
  | Leaf a
  | Node (Tree a) a (Tree a)

Berikut ini tautan ke kode lengkap solusi saya. Latihan merekomendasikan untuk mencoba menerapkan keduanya foldMapdan foldr. Beginilah cara saya menerapkan foldr(tanpa banyak memikirkan urutan pemanggilan):

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  f x $ foldr f (foldr f z left) right

Saya kemudian menerapkan foldMapsebagai berikut:

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

Ketika saya menjalankan kelompok foldableuji QuickCheck , saya mengalami beberapa kegagalan. Mengubah foldrimplementasi saya menjadi yang berikut membuat semua tes lulus:

foldr _ z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left

Saya mencoba menjalankan sendiri kasus pengujian yang gagal, tetapi tidak dapat membuat ulang kegagalan:

*Ch21_12_ExercisesTree Data.Monoid> tree = Node (Node (Leaf (-5)) 3 (Node (Leaf 3) 5 Empty)) (-2) Empty
*Ch21_12_ExercisesTree Data.Monoid> foldr (<>) (mempty :: Sum Int) t
Sum {getSum = 4}
*Ch21_12_ExercisesTree Data.Monoid> foldMap Sum t
Sum {getSum = 4}

Saya curiga ada sesuatu yang tidak saya foldpahami tentang fungsi ing yang digunakan QuickCheck.

Pertanyaan:

1. Mengapa kegagalan terjadi?
2. Apakah ada cara untuk mendapatkan fungsi yang digunakan dalam pengujian dengan QuickCheck?

Answer 1

foldrdapat diperoleh foldMap dengan menggunakan Endomonoid , dengan a -> b -> bfungsi mengubah anilai menjadi b -> bfungsi yang dapat disusun (secara monoid). Karena itu, jika Anda foldMapadalah ...

foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) = 
  foldMap f left <> f x <> foldMap f right

... yang sesuai foldrharus:

foldr f z Empty = id z  -- mempty amounts to id
foldr f z (Leaf x) = (f x) z
foldr f z (Node left x right) = 
  ((\e -> foldr f e left) . f x . (\e -> foldr f e right)) z  -- (<>) amounts to (.)

Jika kita merapikannya sedikit ...

foldr f z Empty = z
foldr f z (Leaf x) = f x z
foldr f z (Node left x right) = 
  foldr f (f x (foldr f z right)) left)

... kami mendapatkan definisi yang benar foldrseperti yang tertulis dalam pertanyaan Anda. Karena perbedaan antara implementasi berkaitan dengan urutan komposisi, mencoba monoid non-komutatif langsung mengarah ke kasus yang gagal, seperti yang telah Anda ketahui .

Pada subquestion QuickCheck, saya tunduk pada jawaban DDub. .

Answer 2

Seperti yang telah Anda simpulkan, alasan Anda mengalami kegagalan adalah karena kedua implementasi tersebut dapat dibedakan, yang dapat Anda amati dengan menggunakan monoid non-komutatif.

---

Mendapatkan fungsi yang digunakan dengan quickcheck tidaklah sesederhana itu. Lihat, sebagai contoh, pertanyaan / jawaban tentang Showfungsi yang dihasilkan oleh pemeriksaan cepat untuk informasi lebih lanjut.

Cara untuk mendapatkan Showfungsi bisa keluar dari QuickCheck adalah untuk membungkus fungsi di dalam Funjenis . Meskipun demikian, kode yang Anda panggil ( ditemukan di sini ) hanya menggunakan fungsi secara langsung, jadi tidak akan pernah bisa ditampilkan. Salah satu opsi yang dapat Anda coba adalah membuat versi Anda sendiri dari foldablefungsi di mana Anda menggunakan tipe Fun a bsebagai pengganti a -> bdan applyFunseperlunya untuk menerapkan fungsi.

Answer 3

Saya baru menyadari bahwa saya menggunakan Monoid komutatif ... Saya dapat membuat ulang kegagalan menggunakan Monoid non-komutatif:

> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}

Ini mungkin kasus sederhana. Saya membayangkan bahwa dalam kode produksi dengan tipe data nyata ini bisa jauh lebih rumit.