How to group similar items in a list using Haskell

问题:

Given a list of tuples like this:

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

How to group items of dic resulting in a list grp where,

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

I'm actually a newcomer to Haskell...and seems to be falling in love with it..
Using group or groupBy in Data.List will only group similar adjacent items in a list. I wrote an inefficient function for this, but it results in memory failures as I need to process a very large coded string list. Hope you would help me find a more efficient way.

回答1:

Here's my solution:

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)

This works by first sorting the list with 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")]

then grouping the list elements by the associated key with 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")]]

and then transforming the grouped items to tuples with map:

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

Testing:

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

回答2:

Whenever possible, reuse library code.

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

Try it out in 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"])]

回答3:

Also you can use TransformListComp extension, for example:

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

回答4:

1. If the list is not sorted on the first element, I don't think you can do better than O(nlog(n)).

   • One simple way would be to just sort and then use anything from the answer of second part.

   • You can use from Data.Map a map like Map k [a] to use first element of tuple as key and keep on adding to the values.

   • You can write your own complex function, which even after you all the attempts will still take O(nlog(n)).

2. If list is sorted on the first element as is the case in your example, then the task is trivial for something like groupBy as given in the answer by @Mikhail or use foldr and there are numerous other ways.

An example of using foldr is here:

  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

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