เหตุใดการใช้งานนี้จึงเป็นตัวอย่างที่ไม่ดีของ Foldable Typeclass

Jan 02 2021

ผมทำงานที่ยอดเยี่ยมผ่าน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 ใช้อยู่

คำถาม:

  1. เหตุใดจึงเกิดความล้มเหลว
  2. มีวิธีรับฟังก์ชันที่ใช้ในการทดสอบโดย QuickCheck หรือไม่?

คำตอบ

4 duplode Jan 02 2021 at 06:30

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 .

3 DDub Jan 02 2021 at 05:40

ดังที่คุณได้อนุมานแล้วสาเหตุที่คุณได้รับความล้มเหลวเป็นเพราะการใช้งานทั้งสองแบบแยกกันได้ซึ่งคุณสามารถสังเกตได้โดยใช้โมโนนอยด์ที่ไม่สับเปลี่ยน


การรับฟังก์ชั่นที่ใช้โดย Quickcheck นั้นไม่ง่ายนัก ดูตัวอย่างเช่นคำถาม / คำตอบเกี่ยวกับShowฟังก์ชัน ing ที่สร้างโดยการตรวจสอบอย่างรวดเร็วเพื่อดูข้อมูลเพิ่มเติมเล็กน้อย

วิธีการที่จะได้รับShowฟังก์ชั่นที่สามารถจากคน QuickCheck คือการตัดฟังก์ชั่นในประเภท ที่กล่าวว่ารหัสที่คุณเรียก ( พบที่นี่ ) ใช้ฟังก์ชันโดยตรงดังนั้นจึงไม่สามารถแสดงได้ ทางเลือกหนึ่งที่คุณสามารถลองทำได้คือสร้างเวอร์ชันของฟังก์ชันของคุณเองโดยที่คุณใช้ประเภทแทนและเท่าที่จำเป็นเพื่อใช้ฟังก์ชันFunfoldableFun a ba -> bapplyFun

2 javinor Jan 02 2021 at 03:00

ฉันเพิ่งรู้ว่าฉันใช้ 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)})}

นี่คงเป็นกรณีง่ายๆ ฉันคิดว่าในรหัสการผลิตที่มีประเภทข้อมูลจริงสิ่งนี้อาจซับซ้อนกว่านี้มาก