Haskell: hành vi đáng ngạc nhiên của "groupBy"

Question

Tôi đang cố gắng tìm ra hành vi của nhóm chức năng thư việnBởi (từ Data.List), nhằm mục đích nhóm các phần tử của danh sách bằng chức năng "kiểm tra bình đẳng" được chuyển thành đối số đầu tiên. Các loại chữ ký cho thấy rằng các bài kiểm tra bình đẳng chỉ cần có loại

(a -> a -> Bool) 

Tuy nhiên, khi tôi sử dụng (<) là "thử nghiệm bình đẳng" trong GHCi 6.6, kết quả không phải là những gì tôi mong đợi:

ghci> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9] 
[[1,2,3,2,4],[1,5,9]] 

Thay vào đó tôi mong đợi chạy của số tăng đúng, như thế này:

[[1,2,3],[2,4],[1,5,9]] 

tôi thiếu gì?

Answer 1

Có một cái nhìn tại GHC thi hành groupBy:

groupBy     :: (a -> a -> Bool) -> [a] -> [[a]] 
groupBy _ []   = [] 
groupBy eq (x:xs)  = (x:ys) : groupBy eq zs 
          where (ys,zs) = span (eq x) xs 

Bây giờ so sánh hai kết quả đầu ra sau đây:

Prelude List> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9] 
[[1,2,3,2,4],[1,5,9]] 
Prelude List> groupBy (<) [8, 2, 3, 2, 4, 1, 5, 9] 
[[8],[2,3],[2,4],[1,5,9]] 

Nói tóm lại, những gì xảy ra đây là: groupBy giả định rằng các chức năng nhất định (đối số đầu tiên) thử nghiệm cho bình đẳng, và do đó giả định rằng các chức năng so sánh là reflexive, transitive và đối xứng (xem equivalence relation). Vấn đề ở đây là mối quan hệ ít hơn không phản xạ, cũng không đối xứng.

---

Sửa: Việc thực hiện sau đây chỉ giả transitivity:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]] 
groupBy' _ []      = [] 
groupBy' _ [x]      = [[x]] 
groupBy' cmp (x:xs@(x':_)) | cmp x x' = (x:y):ys 
          | otherwise = [x]:r 
    where r@(y:ys) = groupBy' cmp xs 

Answer 2

Thực tế là "<" không phải là một bài kiểm tra bình đẳng.

Bạn có thể mong đợi một số hành vi vì bạn thực hiện nó khác nhau, nhưng đó không phải là những gì nó hứa hẹn.

Một ví dụ về lý do tại sao những gì nó kết quả đầu ra là một câu trả lời hợp lý là nếu nó lướt qua nó, làm

[1, 2, 3, 2, 4, 1, 5, 9] -> 
[[1,2,3], [2,4], [1,5,9]] 

Bây giờ có 3 nhóm yếu tố bình đẳng. Vì vậy, nó sẽ kiểm tra nếu có trong số đó là trên thực tế giống nhau:

Kể từ khi nó biết tất cả các yếu tố trong mỗi nhóm được bình đẳng, nó chỉ có thể nhìn vào các yếu tố đầu tiên trong mỗi, 1, 2 và 1.

1 > 2? Vâng! Vì vậy, nó sáp nhập hai nhóm đầu tiên.

1> 1? Không! Vì vậy, nó rời nhóm cuối cùng được.

Và giờ đây, nó đã so sánh tất cả các phần tử cho sự bình đẳng.

... chỉ, bạn không vượt qua loại chức năng mong đợi.

Tóm lại, when it wants an equality test, give it an equality test.

Answer 3

Vấn đề là việc thực hiện tham chiếu groupBy trong Báo cáo Haskell so sánh các yếu tố với phần tử đầu tiên, vì vậy các nhóm không tăng nghiêm ngặt (chúng chỉ phải lớn hơn phần tử đầu tiên). Thay vào đó, điều bạn muốn là phiên bản của groupBy mà các thử nghiệm trên các thành phần liền kề, như việc triển khai here.