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

Question

dado una lista de tuplas como esto:

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

cómo agrupar artículos de DIC lo que resulta en una lista grp donde,

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

En realidad soy un recién llegado a Haskell. ..y parece que se está enamorando de él ..
Usando grupo o grupoBy en D ata.List solo agrupará elementos adyacentes similares en una lista. Escribí una función ineficiente para esto, pero resulta en fallas de memoria ya que necesito procesar una lista de cadenas codificadas muy grande. Espero que me ayudes a encontrar una forma más eficiente.

Answer 1

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 mediante la primera clasificación de 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")] 

continuación, la agrupación de los elementos de la lista de la tecla asociada a 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 t uples con map:

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

prueba:

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

Answer 2

1. Si la lista no está ordenada en el primer elemento, no creo que se puede hacer mejor que O (n log (n))

   • Una forma sencilla sería la de 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 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 así como GroupBy el que figura en la respuesta por @Mikhail o utilizar foldr y hay muchas otras maneras .

Un ejemplo del uso foldr está 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 3

También se puede usar TransformListComp extensión, 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 4

Siempre que sea posible, la reutilización de código biblioteca.

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

Pruébelo 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 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]