F# Intersecting two lists

Question

So I want to intersect two sorted lists, such that intersect ([1;1;1;2;2], [1;1;2;4]) would return [1;1;2]. I've come this far:

let rec intersect (xs, xs') =
    match xs, xs' with
    | ([], [])             -> []
    | (x::tail, [])        -> []
    | ([], x'::tail')      -> []
    | (x::tail, x'::tail') -> if x = x' then x::intersect(tail, tail')
                              else intersect(tail, xs') 

But I'm not quite sure where to go from here. The function takes a tuple containing two lists, and I assume that when the head of each list is equal to each other, I start building up a new list, but I'm missing something that I can't quite figure out and hope to get a hint on.

EDIT: I'm aware I can use library functions to easily solve this, but that's no fun :)

Answer 1

Here's what I came up with:

let rec intersect xs ys =
    match xs, ys with
    | x::xs', y::ys' ->
        if   x = y then x :: intersect xs' ys'
        elif x < y then intersect xs' ys
        else            intersect xs  ys'
    | _ -> []

I removed the tupling of the arguments as I saw no reason for it.

x::xs' will only match with a non-empty list, so the base case match can be moved to the end and simplified to _.

I also changed the names. I find it's better to use the tick suffix only in names referring to the next iteration of an already existing value. In this case you have a list xs and its tail is xs'.

Answer 2

I suggest you rename your arguments to l1 and l2 and match against (x :: xs) and (y :: ys) i.e.

let rec intersect (l1, l2) =
    match l1,l2 with
    ...
    | (x :: xs), (y :: ys) when x < y -> 

The two cases you're missing are where the two heads are different i.e. x < y or x > y. If x < y then since the lists are sorted, there are one or more elements at the front of l2 which can be ignored since they cannot exist in l1 e.g. if

x = 5 and l2 = [1;2;4;5] then [1;2;4] can be discarded to find the next match.

I suggest you write a utility function which discards elements on the front of a list which cannot be found e.g.

//removes items from the front of l which cannot occur in a sorted list with head e
let rec skipUntil e l = ...

Once you have removed those elements you can continue the search.

The case where x > y is handled symmetrically.