Intersection between two lists F#

Question

I am looking for a function that takes the intersection between two lists and creates a new list, I have this function: let intersect x y = Set.intersect (Set.ofList x) (Set.ofList y) that do what I ant but I dont want to use any of the inbuilt functions in F#

Answer 1

It is best to use the library stuff, but if you can't

If we assume that the input lists are sorted (use List.sort or write your own) :

let rec intersect a b =
    match a with
    |h::t -> match b with
             |h2::t2 -> 
                 if h=h2 then h::(intersect t t2)
                 else if h>h2 then intersect t b else intersect a t2
             |[] -> []
    |[] -> []

Answer 2

I agree that converting lists to sets is not good in this case.

Here is another alternative that works without conversion to sets but uses the inbuilt Enumerable.Intersect function:

open System.Linq

let intersect (xs:'a seq) (ys: 'a seq) = xs.Intersect(ys)

You can call this function with FSharpList.