List matching in OCaml

Question

I have a function that I'm working on in Ocaml. It consists of a function that takes in two string lists and returns a string list. The function operates as follows. It scans each individual string in the first list and if it finds a corresponding match in the second list, it returns that match. If the second list has a duplicate match, the match would return twice. Here are test cases I've written that describe the expected behavior:

let test () : bool =
  (in_both [] ["Pearl"; "Steven"]) = []
;; run_test "in_both empty name list 1" test

let test () : bool =
  (in_both ["Pearl"; "Steven"] []) = []
;; run_test "in_both empty name list 2" test

let test () : bool =
  (in_both ["Pearl"; "Amethyst"; "Henry"] ["Pearl"; "Steven"]) = ["Pearl"]
;; run_test "in_both one repeat in both lists" test

let test () : bool =
  (in_both ["Pearl"; "Amethyst"; "Gary"; "Blair"] ["Pearl"; "Amethyst"; "Blair"]) 
  = ["Pearl";"Amethyst";"Blair"]
;; run_test "in_both three different repeats in both lists" test

let test () : bool =
  (in_both ["Garnet"; "Amethyst"; "Pearl"] ["Pearl"; "Pearl"]) 
  = ["Pearl";"Pearl"]
;; run_test "in_both two repeat in second list" test

Here is my function implementation:

let rec in_both (names1: string list) (names2: string list) : string list =
  begin match (names1, names2) with
  |([],[])-> []
  |([],hd2::tl2)-> []
  |(hd1::tl1,[])-> []
  |(hd1::tl1,hd2::tl2)->if contains_str names2 hd1 = true then hd1::in_both tl1 
  tl2 else in_both tl1 names2
  end

All of my tests pass except the last test, where it looks like "Pearl" does not print out twice when it should. What could I be doing wrong in my implementation? For reference, here is the function definition for the contains_str function that I called in in_both:

let rec contains_str (l: string list) (name: string) : bool =
  begin match l with
  |[]-> false
  |hd::tl-> hd = name || contains_str tl name
  end

Any help is appreciated!

Answer 1

One way to look at it is that contains_str is too weak to do what you want. You want to know how many times the string appears, not just whether it appears or not. You might consider a function that returns a list of the appearances of string a in string list b (empty if no appearances).

Also, here is another case your current code doesn't seem to handle properly:

# in_both ["a"; "b"] ["b"; "a"];;
- : string list = ["a"]

It seems to me there's no reason to move to the tail of the second list (tl2) just because hd1 has been found in it. It may be that the head of the second list appears later in the first list.