Tại sao việc triển khai này là một phiên bản xấu của Typeclass có thể gập lại?
Tôi đang làm việc thông qua Sách Haskell tuyệt vời . Ở cuối chương Có thể duyệt (21), tôi cần viết một ví dụ cho Cây sau:
data Tree a =
Empty
| Leaf a
| Node (Tree a) a (Tree a)
Đây là một liên kết đến mã đầy đủ của giải pháp của tôi. Các bài tập khuyến nghị cố gắng thực hiện cả hai foldMapvà foldr. Đây là cách tôi triển khai foldr(mà không cần suy nghĩ nhiều về thứ tự gọi):
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
Sau đó tôi thực hiện foldMapnhư sau:
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
Khi tôi chạy foldablelô thử nghiệm của QuickCheck , tôi gặp một số lỗi. Thay đổi cách foldrtriển khai của tôi thành như sau sẽ làm cho tất cả các thử nghiệm vượt qua:
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
Tôi đã thử tự chạy trường hợp thử nghiệm không thành công, nhưng không thể tạo lại lỗi:
*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}
Tôi nghi ngờ có điều gì đó mà tôi không tìm hiểu về foldchức năng ing mà QuickCheck đang sử dụng.
Câu hỏi:
- Tại sao lại xảy ra hỏng hóc?
- Có cách nào để lấy chức năng được sử dụng trong thử nghiệm bằng QuickCheck không?
Trả lời
foldrcó thể nhận được từ foldMap việc sử dụng Endomonoid , với a -> b -> bchức năng chuyển acác giá trị thành các b -> bhàm có thể được (một cách đơn lẻ) cấu thành. Đó là như vậy, nếu bạn foldMaplà ...
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node left x right) =
foldMap f left <> f x <> foldMap f right
... tương ứng foldrphải là:
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 (.)
Nếu chúng ta dọn dẹp nó một chút ...
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)
... chúng tôi nhận được định nghĩa chính xác foldrnhư được viết trong câu hỏi của bạn. Vì sự khác biệt giữa các triển khai có liên quan đến thứ tự thành phần, việc thử một đơn thức không giao hoán dễ dẫn đến trường hợp thất bại, như bạn đã tìm hiểu .
Trong câu hỏi phụ QuickCheck, tôi bỏ qua câu trả lời của DDub. .
Như bạn đã suy luận, lý do bạn gặp thất bại là vì hai cách triển khai này có thể phân biệt được, bạn có thể quan sát điều này bằng cách sử dụng một đơn nguyên không giao hoán.
Nhận được chức năng được sử dụng bởi quickcheck không đơn giản như vậy. Ví dụ, hãy xem câu hỏi / câu trả lời này về các Showhàm ing được tạo bởi kiểm tra nhanh để biết thêm một chút thông tin.
Cách để có được Showchức năng có thể ra khỏi QuickCheck là để bọc các chức năng trong các Funloại . Điều đó nói rằng, mã bạn đang gọi ( tìm thấy ở đây ) chỉ sử dụng trực tiếp các hàm, vì vậy chúng không bao giờ có thể được hiển thị. Một tùy chọn bạn có thể thử là tạo phiên bản foldablehàm của riêng bạn, nơi bạn sử dụng kiểu Fun a bthay thế a -> bvà applyFunkhi cần thiết để áp dụng các hàm.
Tôi chỉ nhận ra rằng tôi đã sử dụng Monoid giao hoán ... Tôi có thể tạo lại lỗi bằng cách sử dụng Monoid không giao hoán:
> ftree = fmap (First . Just) tree
> foldr (<>) mempty ft
First {getFirst = Just (-2)}
> foldMap (First . Just) ft
First {getFirst = Just (First {getFirst = Just (-5)})}
Đây có lẽ là một trường hợp đơn giản. Tôi tưởng tượng rằng trong mã sản xuất với các kiểu dữ liệu thực, điều này có thể phức tạp hơn nhiều.