CODEWITHSUNDEEP
haskell
Hennes
Hennes

Reputation: 1370

Merge list elements conditionally

I'm still a newbie to haskell, but I'm trying hard to learn it. But now I came to a point, where I think I have to learn a completely new chapter of haskell.

So this is an list of lists of Int containing these numbers:

[[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]]

In the beginning all inner lists contain three numbers. The goal is to merge all overlapping lists into bigger ones:

[[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]]
merging elements at index 0 and 3 because of the common 6 in both lists.
[[5,6,14,13],[1,2,9],[11,12,13],[5,13,14]]
merging elements at index 0 and 2 because of the common 13 in both lists.
[[5,6,14,13,11,12],[1,2,9],[5,13,14]]
merging elements at index 0 and 2 because of the common 5,13 & 14 in both lists.
[[5,6,14,13,11,12],[1,2,9]]

And this should be the result of the function. The order of the lists inside the list is as irrelevant as the order of elements inside the innermost lists.

I know how to code this in any other imperative language, but here I'm stuck.

Upvotes: 0

Views: 1289

Answers (1)

Sibi
Sibi

Reputation: 48654

One way to do this using List data structure would be like as follows. Initially write a predicate function for finding out if two list has any common elements between them:

hasCommon :: Eq a => [a] -> [a] -> Bool
hasCommon xs ys = not . null $ intersect xs ys

λ> hasCommon [1,2,3] [3]
True
λ> hasCommon [1,2,3] [4]
False

Now, you can implement a solve function which will give you your desired functionality:

solve :: Eq a => [[a]] -> [[a]]
solve xs = case xs' of
             [] -> []
             x'@(x:[]) -> x'
             x'@(x1:x2:[]) -> x'
             x'@(x1:x2:xs) -> x1:(solve (x2:xs))
    where xs' = aux (head xs) (tail xs) []
          aux :: Eq a => [a] -> [[a]] -> [[a]] -> [[a]]
          aux acc [] temp = (acc:temp)
          aux acc (y:ys) temp = if (acc `hasCommon` y)
                                then aux (union acc y) (ys ++ temp) []
                                else aux acc ys (y:temp)

The main part of the function is the aux. The function accepts three parameter. The first parameter for that function is the initial head of the input list which is used to compare it with the rest of the input list. The second parameter of the aux function is the tail of the input list. The third parameter is the temporary variable which you keep around to keep track of the elements which has been already processed. You handle two cases within the function: If the tail of the input list is empty, then you return [acc] ++ temp which will hold your result. That will be built up in the other case which will be described now. In the other case, you check if the head of the input list has any common elements with the head of the tail of the input list. If it has any common elements, then see how I'm passing around values to the aux function. Basically I populate the second input with ys ++ temp so that we traverse the already traversed elements. And the first parameter is the union of xs and y. The else part in that case is self-explanatory.

Demo in ghci:

λ> solve [[5,6,14],[1,2,9],[11,12,13],[6,13,14],[5,13,14]]
[[5,6,14,13,11,12],[1,2,9]]
λ> solve [[5,6,14],[18,19,20],[5,13,14],[1,2,9],[17,18,19],[20,21,22]]
[[5,6,14,13],[18,19,20,21,22,17],[1,2,9]]

Upvotes: 1

Related Questions