haskell grouping problem

Question

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

I want to look up all pairs that have the same fst, and merge them, by appending all the list of bs together where they have the same a and discarding the unnessecary pair and so on...

I got as far as:

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 ain't going to cut it, because it doesn't group everything.

Edit: example

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

would output

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

Answer 1

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

this function produces the result:

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

it works by filtering the remaining bits into two camps, the bits that match and the bits that dont. it then combines the ones that match and recurses on the ones that don't. This effectly means you will have one tuple in the output list per 'key' in the input list.

Answer 2

Another solution, using a fold to accumulate the groups in a Map. Because of the Map this does require that a is an instance of Ord (BTW your original definition requires that a is an instance of Eq, which barkmadley has incorporated in his 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 with:

    insert = uncurry $ M.insertWith (++)

This omits the unnecessary m and uncurry breaks the (s, l) pair out into two arguments s and l.