Haskell quickBatch: การทดสอบ ZipList Monoid ที่ mconcat ส่งผลให้เกิดสแต็กล้น
ฉันได้สร้างอินสแตนซ์ orphaned สำหรับ ZipList Semigroup และ Monoid อย่างไรก็ตามเมื่อฉันเรียกใช้การทดสอบจาก QuickBatch บน monoid ที่การทดสอบ mconcat มีข้อผิดพลาดสแตกล้น ฉันจะแก้ไขข้อผิดพลาดนี้ได้อย่างไร เหตุใดจึงเกิดข้อผิดพลาดดังกล่าว เป็นเพราะอะไรpure mempty
ซึ่งฉันไม่ค่อยเข้าใจเท่าที่ฉันได้รับส่วนใหญ่มาจาก HaskellBook บทที่ 17 ส่วนการใช้งาน 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
คำตอบ
ใช่ข้อผิดพลาดเกิดจากpure mempty
แต่ไม่ได้หมายความว่าpure mempty
ผิด ลองดูที่นั่นก่อน
ช่วยได้มากในการดูประเภทที่เกี่ยวข้องกับคำจำกัดความmempty = pure mempty
:
mempty :: ZipList a
mempty = (pure :: a -> ZipList a) (mempty :: a)
โดยทั่วไปเราจะใช้pure
การดำเนินการเพื่อสร้างZipList
ออกจากประเภทmempty
a
จากที่นี่เพื่อดูคำจำกัดความของpureforZipList :
pure :: a -> ZipList a
pure x = ZipList (repeat x)
โดยรวมแล้วmempty
สำหรับการZipList a
เป็นไปได้ZipList
ที่มีรายชื่อซ้ำอนันต์ของค่าของชนิดพื้นฐานmempty
a
กลับไปที่ข้อผิดพลาดนี้ที่คุณได้รับ เมื่อคุณพยายามที่จะใช้ทดสอบmonoid
มากกว่าZipList (Sum Int)
, QuickCheck เป็นไปทดสอบลำดับของคุณสมบัติ
- สองตัวแรกตรวจสอบคุณสมบัติประจำตัวทางซ้ายและคุณสมบัติประจำตัวทางขวา ทำในสิ่งเหล่านี้คือการสร้างค่านิยมของประเภทและตรวจสอบว่า
x :: ZipList (Sum Int)
x <> mempty = mempty <> x = x
- ประการที่สามตรวจสอบว่าสำหรับสองค่าใด ๆ
x, y :: ZipList (Sum Int)
เรามีการx
แมปy = x <> y
นั้น - ตรวจสอบที่สี่ที่สำหรับรายการของค่าใด ๆ
x :: [ZipList (Sum Int)]
พับเหล่านี้ด้วยการmappend
เป็นเช่นเดียวกับmconcat
ไอเอ็นจีพวกเขา
ก่อนที่จะดำเนินการต่อสิ่งสำคัญมากที่จะต้องทราบว่าเมื่อฉันพูดว่า "สำหรับค่าใด ๆ " ฉันหมายความว่า QuickCheck กำลังใช้Arbitrary
อินสแตนซ์ของประเภทดังกล่าวเพื่อสร้างค่าประเภทนั้น นอกจากนี้Arbitrary
อินสแตนซ์สำหรับZipList a
ยังเหมือนกับArbitrary
อินสแตนซ์[a]
แต่ถูกรวมเข้าด้วยZipList
กัน สุดท้ายArbitrary
อินสแตนซ์สำหรับ[a]
จะไม่สร้างรายการที่ไม่มีที่สิ้นสุด (เพราะสิ่งเหล่านี้จะทำให้เกิดปัญหาเมื่อคุณกำลังตรวจสอบความเท่าเทียมกันเช่นการวนซ้ำไม่สิ้นสุดหรือล้นสแต็ก) ดังนั้น "สำหรับค่าใด ๆ " ประเภทZipList (Sum Int)
จะไม่มีที่สิ้นสุด ทั้ง.
โดยเฉพาะหมายความว่า QuickCheck จะไม่สร้างค่าโดยพลการmempty :: ZipList a
เนื่องจากเป็นรายการที่ไม่มีที่สิ้นสุด
แล้วทำไม 3 ครั้งแรกถึงผ่าน แต่อันสุดท้ายล้มเหลวด้วยสแต็กล้น? ในการทดสอบสามครั้งแรกเราไม่เคยพยายามเปรียบเทียบรายการที่ไม่มีที่สิ้นสุดกับรายการที่ไม่มีที่สิ้นสุด มาดูกันว่าทำไมไม่
- ในการทดสอบสองครั้งแรกที่เรากำลังมองหาที่และ
x <> mempty == x
mempty <> x == x
ในทั้งสองกรณีx
เป็นหนึ่งในค่า "ตามอำเภอใจ" ของเราซึ่งจะไม่มีที่สิ้นสุดดังนั้นความเท่าเทียมกันนี้จะไม่มีวันวนเวียนไม่สิ้นสุด - ในการทดสอบที่สามที่เรากำลังสร้างสอง ZipLists จำกัด
x
และy
และmappend
ไอเอ็นจีพวกเขาร่วมกัน ไม่มีอะไรเกี่ยวกับเรื่องนี้ที่จะไม่มีที่สิ้นสุด - ในกรณีที่สามเรากำลังสร้างรายการ ZipLists และ
mconcat
สร้างรายชื่อ แต่จะเกิดอะไรขึ้นถ้ารายการว่างเปล่า? ดีและพับรายการที่ว่างเปล่าผลิตmconcat [] = mempty
mempty
ซึ่งหมายความว่าหากรายการว่างถูกสร้างขึ้นเป็นอินพุตโดยพลการ (ซึ่งเป็นไปได้อย่างสมบูรณ์แบบ) การทดสอบจะพยายามยืนยันว่ารายการที่ไม่มีที่สิ้นสุดนั้นเท่ากับรายการที่ไม่มีที่สิ้นสุดอื่นซึ่งจะส่งผลให้เกิดสแต็กล้นหรือหลุมดำเสมอ
คุณจะแก้ไขปัญหานี้ได้อย่างไร? ฉันคิดได้สองวิธี:
คุณสามารถกำหนดเวอร์ชันของคุณเอง
EqProp
เพื่อZipList
ให้เปรียบเทียบความเท่าเทียมกับคำนำหน้า จำกัด ของรายการเท่านั้น สิ่งนี้น่าจะเกี่ยวข้องกับการสร้าง newtype wrapper (อาจnewtype MonZipList a = MonZipList (ZipList a)
) ได้รับอินสแตนซ์จำนวนมากจากนั้นเขียนEqProp
ทีละชิ้น สิ่งนี้อาจจะใช้ได้ แต่ก็ไม่โอ่อ่าเล็กน้อยคุณสามารถเขียนเวอร์ชันของคุณเองโดย
monoid
ใช้การทดสอบที่สี่เวอร์ชันอื่น ตัวอย่างเช่นหากคุณ จำกัด เพื่อให้การทดสอบใช้เฉพาะรายการที่ไม่ว่างเปล่าคุณก็จะไม่มีปัญหาใด ๆ การทำเช่นนี้คุณควรเริ่มต้นโดยดูที่ความหมายของmonoidการทดสอบคุณสมบัติ สังเกตว่าปัจจุบันกำหนดคุณสมบัติ "mconcat" ว่าproperty mconcatP
อยู่ที่ไหน
mconcatP :: [a] -> Property
mconcatP as = mconcat as =-= foldr mappend mempty as
ด้วยการใช้NonEmptyList
คลาสของ QuickCheck คุณสามารถเขียนสิ่งนี้ใหม่ตามวัตถุประสงค์ของคุณได้ดังนี้:
mconcatP :: NonEmptyList a -> Property
mconcatP (NonEmptyList as) = mconcat as =-= foldr mappend mempty as
เห็นได้ชัดว่านี่เป็นสภาพที่อ่อนแอกว่าเล็กน้อย แต่อย่างน้อยก็เป็นสภาพที่ไม่ห้อย