Haskell: sorprendente comportamiento de “GroupBy”

Question

Estoy tratando de averiguar el comportamiento de la función de la biblioteca GroupBy (de Data.List), que pretende agrupar elementos de una lista por una función de "prueba de igualdad" en el pasado como primer argumento. El tipo de firma sugiere que la prueba de la igualdad sólo necesita tener el tipo

(a -> a -> Bool)

Sin embargo, cuando se utiliza (<) como la "prueba de igualdad" en GHCi 6.6, los resultados no son lo que espero:

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

En su lugar yo esperaría carreras de números estrictamente creciente, como esto:

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

¿Qué me falta?

Answer 1

Tener un vistazo a la GHC implementación de GroupBy :

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

Ahora comparar estos dos salidas:

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

En resumen, lo que sucede es lo siguiente: groupBy asume que la función dada (el primer argumento) pruebas para la igualdad, y por lo tanto se supone que la función de comparación es reflexiva , transitiva y simétrica (ver de equivalencia relación ). El problema aquí es que el menor a relación no es reflexiva, ni simétrica.

---

Editar : La siguiente aplicación sólo se asume la transitividad:

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

El hecho de que "<" no es una prueba de la igualdad.

Se podría esperar que algunos comportamientos porque habías ponerlo en práctica de manera diferente, pero eso no es lo que promete.

Un ejemplo de por qué lo que da salida es una respuesta razonable es si se barre a través de él, haciendo

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

Ahora tiene 3 grupos de elementos iguales. Por lo tanto comprueba si alguno de ellos son de hecho el mismo:

Ya que conoce todos los elementos de cada grupo es igual, puede simplemente mirar el primer elemento en cada uno, 1, 2 y 1.

1> 2? ¡Si! Por lo tanto, combina los dos primeros grupos.

1> 1? ¡No! Así que deja ser el último grupo.

Y ahora se comparó todos los elementos para la igualdad.

... solamente, que no lo pasa el tipo de función que se esperaba.

En resumen, cuando se quiere una prueba de igualdad, dar que es una prueba de igualdad .

Answer 3

El problema es que la implementación de referencia de groupBy en el Informe Haskell compara elementos contra el primer elemento, por lo que los grupos no están aumentando en sentido estricto (sólo tienen que ser todo lo grande que el primer elemento). Lo que quiere en cambio, es una versión de groupBy que pone a prueba en elementos, como la implementación aquí .

Answer 4

sólo me gustaría señalar que la función GroupBy también requiere su lista para ser resuelto antes de ser aplicado.

Por ejemplo:

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

Este comportamiento se produce porque está utilizando GroupBy lapso en su definición. Para obtener un comportamiento razonable, que no depende de nosotros tener la lista que subyace en cualquier orden particular, podemos definir una función:

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