The haskell grouping problem

Question

group :: Ord a => [(a, [b])] -> [(a, [b])]

I want to look at all the pairs that have the same fst, and combine them by adding the entire list bs together, where they have the same a and drop the unprotected pair and so on ...

Reached:

group ((s, ls):(s', ls'):ps) = 
    if s == s' 
    then group ((s, ls++ls'):ps) 
    else (s, ls) : group ((s', ls'):ps)
group p = p

but obviously this is not going to cut him, because he does not group everything.

Edit: Example

[("a", as),("c", cs), ("c", cs3), ("b", bs),("c", cs2), ("b", bs2)]

displays

[("a", as),("c", cs++cs2++cs3),("b", bs++bs2)]

Answer 1

Two alternative barkmadley answer solutions :

• Tirpen , m . m barkmadley Data.List.partition - . O (n * m) . O (n log n) . ,

  import Data.List (groupBy, sortBy)
  combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
  combine = map mergeGroup . myGroup . mySort
    where
      mySort = sortBy (\a b -> compare (fst a) (fst b))
      myGroup = groupBy (\a b -> fst a == fst b)
      mergeGroup ((a, b):xs) = (a, b ++ concatMap snd xs)
  

  [("Dup",["2","3","1","5"]),("Non",["4"])] .

• Data.Map:

  import Data.Map (assocs, fromListWith)
  combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
  combine = assocs . fromListWith (++)
  

  [("Dup",["5","1","2","3"]),("Non",["4"])], . , :

  • , Data.List.reverse:

    import Data.List (reverse)
    import Data.Map (assocs, fromListWith)
    combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
    combine = assocs . fromListWith (++) . reverse
    

  • (flip (++)) append ((++)) ^{( barkmadley; )}

    import Data.Map (assocs, fromListWith)
    combine :: (Ord a) => [(a, [b])] -> [(a, [b])]
    combine = assocs . fromListWith (flip (++))
    

  combine [("Dup",["2","3","1","5"]),("Non",["4"])].

, combine , Ord. barkmadley , Eq. , , , .

Answer 2

import Data.List hiding (group)

group :: (Eq a) => [(a, [b])] -> [(a, [b])]
group ((s,l):rest) = (s, l ++ concatMap snd matches) : group nonmatches
    where
        (matches, nonmatches) = partition (\x-> fst x == s) rest
group x = x

:

group [("Dup", ["2", "3"]), ("Dup", ["1"]), ("Non", ["4"]), ("Dup", ["5"])]
    = [("Dup", ["2", "3", "1", "5"]), ("Non", ["4"])]

, , , , , . , , . , "" .

Answer 3

Another solution that uses the fold to accumulate groups on the map. Due to Map, this requires that it be aan instance Ord(BTW, your original definition requires that it be aan instance Eqthat barkmadley included in its solution).

import qualified Data.Map as M

group :: Ord a => [(a, [b])] -> [(a, [b])]
group = M.toList . foldr insert M.empty
  where
    insert (s, l) m = M.insertWith (++) s l m

If you're a big fan of obscurity, replace the last line:

    insert = uncurry $ M.insertWith (++)

This eliminates the unnecessary mand uncurrysplits the pair (s, l)into two arguments sand l.