Intersection of infinite lists

Question

I know from computability theory that it is possible to take the intersection of two infinite lists, but I can't find a way to express it in Haskell.

The traditional method fails as soon as the second list is infinite, because you spend all your time checking it for a non-matching element in the first list.

Example:

let ones = 1 : ones -- an unending list of 1s
intersect [0,1] ones

This never yields 1, as it never stops checking ones for the element 0.

A successful method needs to ensure that each element of each list will be visited in finite time.

Probably, this will be by iterating through both lists, and spending approximately equal time checking all previously-visited elements in each list against each other.

If possible, I'd like to also have a way to ignore duplicates in the lists, as it is occasionally necessary, but this is not a requirement.

Answer 1

Using the universe package's Cartesian product operator we can write this one-liner:

import Data.Universe.Helpers

isect :: Eq a => [a] -> [a] -> [a]
xs `isect` ys = [x | (x, y) <- xs +*+ ys, x == y]
-- or this, which may do marginally less allocation
xs `isect` ys = foldr ($) [] $ cartesianProduct 
    (\x y -> if x == y then (x:) else id)
    xs ys

Try it in ghci:

> take 10 $ [0,2..] `isect` [0,3..]
[0,6,12,18,24,30,36,42,48,54]

This implementation will not produce any duplicates if the input lists don't have any; but if they do, you can tack on your favorite dup-remover either before or after calling isect. For example, with nub, you might write

> nub ([0,1] `isect` repeat 1)
[1

and then heat up your computer pretty good, since it can never be sure there might not be a 0 in that second list somewhere if it looks deep enough.

This approach is significantly faster than David Fletcher's, produces many fewer duplicates and produces new values much more quickly than Willem Van Onsem's, and doesn't assume the lists are sorted like freestyle's (but is consequently much slower on such lists than freestyle's).