Haskell: Comportamento surpreendente de "Groupby"

Question

Estou tentando descobrir o comportamento do grupo de funções da biblioteca (do data.list), que pretende agrupar elementos de uma lista por uma função de "teste de igualdade" passada como o primeiro argumento. A assinatura do tipo sugere que o teste de igualdade só precisa ter tipo

(a -> a -> Bool)

No entanto, quando eu uso (<) como o "teste de igualdade" no GHCI 6.6, os resultados não são o que eu espero:

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

Em vez disso, eu esperaria corridas de números estritamente crescentes, como este:

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

o que estou perdendo?

Answer 1

Dê uma olhada no GHC implementação de grupo:

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

Agora compare estas duas saídas:

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

Em suma, o que acontece é isso: groupBy pressupõe que a função dada (o primeiro argumento) testa a igualdade e, portanto, assume que a função de comparação é reflexivo, transitivo e simétrico (Vejo relação de equivalência). O problema aqui é que o Menor que A relação não é reflexiva, nem simétrica.

---

Editar: A implementação a seguir assume apenas a transitividade:

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

O fato de que "<" não é um teste de igualdade.

Você pode esperar algum comportamento, porque implementou de maneira diferente, mas não é o que ele promete.

Um exemplo de por que o que produz é uma resposta razoável é se ele varreu, fazendo

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

Agora tem 3 grupos de elementos iguais. Então, ele verifica se algum deles é de fato o mesmo:

Como sabe que todos os elementos de cada grupo são iguais, ele pode apenas olhar para o primeiro elemento em cada um, 1, 2 e 1.

1> 2? Sim! Por isso, mescla os dois primeiros grupos.

1> 1? Não! Então deixa o último grupo.

E agora é comparado a todos os elementos da igualdade.

... Só que você não passou pelo tipo de função que esperava.

Resumidamente, Quando quiser um teste de igualdade, faça um teste de igualdade.

Answer 3

O problema é que a implementação de referência de groupBy No relatório Haskell, compara elementos com o primeiro elemento, portanto os grupos não estão aumentando estritamente (eles precisam ser maiores que o primeiro elemento). O que você quer é uma versão de groupBy isso testa adjacente elementos, como a implementação aqui.

Answer 4

Eu gostaria de ressaltar que a função do grupo também exige que sua lista seja classificada antes de ser aplicada.

Por exemplo:

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

Esse comportamento ocorre porque o Groupby está usando o SPAN em sua definição. Para obter um comportamento razoável que não depende de termos a lista subjacente em qualquer ordem específica, podemos definir uma função:

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