f# Intersection of lists

I like to use the set operators http://msdn.microsoft.com/en-us/library/ee353629.aspx You can use Set.intersect (Set.ofList list1) (Set.ofList list2) |> Set.toList

The most direct way to fix your code is to write something like the code below.

In mem function, I just fixed the indentation and change it to use head and tail that you get from pattern matching rather than accessing them via list.Head and list.Tail (because doing that is more idiomatic and safer):

let rec mem list x = 
  match list with
  | [] -> false
  | head :: tail -> 
    if x = head then true else mem tail x 

In intersection, the trick is to use head::rest to build a resulting list when head is an element that appears in both lists (and rest is the list that you get by applying intersection to the tail recursively). You also do not need to match on list2 because mem handles empty lists fine:

let rec intersection list1 list2 = 
  match list1 with
  | head :: tail -> 
      let rest = intersection tail list2
      if mem list2 head then head::rest
      else rest
  | [] -> []

This is not super efficient (assuming n is the length of list1 and m is the length of list2, you may need up to m*n steps), but that's probably not the point. Also, intersection is not tail-recursive so it will not work on large lists, but that's another - more advanced - functional programming topic.

Finally, the code will also return list that may contain a single element multiple times - but I guess that's fine for you (e.g. intersection [1;1;1] [1] returns [1;1;1] but if you flip the arguments you'll get just [1])