Haskell: comportamento sorprendente di "groupBy"

Question

Sto cercando di capire il comportamento del gruppo di funzioni di libreriaBy (da DataList), che si propone di raggruppare gli elementi di una lista con una funzione di "test di uguaglianza" inoltrata come il primo argomento. La firma di tipo suggerisce che il test di uguaglianza solo bisogno di avere tipo

(a -> a -> Bool) 

Tuttavia, quando uso (<) come il "test di uguaglianza" in GHCi 6.6, i risultati non sono ciò che mi aspetto:

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

Invece mi aspetto piste di numeri strettamente crescente, come questo:

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

che cosa mi manca?

Answer 1

Avere uno sguardo alla ghc attuazione groupBy:

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

Ora confrontare queste due uscite:

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

In breve, ciò che accade è questo: groupBy presuppone che la funzione data (il primo argomento) verifica l'uguaglianza e quindi assume che la funzione di confronto sia riflessa, transitiva e simmetrico (vedere equivalence relation). Il problema qui è che la relazione inferiore a non è riflessa, né simmetrica.

---

Edit: La seguente implementazione assume solo transitività:

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

Il fatto che "<" non è un test di uguaglianza.

Ci si potrebbe aspettare un comportamento perché lo si implementerebbe in modo diverso, ma non è quello che promette.

Un esempio del perché ciò che in uscita è una risposta ragionevole è se spazza attraverso di essa, facendo

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

ora ha 3 gruppi di elementi uguali. Quindi controlla se qualcuno di loro sono in realtà lo stesso:

Poiché si conosce tutti gli elementi di ogni gruppo è uguale, può basta guardare il primo elemento in ciascuna, 1, 2 e 1.

1 > 2? Sì! Quindi unisce i primi due gruppi.

1> 1? No! Quindi lascia l'ultimo gruppo essere.

E ora viene confrontato tutti gli elementi per l'uguaglianza.

... solo, non hai passato il tipo di funzione che si aspettava.

In breve, when it wants an equality test, give it an equality test.

Answer 3

Il problema è che l'implementazione di riferimento di groupBy nel Report Haskell confronta gli elementi con il primo elemento, quindi i gruppi non sono strettamente in aumento (devono solo essere tutti più grandi del primo elemento). Quello che vuoi invece è una versione di groupBy test su adiacente a elementi, come l'implementazione here.