Haskell quickBatch: Thử nghiệm ZipList Monoid tại mconcat dẫn đến tình trạng tràn ngăn xếp

Question

tôi đã tạo các phiên bản mồ côi cho ZipList Semigroup và Monoid. Tuy nhiên, khi tôi chạy các bài kiểm tra từ quickBatch trên monoid, ở bài kiểm tra mconcat, có lỗi tràn ngăn xếp. Làm cách nào để giải quyết lỗi này? Tại sao lại có lỗi như vậy? Đó có phải là do pure mempty, điều mà tôi không hiểu lắm vì tôi nhận được điều này chủ yếu từ HaskellBook Chương 17 Phần ứng dụng 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

Answer 1

Đúng, lỗi là do pure mempty, nhưng không có nghĩa pure memptylà sai. Hãy nhìn vào đó trước.

Nó giúp ích rất nhiều cho việc xem xét các loại liên quan đến định nghĩa mempty = pure mempty:

mempty :: ZipList a
mempty = (pure :: a -> ZipList a) (mempty :: a)

Về cơ bản, chúng ta sẽ sử dụng các purehoạt động để tạo ra một ZipListra khỏi memptycác loại a. Từ đây sẽ giúp bạn xem xét định nghĩa của pureforZipList :

pure :: a -> ZipList a
pure x = ZipList (repeat x)

Tổng cộng, memptyfor ZipList asẽ là một ZipListchứa danh sách các memptygiá trị lặp lại vô hạn của kiểu cơ bản a.

---

Quay lại lỗi bạn đang gặp phải. Khi bạn cố gắng chạy thử nghiệm monoidtrên ZipList (Sum Int), QuickCheck đang xảy ra để kiểm tra một chuỗi các tài sản.

• Hai đầu tiên kiểm tra các thuộc tính nhận dạng bên trái và bên phải. Những gì chúng làm là tạo ra các giá trị của loại x :: ZipList (Sum Int)và xác minh điều đó x <> mempty = mempty <> x = x.
• Lần thứ ba kiểm tra xem đối với hai giá trị bất kỳ x, y :: ZipList (Sum Int), chúng tôi có x mappend đó y = x <> y.
• Lần thứ tư kiểm tra xem có bất kỳ danh sách giá trị nào không x :: [ZipList (Sum Int)], việc gấp các giá trị này mappendlại giống như nhập mconcatchúng.

Trước khi tiếp tục, điều quan trọng cần lưu ý là khi tôi nói "cho bất kỳ giá trị nào", ý tôi thực sự là QuickCheck đang sử dụng Arbitraryphiên bản của loại đã nói để tạo ra các giá trị của loại đó. Hơn nữa, Arbitraryinstance for ZipList acũng giống như Arbitraryinstance for [a]nhưng sau đó được bao bọc trong ZipList. Cuối cùng, Arbitraryví dụ for [a]sẽ không bao giờ tạo ra một danh sách vô hạn (vì chúng sẽ gây ra vấn đề khi bạn đang kiểm tra tính bình đẳng, như đi vào một vòng lặp vô hạn hoặc làm tràn ngăn xếp), vì vậy những kiểu "cho bất kỳ giá trị nào" ZipList (Sum Int)này sẽ không bao giờ là vô hạn hoặc.

Cụ thể, điều này có nghĩa là QuickCheck sẽ không bao giờ tự ý tạo giá trị mempty :: ZipList avì đây là danh sách vô hạn.

---

Vậy tại sao 3 cái đầu tiên vượt qua nhưng cái cuối cùng lại bị lỗi tràn ngăn xếp? Trong ba bài kiểm tra đầu tiên, chúng tôi không bao giờ kết thúc việc cố gắng so sánh một danh sách vô hạn với một danh sách vô hạn. Hãy xem tại sao không.

• Trong hai thử nghiệm đầu tiên, chúng tôi đang xem xét x <> mempty == xvà mempty <> x == x. Trong cả hai trường hợp, xlà một trong những giá trị "tùy ý" của chúng ta, sẽ không bao giờ là vô hạn, vì vậy đẳng thức này sẽ không bao giờ đi vào một vòng lặp vô hạn.
• Trong thử nghiệm thứ ba, chúng tôi đang tạo ra hai ZipLists hữu hạn xvà yvà mappending chúng lại với nhau. Không có gì về điều này sẽ là vô hạn.
• Trong trường hợp thứ ba, chúng tôi đang tạo một danh sách ZipLists và mconcattạo ra danh sách. Nhưng, điều gì sẽ xảy ra nếu danh sách trống? Vâng, mconcat [] = memptyvà gấp một danh sách trống sẽ tạo ra mempty. Điều này có nghĩa là, nếu danh sách trống được tạo dưới dạng đầu vào tùy ý (điều này hoàn toàn có thể xảy ra), thì kiểm tra sẽ cố gắng xác nhận rằng một danh sách vô hạn bằng với một danh sách vô hạn khác, điều này sẽ luôn dẫn đến tràn ngăn xếp hoặc lỗ đen.

---

Làm thế nào bạn có thể sửa chữa điều này? Tôi có thể đưa ra hai phương pháp:

1. Bạn có thể xác định phiên bản của riêng mình EqPropcho ZipListđể nó chỉ so sánh bình đẳng trên một số tiền tố hữu hạn của danh sách. Điều này có thể liên quan đến việc tạo một trình bao bọc kiểu mới (có lẽ newtype MonZipList a = MonZipList (ZipList a)), tạo ra một loạt các trường hợp, và sau đó viết một bản sao EqPropbằng tay. Điều này có thể sẽ hiệu quả nhưng hơi không phù hợp.

2. Bạn có thể viết phiên bản của riêng mình bằng cách monoidsử dụng một phiên bản khác của bài kiểm tra thứ tư. Ví dụ: nếu bạn hạn chế nó để thử nghiệm chỉ sử dụng các danh sách không trống, thì bạn sẽ không gặp vấn đề gì. Để làm điều này, bạn nên bắt đầu bằng cách xem định nghĩa của các monoidbài kiểm tra thuộc tính . Lưu ý rằng nó hiện định nghĩa thuộc tính "mconcat" là property mconcatPnơi

mconcatP :: [a] -> Property
mconcatP as = mconcat as =-= foldr mappend mempty as

Sử dụng NonEmptyListlớp riêng của QuickCheck , bạn có thể viết lại lớp này cho các mục đích của mình như:

mconcatP :: NonEmptyList a -> Property
mconcatP (NonEmptyList as) = mconcat as =-= foldr mappend mempty as

Rõ ràng, đây là một tình trạng yếu hơn một chút, nhưng ít nhất nó là một trong những điều kiện sẽ không bị treo.