CODEWITHSUNDEEP
listf#intersection
Bobson
Bobson

Reputation: 233

f# Intersection of lists

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.

Upvotes: 12

Views: 4567

Answers (4)

user4514782
user4514782

Reputation:

I am 1000 years late to the party, but in case anyone is having a hard time with this question, the answer in the 1st comment didn't work for me. But, that can always be my fault, I am fairly new to F#. I came up with the following that seems to work fine. Any comments on improvements are welcome, as my code may be goofy.

ps. at this point I don't want to use built-in operators, as I am doing this for a class.

ps1. I don't want to use if, my prof prefers match (idk why)

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

Upvotes: 0

Remko
Remko

Reputation: 764

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

Upvotes: 21

JaredPar
JaredPar

Reputation: 755307

In order to do this you are going to need to keep track of the list that is being built up. The best way to do this is to define a helper function that takes the list being built as a parameter and includes it in the 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 []

One other comment is that failing on an empty list is bad practice. Just treat the empty list as a list with no elements hence no intersection is 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 end up returning a list that has the elements in the reverse order that they appear in list1. To fix that we can use a callback to build up 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)

Upvotes: 1

Tomas Petricek
Tomas Petricek

Reputation: 243106

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

Upvotes: 8

Related Questions