Haskell quickBatch: การทดสอบ ZipList Monoid ที่ mconcat ส่งผลให้เกิดสแต็กล้น

Jan 14 2021

ฉันได้สร้างอินสแตนซ์ 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

คำตอบ

1 DDub Jan 18 2021 at 01:54

ใช่ข้อผิดพลาดเกิดจาก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ที่มีรายชื่อซ้ำอนันต์ของค่าของชนิดพื้นฐานmemptya


กลับไปที่ข้อผิดพลาดนี้ที่คุณได้รับ เมื่อคุณพยายามที่จะใช้ทดสอบ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ซึ่งหมายความว่าหากรายการว่างถูกสร้างขึ้นเป็นอินพุตโดยพลการ (ซึ่งเป็นไปได้อย่างสมบูรณ์แบบ) การทดสอบจะพยายามยืนยันว่ารายการที่ไม่มีที่สิ้นสุดนั้นเท่ากับรายการที่ไม่มีที่สิ้นสุดอื่นซึ่งจะส่งผลให้เกิดสแต็กล้นหรือหลุมดำเสมอ

คุณจะแก้ไขปัญหานี้ได้อย่างไร? ฉันคิดได้สองวิธี:

  1. คุณสามารถกำหนดเวอร์ชันของคุณเองEqPropเพื่อZipListให้เปรียบเทียบความเท่าเทียมกับคำนำหน้า จำกัด ของรายการเท่านั้น สิ่งนี้น่าจะเกี่ยวข้องกับการสร้าง newtype wrapper (อาจnewtype MonZipList a = MonZipList (ZipList a)) ได้รับอินสแตนซ์จำนวนมากจากนั้นเขียนEqPropทีละชิ้น สิ่งนี้อาจจะใช้ได้ แต่ก็ไม่โอ่อ่าเล็กน้อย

  2. คุณสามารถเขียนเวอร์ชันของคุณเองโดย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

เห็นได้ชัดว่านี่เป็นสภาพที่อ่อนแอกว่าเล็กน้อย แต่อย่างน้อยก็เป็นสภาพที่ไม่ห้อย