How do I return a list of merged tuples?

user_10526607 0
Viewed 62

Currently I have a list of tuples [ (1 , [1]) , (2 , [1]) , (3 , [1]) , (1 , [2]) , (3 , [2]) , (1 , [3]) ]. I'd like to return a list of [ (1 , [1,2,3]) , (2 , [1]) , (3 , [1,2]) ].

I have written a merge method that merges two tuples.

merge :: Ord a => (a,[Int]) -> (a,[Int]) -> (a,[Int])
merge (x,y) (w,z) = (x, y ++ z )

And a method that checks if the first element of each tuple is equal.

isEqual :: Ord a => (a,[Int]) -> (a,[Int]) -> Bool
isEqual (x,y) (w,z)
  | x == w = True
  | otherwise = False

I'm having trouble coming up with a way to run the isEqual and merge methods on each element though to get to the answer. Would you guys recommend a fold or a recursive method? Thanks!

haskell
1 Answers

Generally, to solve this type of problem efficiently, you need to store the values in a map structure that can be easily accessed by the "key" on which you're matching. That way, when you run across (1, [2]), you can quickly consult the map, see that you already have (1, [1]), and combine them to get (1, [1,2]). Later, when you run across (1, [3]), you can quickly find (1, [1,2]) in the map and combine them to get (1, [1,2,3]), and so on...

For this specific problem, there's a short solution using facilities in Data.Map:

import qualified Data.Map.Strict as Map

gather :: (Ord a) => [(a, [Int])] -> [(a, [Int])]
gather = Map.toList . Map.fromListWith (++) . reverse

after which:

> gather [(1 , [1]) , (2 , [1]) , (3 , [1]) , (1 , [2]) , (3 , [2]) , (1 , [3])]
[(1,[1,2,3]),(2,[1]),(3,[1,2])]

Here, Map.fromListWith runs through a list of key-value pairs [(k,v)] and adds them, one by one, to a new map. As each pair is added, if the key isn't already in the map, the value (in your case, a singleton value like [1] or [2]) is added under that key. If the key is already in the map, the new value is combined with the old value using the supplied function (++) (i.e., as new_singleton_value ++ existing_list_of_values). This has the effect of creating a list of values in reverse order from the input list, so that's why I pre-processed the input list with reverse. (If the order doesn't matter, you should drop it.)

A more common variant of this problem is writing a function that takes a list of pairs:

[(1,1), (2,1), (3,1), (1,2), (3,2), (1,3)]

where the values aren't already lists. The solution is the same. You just pre-process the list with map (\(k,v) -> (k,[v]). This solution is covered in the other question mentioned in the comments.

user_72030160
Related