I am using two lists as "sets" in Haskell, and I am supposed to find and return the intersection of the two lists. I have measures to remove the duplicates from the list however I cannot think of how to actually compare the lists and get another list that only contains the elements that are present in both the lists. Here is what I have so far

intersect :: [Integer] -> [Integer] -> [Integer]
intersect [] _ = []
intersect _ [] = []
intersect (x:xs) L2 = filter (\x -> x 'elem' L2) L2

However, this is incorrect, but logically I cannot exactly think of how to make this work. Any ideas and suggestions will be appreciated! Also, it would be better if someone has any idea that doesn't involve importing any other modules as I want to depend on only the functions in the prelude for this.

CodePudding user response：

You should use backtics to use a function as infix operator, so x `elem` L2. Furthermore you here use L2 twice (and since L2 starts with an uppercase, the compiler will think that L2 is a data constructor). You should filter one list with the items of the other list. Integer is a type and thus starts with an uppercase character.

If we thus fix the above problems, we obtain:

intersect :: [Integer] -> [Integer] -> [Integer]
intersect [] _ = []
intersect _ [] = []
intersect xs ys = filter (\x -> x `elem` xs) ys

or shorter:

intersect :: [Integer] -> [Integer] -> [Integer]
intersect [] _ = []
intersect xs = filter (`elem` xs)

These however will not work on if xs is an infinite list and there is at least one item of ys that is not eventually produced for the xs list. One can use diagonalization to eventually yield all items that occur in both lists. One can use the control-monad-omega package for this.