Haskell: zaskakujące zachowanie "groupBy"

Question

Próbuję zrozumieć zachowanie biblioteki function groupBy (z Data.List), która służy do grupowania elementów listy za pomocą funkcji "testu równości" przekazywanej jako pierwszy argument. Podpis typ sugeruje, że test równości prostu musi mieć typ

(a -> a -> Bool) 

Jednak kiedy używam (<) jako „test równości” w GHCi 6.6, wyniki nie są, czego można oczekiwać:

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

Zamiast tego będę oczekiwać serie ściśle rosnącej liczby, na przykład:

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

Czego mi brakuje?

Answer 1

Wystarczy popatrzeć na ghc realizacji groupBy:

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

teraz porównać te dwa wyjścia:

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]] 

w skrócie, co się dzieje, jest to: groupBy zakłada, że ​​dana funkcja (pierwszy argument) sprawdza równość, a tym samym zakłada, że ​​funkcja porównawcza to reflexive, przechodnia i symetryczny (patrz equivalence relation). Problem polega na tym, że relacja o wartości mniejszej niż nie jest zwrotna ani symetryczna.

---

Edit: Poniższy realizacja zakłada tylko przechodniości:

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

fakt, że "<" nie jest testem równości.

Można oczekiwać pewnych zachowań, ponieważ można je inaczej wdrożyć, ale to nie jest to, co obiecuje.

Przykładem dlaczego co wyprowadza jest rozsądna odpowiedź brzmi, czy to wymiata przez to, robi

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

Teraz ma 3 grupy równych elementów. Więc to sprawdza, czy któryś z nich są w istocie takie same:

Ponieważ zna wszystkie elementy w każdej grupie jest równa, to może wystarczy spojrzeć na pierwszy element w każdym, 1, 2 i 1.

1 > 2? Tak! Więc łączy dwie pierwsze grupy.

1> 1? Nie! Pozostaje więc ostatnia grupa.

A teraz porównywano wszystkie elementy równości.

... tylko, nie przekazałeś jej funkcji, której oczekiwałeś.

W skrócie: when it wants an equality test, give it an equality test.

Answer 3

Problem polega na tym, że implementacja referencyjna groupBy w raporcie Haskella porównuje elementy z pierwszym elementem, więc grupy nie są ściśle rosnące (po prostu muszą być większe niż pierwszy element). Zamiast tego potrzebna jest wersja groupBy, która testuje na sąsiadujących elementach, takich jak implementacja here.