Find at least one item that exists in all three lists in OCaml

Question

We have three lists that contain the names of people.

All three lists are sorted alphabetically.

Now we need to find at least one name that appears in all three lists.

---

The algorithm I think of is as follows:

I get three chapters from three lists.

if the three heads are not equal to each other, I keep the maximum one and get two new chapters from the lists from which I just dropped the chapters.

Continue the procedure above until I find such an element as described in the beginning.

Is this algorithm correct?

---

The problem is that I'm not sure how to use ocaml to write a function .

Answer 1

The Thomash algorithm will do the job with two calls to intersect and create intermediate lists, so it is not very efficient.

Your algorithm is essentially correct. The extra bit is that sometimes you have two heads equal to max, and you should leave only the remaining head.

Here is the edited algorithm written in OCaml:

 let rec intersect xs ys zs = match xs, ys, zs with | [], _, _ | _, [], _ | _, _, [] -> None | x::xs', y::ys', z::zs' -> if x = y && y = z then Some x else let m = max x (max yz) in if x = m && y = m then intersect xs ys zs' else if x = m && z = m then intersect xs ys' zs else if y = m && z = m then intersect xs' ys zs else if x = m then intersect xs ys' zs' else if y = m then intersect xs' ys zs' else intersect xs' ys' zs 

Answer 2

Here is an OCaml function that crosses two sorted lists using your algorithm (which is really a good way to solve this problem).

 let rec intersect l1 l2 = match l1, l2 with | [], _ | _, [] -> [] | h1 :: t1, h2 :: t2 -> if h1 < h2 then intersect t1 l2 else if h1 = h2 then h1 :: (intersect t1 t2) else intersect l1 t2