Haskell equivalente al grupo de ScalaBy

Question

Scala tiene una función groupBy en listas que acepta una función para extraer claves de los elementos de la lista, y devuelve otra lista donde los elementos son tuplas que consisten en la clave y la lista de elementos que producen esa clave. En otras palabras, algo como esto:

List(1,2,3,4,5,6,7,8,9).groupBy(_ % 2)
// List((0, List(2,4,6,8)), (1, List(1,3,5,7,9)))

(En realidad, parece que en las versiones actuales proporciona un Map lugar, pero eso no es importante). C # tiene una versión aún más útil que le permite asignar los valores al mismo tiempo (muy útil si, por ejemplo, su función clave es simplemente extraer parte de una tupla).

Haskell tiene un groupBy , pero es algo diferente: agrupa series de cosas de acuerdo con alguna función de comparación.

Antes de ir y escribirlo, ¿hay un equivalente al grupo de Scala groupBy en Haskell? Hoogle no tiene nada de lo que yo esperaría que se viera la firma (a continuación), pero es posible que me haya equivocado.

Eq b => (a -> b) -> [a] -> [(b,[a])]

Answer 1

Específicamente, lo siguiente debería funcionar:

scalaGroupBy f = groupBy ((==) `on` f) . sortBy (comparing f)

Módulo: esto no le da el resultado de f en cada grupo, pero si realmente lo necesita, siempre puede postprocesar con

map (/xs -> (f (head xs), xs)) . scalaGroupBy f

Answer 2

Esta no es una función en la biblioteca de listas.

Puedes escribirlo como la composición de sortBy y groupBy.

Answer 3

Esta solución se romperá y se agrupará en (fx), independientemente de si está ordenada o no

f = (`mod` (2::Int))
list = [1,3,4,6,8,9] :: [Int]
myGroupBy :: Eq t => (b -> t) -> [b] -> [(t, [b])]
myGroupBy f (z:zs) = reverse $ foldl (g f) [(f z,[z])] zs
where
-- folding function
g f ((tx, xs):previous) y = if (tx == ty)
then (tx, y:xs):previous
else (ty, [y]):(tx, reverse xs):previous
where ty = f y
main = print $ myGroupBy f list

resultado: [(1, [1,3]), (0, [4,6,8]), (1, [9])]

Answer 4

Poner una trace en f revela que, con la solución @Niklas, f se evalúa 3 veces para cada elemento en cualquier lista de longitud 2 o más. Me tomé la libertad de modificarlo para que f se aplique a cada elemento solo una vez. Sin embargo, no está claro si el costo de crear y destruir las tuplas es menor que el costo de evaluar f varias veces (ya que f puede ser arbitrario).

import Control.Arrow ((&&&))
import Data.List
import Data.Function
myGroupBy'' :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]
myGroupBy'' f = map (fst . head &&& map snd)
. groupBy ((==) `on` fst)
. sortBy (compare `on` fst)
. map (f &&& id)

Answer 5

Puede escribir la función usted mismo con bastante facilidad, pero debe colocar una restricción Ord o Hashable en el resultado de la función clasificadora si desea una solución eficiente. Ejemplo:

import Control.Arrow ((&&&))
import Data.List
import Data.Function
myGroupBy :: (Ord b) => (a -> b) -> [a] -> [(b, [a])]
myGroupBy f = map (f . head &&& id)
. groupBy ((==) `on` f)
. sortBy (compare `on` f)
> myGroupBy (`mod` 2) [1..9]
[(0,[2,4,6,8]),(1,[1,3,5,7,9])] 

También puede usar un mapa hash como Data.HashMap.Strict lugar de ordenar el tiempo lineal esperado.