operator - haskell simbolos

¿Cómo agrupar elementos similares en una lista usando Haskell?

Question

Dada una lista de tuplas como esta:

dic = [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]

Cómo agrupar elementos de dic resultando en una lista grp donde,

grp  = [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]

De hecho, soy un recién llegado a Haskell ... y parece que me estoy enamorando de eso ...
Usando group o groupBy en Data.List solo agrupará elementos adyacentes similares en una lista. Escribí una función ineficiente para esto, pero da como resultado fallos de memoria ya que necesito procesar una lista de cadenas codificadas muy grande. Espero que me ayuden a encontrar una manera más eficiente.

Answer 1

1. Si la lista no está ordenada en el primer elemento, no creo que pueda hacerlo mejor que O (nlog (n)).

   • Una forma simple sería simplemente sort y luego usar cualquier cosa de la respuesta de la segunda parte.

   • Puede usar desde Data.Map un mapa como Map k [a] para usar el primer elemento de la tupla como clave y seguir agregando valores.

   • Puede escribir su propia función compleja, que incluso después de todos los intentos todavía tomará O (nlog (n)).

2. Si la lista está ordenada en el primer elemento, como es el caso en su ejemplo, entonces la tarea es trivial para algo como groupBy como se indica en la respuesta de @Mikhail o use foldr y hay muchas otras formas.

Un ejemplo del uso de foldr es aquí:

  grp :: Eq a => [(a,b)] -> [(a,[b])]
  grp = foldr f []
     where 
       f (z,s) [] = [(z,[s])] 
       f (z,s) a@((x,y):xs)  | x == z = (x,s:y):xs 
                             | otherwise = (z,[s]):a

Answer 2

Aquí está mi solución:

import Data.Function (on)
import Data.List (sortBy, groupBy)
import Data.Ord (comparing)

myGroup :: (Eq a, Ord a) => [(a, b)] -> [(a, [b])]
myGroup = map (/l -> (fst . head $ l, map snd l)) . groupBy ((==) `on` fst)
          . sortBy (comparing fst)

Esto funciona ordenando primero la lista con sortBy :

[(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]     
=> [(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")]

luego agrupando los elementos de la lista por la clave asociada con groupBy :

[(1,"aa"),(1,"bb"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg")] 
=> [[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]]

y luego transformar los elementos agrupados en tuplas con map :

[[(1,"aa"),(1,"bb"),(1,"cc")],[(2,"aa")],[(3,"ff"),(3,"gg")]] 
=> [(1,["aa","bb","cc"]), (2, ["aa"]), (3, ["ff","gg"])]`)

Pruebas:

> myGroup dic
[(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]

Answer 3

Siempre que sea posible, reutilice el código de la biblioteca.

import Data.Map
sortAndGroup assocs = fromListWith (++) [(k, [v]) | (k, v) <- assocs]

Pruébalo en ghci:

*Main> sortAndGroup [(1,"aa"),(1,"cc"),(2,"aa"),(3,"ff"),(3,"gg"),(1,"bb")]
fromList [(1,["bb","cc","aa"]),(2,["aa"]),(3,["gg","ff"])]

Answer 4

También puedes usar la extensión TransformListComp , por ejemplo:

Prelude> :set -XTransformListComp 
Prelude> import GHC.Exts (groupWith, the)
Prelude GHC.Exts> let dic = [ (1, "aa"), (1, "bb"), (1, "cc") , (2, "aa"), (3, "ff"), (3, "gg")]
Prelude GHC.Exts> [(the key, value) | (key, value) <- dic, then group by key using groupWith]
[(1,["aa","bb","cc"]),(2,["aa"]),(3,["ff","gg"])]

Answer 5

{-# LANGUAGE TransformListComp #-}

import GHC.Exts
import Data.List
import Data.Function (on)

process :: [(Integer, String)] -> [(Integer, [String])]
process list = [(the a, b) |  let info = [ (x, y) | (x, y) <- list, then    sortWith by y ], (a, b) <- info, then group by a using groupWith]