F # Intersection 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 mem function takes a list and the var X as parameter and checks if the list contains the value X and returns true if it does, and false if it exists.

 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'm new to F #, and the problem I'm currently facing is not knowing how to build a list in (add a value to the list), and then add a value to it. I have not tested the code yet, since I need to complete this step first so as not to get errors, so I am not 100% sure how it works.

I am trying to cross 2 lists, I know that it exists for this "Set.Intersect list1 list2". The indentation is a bit strange, since I didn’t want to get to long lines, but you probably will understand anyway.

Answer 1

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

In the mem function, I just fixed the indentation and changed it to use head and tail , which you got from the pattern matching, and not to access them through list.Head and list.Tail (because it's more idiomatic and safe):

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

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

 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 this is probably not the case. In addition, intersection not tail recursive, so it won’t work on large lists, but this is another - more advanced - functional programming issue.

Finally, the code will also return a list that may contain one element several times - but I think this is good for you (for example, intersection [1;1;1] [1] returns [1;1;1] , but if you flip the arguments, you only get [1] )

Answer 2

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

Answer 3

To do this, you will need to track the list that is being created. The best way to do this is to define a helper function that takes a list created as a parameter and includes it in recursive calls

 let intersection list1 list2 = let rec inner list1 list2 builtList = match list1 with | head :: tail -> match list2 with | head :: tail -> if mem list2 list1.Head = true then inner tail list2 (list1.Head :: builtList) else inner tail list2 builtList | [] -> failwith "Second list is empty" | [] -> failwith "First list is empty" inner list1 list2 [] 

Another comment is that failure on an empty list is bad practice. Just treat the empty list as a list without elements, so intersection is not possible

 let intersection list1 list2 = let rec inner list1 list2 builtList = match list1 with | head :: tail -> if mem list2 list1.Head = true then inner tail list2 (list1.Head :: builtList) else inner tail list2 builtList | [] -> builtList inner list1 list2 [] 

This version works, but will return a list in which there are elements in the reverse order that they appear in list1 . To fix this, we can use the callback to create the list in the correct order.

 let intersection list1 list2 = let rec inner list1 list2 builder = match list1 with | head :: tail -> if mem list2 list1.Head = true then inner tail list2 (fun next -> list1.Head :: next) else inner tail list2 builder | [] -> (builder []) inner list1 list2 (fun x -> x) 

Answer 4

I was late for the party for 1000 years, but in case it would be difficult for someone with this question, the answer in the 1st comment did not work for me. But it's always my fault, I'm pretty new to F #. I came up with the following, which seems to work fine. Any comments on the improvement are welcome, as my code might be dumb.

ps. at the moment I do not want to use the built-in operators, since I do this for the class.

ps1. I do not want to use if , my professor prefers match (I know why)

 let rec intersect = function | ([],[]) -> [] | ([],_) -> [] | (_,[]) -> [] | (x::xtail,y::ytail) -> match x=y with | true -> x::intersect(xtail,ytail) | false -> intersect(xtail,y::ytail)