เหตุใดการใช้งานนี้จึงเป็นตัวอย่างที่ไม่ดีของ Foldable Typeclass
ผมทำงานที่ยอดเยี่ยมผ่านHaskell หนังสือ ในตอนท้ายของบท Traversable (21) ฉันต้องเขียนอินสแตนซ์สำหรับ Tree ต่อไปนี้:
data Tree a =
Empty
| Leaf a
| Node (Tree a) a (Tree a)
นี่คือลิงค์ไปยังโค้ดทั้งหมดของโซลูชันของฉัน การออกกำลังกายแนะนำให้พยายามที่จะใช้ทั้งสองและfoldMap
foldr
นี่คือวิธีที่ฉันนำไปใช้foldr
(โดยไม่ต้องคิดมากกับคำสั่งเรียก):
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
จากนั้นฉันดำเนินการfoldMap
ดังนี้:
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
เมื่อฉันเรียกใช้foldable
ชุดทดสอบของ QuickCheck ฉันพบข้อผิดพลาดบางประการ การเปลี่ยนการfoldr
ใช้งานของฉันเป็นสิ่งต่อไปนี้ทำให้การทดสอบทั้งหมดผ่าน:
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
ฉันพยายามเรียกใช้กรณีทดสอบที่ล้มเหลวด้วยตัวเอง แต่ไม่สามารถสร้างความล้มเหลวขึ้นมาใหม่ได้:
*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}
ฉันสงสัยว่ามีบางอย่างที่ฉันไม่เข้าใจเกี่ยวกับfold
ฟังก์ชัน ing ที่ QuickCheck ใช้อยู่
คำถาม:
- เหตุใดจึงเกิดความล้มเหลว
- มีวิธีรับฟังก์ชันที่ใช้ในการทดสอบโดย QuickCheck หรือไม่?
คำตอบ
foldr
สามารถหาได้จากการfoldMap
ใช้Endoโมโนนอยด์โดยa -> b -> b
ฟังก์ชันจะเปลี่ยนa
ค่าเป็นb -> b
ฟังก์ชันที่สามารถประกอบ (โมโนนอยด์) ได้ เป็นอย่างนั้นถ้าคุณfoldMap
เป็น ...
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
... สิ่งที่สอดคล้องกันfoldr
จะต้อง:
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 (.)
ถ้าเราจัดระเบียบให้เรียบร้อยสักหน่อย ...
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)
... เราได้คำจำกัดความที่ถูกต้องfoldr
ตามที่เขียนไว้ในคำถามของคุณ ในฐานะที่เป็นความแตกต่างระหว่างการใช้งานที่มีการทำตามคำสั่งขององค์ประกอบที่พยายามออกมาเป็นหนังสือที่ไม่ใช่การสับเปลี่ยนได้อย่างง่ายดายนำไปสู่กรณีที่ล้มเหลวในขณะที่คุณได้พบ
ในคำถามย่อย QuickCheck ฉันเลื่อนไปที่คำตอบของ DDub .
ดังที่คุณได้อนุมานแล้วสาเหตุที่คุณได้รับความล้มเหลวเป็นเพราะการใช้งานทั้งสองแบบแยกกันได้ซึ่งคุณสามารถสังเกตได้โดยใช้โมโนนอยด์ที่ไม่สับเปลี่ยน
การรับฟังก์ชั่นที่ใช้โดย Quickcheck นั้นไม่ง่ายนัก ดูตัวอย่างเช่นคำถาม / คำตอบเกี่ยวกับShow
ฟังก์ชัน ing ที่สร้างโดยการตรวจสอบอย่างรวดเร็วเพื่อดูข้อมูลเพิ่มเติมเล็กน้อย
วิธีการที่จะได้รับShow
ฟังก์ชั่นที่สามารถจากคน QuickCheck คือการตัดฟังก์ชั่นในประเภท ที่กล่าวว่ารหัสที่คุณเรียก ( พบที่นี่ ) ใช้ฟังก์ชันโดยตรงดังนั้นจึงไม่สามารถแสดงได้ ทางเลือกหนึ่งที่คุณสามารถลองทำได้คือสร้างเวอร์ชันของฟังก์ชันของคุณเองโดยที่คุณใช้ประเภทแทนและเท่าที่จำเป็นเพื่อใช้ฟังก์ชันFunfoldable
Fun a b
a -> b
applyFun
ฉันเพิ่งรู้ว่าฉันใช้ Monoid สับเปลี่ยน ... ฉันสามารถสร้างความล้มเหลวขึ้นมาใหม่โดยใช้ Monoid ที่ไม่สับเปลี่ยน:
> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}
นี่คงเป็นกรณีง่ายๆ ฉันคิดว่าในรหัสการผลิตที่มีประเภทข้อมูลจริงสิ่งนี้อาจซับซ้อนกว่านี้มาก