Set Intersection with Tail Recursion

Question

I am trying to produce the solution for an intersection of two sets using tail recursion and an empty list [] as an accu:

let rec setintersect list list =
  let rec setintersect2 a b c = 
    match a with
      | [] -> (match b with [] -> (setsimplify c) | h::t -> (setsimplify c))
      | h1::t1 -> (match b with [] -> (setsimplify c) |h2::t2 -> (if (elementof h1 b) then (setintersect2 t1 b (c@[h1])) else (setintersect2 t1 b c)))  in
  setintersect2 list list [];;

Elementof takes takes "an int and a list" and is correctly working to give true if x is an element of the list, false otherwise..

Here is the problem:

# setintersect [5;2;1] [2;6;9];;
- : int list = [2; 6; 9]

and it should give [2].

What am I doing wrong? I feel like there's something really simple that I am misunderstanding!

Edit: Thanks for the responses so far.

setsimplify just removes the duplicates. so [2,2,3,5,6,6] becomes [2,3,5,6]. Tested and made sure it is working properly.

I am not supposed to use anything from the List library either. Also, I must use "tail recursion" with the accumulator being a list that I build as I go.

Here is the thought:

• Check the head element in list1, IF it exists in list2, THEN recurse with the "tail of list1, list2, and list c with that element added to it". ELSE, then recurse with "tail of list1, list2 and list c(as it is)".

• end conditions are either list1 or list2 are empty or both together are empty, return list c (as it is).

Answer 1

let rec setintersect list list = is wrong: the two arguments should be named differently (you should of course update the call to setintersect2 accordingly), otherwise the second will shadow the first. I would have thought that OCaml would have at least warned you about this fact, but it appears that it is not the case.

Apart from that, the code seems to do the trick. There are a couple of things that could be improved though:

• setintersect itself is not recursive (only setintersect2 is), you thus don't need the rec
• you should find a different name for the argument of setintersect2. In particular, it is not obvious which is the accumulator (acc or accu will be understood by most OCaml programmers in these circumstances).
• c@[h1] is inefficient: you will traverse c completely each time you append an element. It's better to do h1::c and reverse the result at the end
• As a bonus point, if you append element at the beginning of c, and assume that a is ordered, you don't have to call setsimplify at the end of the call: just check whether c is empty, and if this is not the case, append h1 only if it is not equal to the head of c.

Answer 2

First, You didn't list out your setsimplify function.

To write an ocaml function, try to split it first, and then combine if possible.

To solve this task, you just go through all elements in l1, and for every element, you check whether it is in l2 or not, right?

So definitely you need a function to check whether an element is in a list or not, right?

let make one:

let rec mem x = function
  | [] -> false
  | hd::tl -> hd = x || mem x tl

Then you can do your intersection:

let rec inter l1 l2 =
  match l1 with
    | [] -> []
    | hd::tl -> if mem hd l2 then hd::(inter tl l2) else inter tl l2

Note that the above function is not tail-recursive, I guess you can change it to tail-recursive as an excise.

---

If you use std library, then it is simple:

let intersection l1 l2 = List.filter (fun x -> List.mem x l2) l1