Haskell: comportamiento sorprendente de "groupBy"

Question

Estoy intentando averiguar el comportamiento de la función de biblioteca groupBy (de Data.List), que pretende agrupar elementos de una lista mediante una función de "prueba de igualdad" pasada como el primer argumento El tipo de firma sugiere que la prueba de la igualdad sólo tiene que tener un 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 cambio yo esperaría carreras de números estrictamente creciente, como este:

[[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 estas 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 supone que la función dada (el primer argumento) prueba la igualdad, y asume que la función de comparación es reflexivo, transitivo y simétrico (ver equivalence relation). El problema aquí es que la relación menor que 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.

Puede esperar cierto comportamiento porque lo implementaría 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, sólo se puede ver en el primer elemento de cada uno, 1, 2 y 1.

1 > 2? ¡Sí! Entonces fusiona los primeros dos grupos.

1> 1? ¡No! Entonces deja el último grupo ser.

Y ahora se comparan todos los elementos para la igualdad.

... solo, no pasó el tipo de función que esperaba.

En resumen, when it wants an equality test, give it an equality test.

Answer 3

El problema es que la implementación de referencia de groupBy en el Informe Haskell compara elementos con el primer elemento, por lo que los grupos no aumentan estrictamente (solo tienen que ser todos mayores que el primer elemento). En su lugar, lo que desea es una versión de groupBy que pruebe elementos adyacentes, como la implementación here.