CODEWITHSUNDEEP
syntaxf#intersection
jboy12
jboy12

Reputation: 3916

intersection of sets in F#

In an attempt to understand one of the answers from this question. I edited the code to look like this however it only returns []

let rec intersect a b =
    let L1 = List.sort(a)
    let L2 = List.sort(b)
    match L1 with
    |h::t -> match L2 with
             |h2::t2 -> 
                 if h=h2 then h::(intersect t t2)
                 else if h>h2 then intersect t L2 else intersect L1 t2
             |[] -> []
    |[] -> [];;

intersect [1;2;3] [2;3;4]

What do I need to change to make it return a list (set) of intersecting values?

Upvotes: 3

Views: 1502

Answers (1)

mndrake
mndrake

Reputation: 100

The intersection of 2 lists can be found by using the Set type. Which is basically an immutable HashSet.

let a = [1;2;3]
let b = [2;3;4]
let intersect a b = Set.intersect (set a) (set b) |> Set.toList

Edit:

Shredderroy is correct that your logic is swapped between your else if & else condition. Also as an intro to F# recursion you shouldn't have a return like h::(intersect t t2) since this is not proper tail recursion and could lead to a stack overflow if the lists are long enough. The closest I could get to your original code with proper tail recursion is :

let intersect a b =
    let rec loopy L1 L2 acc =
        match L1 with
        |h::t -> 
            match L2 with
            |h2::t2 -> 
                if h=h2 then 
                    loopy t t2 (h::acc)
                elif h>h2 then 
                    loopy L1 t2 acc
                else 
                    loopy t L2 acc
                 |[] -> List.rev acc
        |[] -> List.rev acc
    loopy (List.sort a) (List.sort b) []

Upvotes: 3

Related Questions