Haskell: sorprendente il comportamento di “groupBy”

Question

Sto cercando di capire il comportamento della funzione di libreria groupBy (da Data.List), che pretende di raggruppare gli elementi di una lista da una funzione di "test di uguaglianza" passato come 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, in questo modo:

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

Che cosa mi manca?

Answer 1

Dai un'occhiata al GHC implementazione di 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 questi 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) test per l'uguaglianza, e quindi si presuppone che la funzione di confronto è riflessiva , transitivo e simmetrica (vedi relazione di equivalenza ). Il problema qui è che il meno-che relazione non è riflessiva, non simmetrica.

---

Modifica : 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 po 'di comportamento, perché si sarebbe di implementare 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é conosce tutti gli elementi in ciascun gruppo è pari, si può semplicemente guardare il primo elemento in ciascuna, 1, 2 e 1.

1> 2? Sì! Così si fonde i primi due gruppi.

1> 1? No! Così lascia l'ultimo gruppo sia.

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

... solo, non hai superato così il tipo di funzione si aspettava.

In breve, quando vuole un test di uguaglianza, dare è un test di uguaglianza.

Answer 3

Il problema è che l'implementazione di riferimento di groupBy nella relazione Haskell confronta elementi contro il primo elemento, in modo che i gruppi non sono strettamente crescente (devono solo essere tutto più grande del primo elemento). Ciò che si vuole invece è una versione di groupBy che mette alla prova su elementi adiacenti, come l'attuazione qui .

Answer 4

Vorrei solo far notare che la funzione groupBy richiede anche la vostra lista per essere ordinati prima di essere applicate.

Ad esempio:

equalityOp :: (a, b1) -> (a, b2) -> Bool
equalityOp x y = fst x == fst y

testData = [(1, 2), (1, 4), (2, 3)]

correctAnswer = groupBy equalityOp testData == [[(1, 2), (1, 4)], [(2, 3)]]

otherTestData = [(1, 2), (2, 3), (1, 4)]

incorrectAnswer = groupBy equalityOp otherTestData == [[(1, 2)], [(2, 3)], [(1, 4)]]

Questo comportamento avviene perché groupBy sta usando arco nella sua definizione. Per ottenere un comportamento ragionevole che non si basa su di noi avendo la lista sottostante in un ordine particolare siamo in grado di definire una funzione:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' eq []     = []
groupBy' eq (x:xs) = (x:similarResults) : (groupBy' eq differentResults)
    where similarResults   = filter (eq x) xs
          differentResults = filter (not . eq x) xs