f# Intersection of lists

Question

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

The function mem takes a list and a var X as parameter and checks if the list contains the value X and returns true if it does and false if it doesent.

let rec intersection list1 list2 = match list1 with
               | head :: tail -> match list2 with 
                     | head :: tail -> if mem list2 list1.Head = true 
                     then (*add the value to a list*) else intersection list1.Tail list2
               | [] -> failwith "Second list is empty"
       | [] -> failwith "First list is empty"

I am quite new to F# and the problem i am having right now is i dont know how to construct a list in the (add the value to a list) and then add the value to it. I havent tested the code yet since i need to complete this step first in order to not get errors so im not 100% sure on how it works.

I am trying to intersect 2 lists, I know that it does exists functions for this "Set.Intersect list1 list2". The indentation is a bit weird aswell here since i didnt want to get to long of rows but you will probably understand anyway.

Answer 1

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

Answer 2

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])