CODEWITHSUNDEEP
haskellfunctional-programming
dandycomp
dandycomp

Reputation: 33

Merge similar lists of lists in Haskell

I need to combine multiple lists with common elements to one. And i should do it inside list.

Eg:

INPUT: [[1,2,3], [5,6], [8,3,11], [4,9,1]]

MY output: [[1,2,3,8,3,11,1,2,3,4,9,1],[]]

Needed OUTPUT: [[1,2,3,8,11,9], [5,6]]

Another example:

INPUT: [[4],[0],[7,10],[6],[6]]

MY output: [[6,6],[]]

OUTPUT: [[4],[0],[7,10],[6]]

My code:

mergeAllLists :: [[Integer]] -> [[Integer]]
mergeAllLists (x:[]) = [x]
mergeAllLists (x:[]:y) = [x]
mergeAllLists (x:y:[]:_) = mergeOneToAll_ x [y]
mergeAllLists (x:xs) =  mergeAllLists (mergeOneToAll x xs)

mergeOneToAll :: [Integer] -> [[Integer]] -> [[Integer]]
mergeOneToAll _ [] = [[]]
mergeOneToAll list (y:list_of_list) = (mergeLists list y) : ( mergeOneToAll list list_of_list )

Upvotes: 2

Views: 97

Answers (1)

Will Sewell
Will Sewell

Reputation: 2643

mergeAllLists :: [[Integer]] -> [[Integer]]
mergeAllLists = foldl mergeOneToAll []

mergeOneToAll :: [[Integer]] -> [Integer] -> [[Integer]]
mergeOneToAll [] xs = [xs]
mergeOneToAll (as:acc) xs =
  if null $ intersect xs as then
    as : mergeOneToAll acc xs
  else
    (as ++ xs) : acc

It's not very efficient though (not tail recursive). Let me know if it needs to be more efficient and I will try and improve on it.

Upvotes: 2

Related Questions