ocaml

Combine two lists while removing duplicates


The goal is to combine (append) two lists while removing the duplicates.

let rec find_dup a lst =
  match lst with
    | [] -> false
    | hd::tl -> if (hd == a) then true else find_dup a tl;;

let rec app lst2 lst1 =
  match lst1 with
    | [] -> lst2
    | hd::tl -> if (find_dup hd lst2) then (app tl lst2)
     else hd::app tl lst2
     ;;

I have my code like this but when the test case is app [4;5;6;7] [1;2;3;4] the answer should be [1;2;3;4;5;6;7] but I keep getting

 - : int list = [1; 2; 5; 3; 6; 4; 7]

What is going on?


Solution

  • You're switching the lists around for every recursive call.

    Look at the argument order of the function definition:

    let rec app lst2 lst1
    

    and then the recursive function call:

    app tl lst2
    

    Also, just to nitpick, find_dup already exists in the standard library. It's called List.mem.