CODEWITHSUNDEEP
listhaskell
Heil
Heil

Reputation: 53

How to create a function that the input are two lists and the output are the elements that that are equal in the lists?

The elements just need to be equal. Each list cannot have repeated elements.

I tried this but somehow the function never hits "length (j:k) == 0 = intersect t (j:k)"

intersect _ [] = []
intersect (h:t) (j:k)
 |length (j:k) == 0 = intersect t (j:k)
 |h==j = h : intersect t k
 |otherwise =  intersect (h:t) k

What I'm trying to do is like "[1,2,3] [7,2,0] ======> [2]"

Upvotes: 1

Views: 127

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477170

length (j:k) is at least one, since you make a list that starts with j and k as a list of remaining elements.

In Haskell it is rare to work with length on a list, since it takes linear time to determine the length of a list, and for infinite lists, it gets stuck in an infinite loop.

You can work with an elem to check if an item is an element of a list, so you can work with:

intersect :: Eq a => [a] -> [a] -> [a]
intersect xs = filter (`elem` xs)

For two lists with lengths m and n, this will run in O(m×n), so it is better to work with a collection that can perform fast lookups. For example a HashSet of the unordered-containers package.

This will not work for intersections where the first list has infinite length. You can make a function that can yield intersections, even if both lists are infinite, I leave that as an exercise.

Upvotes: 2

Related Questions