CODEWITHSUNDEEP
haskell
Madalina
Madalina

Reputation: 85

Intersection of List of lists Haskell

I must write a function that returns the intersaction of more than 2 lists

Ex: intersection[[1,5,3,11],[1,5,2,11],[5,3,2,11]] = [5, 11]
intersection:: (Eq a) => [[a]] -> [a]
intersection= undefined

I discovered that exists a function intersect :: Eq a => [a] -> [a] -> [a] ( but it's available only for 2 lists :)

Upvotes: 0

Views: 3908

Answers (3)

Eugene Sh.
Eugene Sh.

Reputation: 18299

Intersection of two sets is associative (and commutative, but it is less important here). I.e.:

intersect(A, B, C) = intersect(intersect(A,B), C) = intersect(A, intersect(B, C))

It means that it doesn't matter in which order you do the intersection operation, the result won't change.

So in Haskell you can utilize the foldl1 function to apply the intersect function over all of the list:

> import Data.List
> foldl1 intersect [[1,5,3,11],[1,5,2,11],[5,3,2,11]]
[5,11]

Upvotes: 3

castletheperson
castletheperson

Reputation: 33466

When you notice a function with the form a -> a -> a, you're possibly dealing with a function that can be used with a monoid, which means you can use folds.

In your case, there isn't really a reasonable output for intersection [], so you should use a fold function that requires a non-empty input list, such as foldr1.

Therefore, an easy implementation would be:

intersection:: (Eq a) => [[a]] -> [a]
intersection = foldr1 intersect

Upvotes: 4

user2184057
user2184057

Reputation: 964

Easy approach pro tip:

pro tip:

Intersection of 2 lists is obvious.

Intersection of 3 lists is intersection of 3rd list with intersection of first 2 lists.

So what do you have to do is to remember your current intersection result and intersect it with next list until you run out of lists or till your intersection will be empty.

Better approach in terms of complexity would be using merge sort like approach.

Where your threat lists like elements of list and instead of comprehension use intersect on elements and return an intersection of them.

Merge operation would be an intersection too.

It's been a long time since i had anything to do with Haskell so unfortunately I won't be able to provide you with code sample.

Upvotes: 1

Related Questions