CODEWITHSUNDEEP
listhaskell
user2878641
user2878641

Reputation:

Joining lists in Haskell

So i've been praticing Haskell, and i was doing just fine, until i got stuck in this exercise. Basically i want a function that receives a list like this : 

xs = [("a","b"),("a","c"),("b","e")]

returns something like this :

xs = [("a",["b","c"]), ("b",["e"])].

I come up with this code:

list xs = [(a,[b])|(a,b) <- xs]

but the problem is that this doesn't do what i want. i guess it's close, but not right.

Here's what this returns:

xs = [("a",["b"]),("a",["c"]),("b",["e"])]

Upvotes: 3

Views: 938

Answers (3)

kqr
kqr

Reputation: 15028

The basic principle is that you want to group "similar" elements together.

Whenever you want to group elements together, you have the group functions in Data.List. In this case, you want to specify yourself what counts as similar, so you will need to use the groupBy version. Most functions in Data.List have a By-version that lets you specify more in detail what you want.

Step 1

In your case, you want to define "similarity" as "having the same first element". In Haskell, "having the same first element on a pair" means

(==) `on` fst

In other words, equality on the first element of a pair.

So to do the grouping, we supply that requirement to groupBy, like so:

groupBy ((==) `on` fst) xs

This will get us back, in your example, the two groups:

[[("a","b"),("a","c")]
,[("b","e")]]

Step 2

Now what remains is turning those lists into pairs. The basic principle behind that is, if we let

ys = [("a","b"),("a","c")]

as an example, to take the first element of the first pair, and then just smash the second element of all pairs together into a list. Taking the first element of the first pair is easy!

fst (head ys) == "a"

Taking all the second elements is fairly easy as well!

map snd ys == ["b", "c"]

Both of these operations together give us what we want.

(fst (head ys), map snd ys) == ("a", ["b", "c"])

Finished product

So if you want to, you can write your clumping function as

clump xs = (fst (head ys), map snd ys)
  where ys = groupBy ((==) `on` fst) xs

Upvotes: 1

jwodder
jwodder

Reputation: 57470

If you don't care about the order of the tuples in the final list, the most efficient way (that doesn't reinvent the wheel) would be to make use of the Map type from Data.Map in the containers package:

import Data.Map as Map

clump :: Ord a => [(a,b)] -> [(a, [b])]
clump xs = Map.toList $ Map.fromListWith (flip (++)) [(a, [b]) | (a,b) <- xs]

main = do print $ clump [("a","b"),("a","c"),("b","e")]

If you do care about the result order, you'll probably have to do something ugly and O(n^2) like this:

import Data.List (nub)

clump' :: Eq a => [(a,b)] -> [(a, [b])]
clump' xs = [(a, [b | (a', b) <- xs, a' == a]) | a <- nub $ map fst xs]

main = do print $ clump' [("a","b"),("a","c"),("b","e")]

Upvotes: 1

awesoon
awesoon

Reputation: 33661

You could use right fold with Data.Map.insertWith:

import Data.Map as M hiding (foldr)

main :: IO ()
main = print . M.toList
             $ foldr (\(k, v) m -> M.insertWith (++) k [v] m)
                     M.empty
                     [("a","b"),("a","c"),("b","e")]

Output:

./main
[("a",["b","c"]),("b",["e"])]

Upvotes: 1

Related Questions