CODEWITHSUNDEEP
ocaml
user13648242
user13648242

Reputation:

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?

Upvotes: -1

Views: 92

Answers (2)

Chris
Chris

Reputation: 36451

Note that your find_dup can be a little more terse without sacrificing clarity by using the short-circuiting nature of ||. You also want to avoid physical equality (==) as this will only work as expected in very few circumstances.

let rec find_dup a = function
  | [] -> false
  | hd::tl -> hd = a || find_dup a tl

We can see what glennsl is talking about if we trace out your example.

app [4; 5; 6; 7] [1; 2; 3; 4]
  find_dup 1 [4; 5; 6; 7] -> false
  1 :: app [2; 3; 4] [4; 5; 6; 7]
    find_dup 4 [2; 3; 4] -> true
    1 :: app [5; 6; 7] [2; 3; 4]
      find_dup 2 [5; 6; 7] -> false
      1 :: 2 :: app [3; 4] [5; 6; 7]
        find_dup 5 [3; 4] -> false
        1 :: 2 :: 5 :: app [6; 7] [3; 4]
          find_dup 3 [6; 7] -> false
          1 :: 2 :: 5 :: 3 :: app [4] [6; 7]
            find_dup 6 [4] -> false
            1 :: 2 :: 5 :: 3 :: 6 :: app [7] [4]
              find_dup 4 [7] -> false
              1 :: 2 :: 5 :: 3 :: 6 :: 4 :: app [] [7]
                find_dup 7 [] -> false
                1 :: 2 :: 5 :: 3 :: 6 :: 4 :: 7 :: app [] []
                  [1; 2; 5; 3; 6; 4; 7]

If we get rid of the reversal of lists:

let rec find_dup a lst =
  match lst with
  | [] -> false
  | hd::tl -> hd = a || find_dup a tl

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

Now:

app [4; 5; 6; 7] [1; 2; 3; 4]
  find_dup 4 [1; 2; 3; 4] -> true
  app [5; 6; 7] [1; 2; 3; 4]
    find_dup 5 [1; 2; 3; 4] -> false
    5 :: app [6; 7] [1; 2; 3; 4]
      find_dup 6 [1; 2; 3; 4] -> false
      5 :: 6 :: app [7] [1; 2; 3; 4]
        find_dup 7 [1; 2; 3; 4]
        5 :: 6 :: 7 :: app [] [1; 2; 3; 4]
          5 :: 6 :: 5 :: [1; 2; 3; 4]
          [5; 6; 7; 1; 2; 3; 4]

Of course, this is inefficient, as we have a loop (find_dup) within a loop (app) meaning this has quadratic runtime complexity. We can do better.

Let's just append both lists and then sort the whole. We'd get:

[1; 2; 3; 4; 4; 5; 6; 7]

The sorting is O(n * log n), and concatenating the lists is O(n). Removing duplicates them is an O(n) operation.

# let[@tail_mod_cons] rec uniq = function
    | ([] | [_]) as lst -> lst
    | a::(b::_ as tl) when a = b -> uniq tl
    | a :: tl -> a :: uniq tl;;
val uniq : 'a list -> 'a list = <fun>
# uniq [1; 2; 3; 4; 4; 5; 6; 7];;
- : int list = [1; 2; 3; 4; 5; 6; 7]

Upvotes: 0

glennsl
glennsl

Reputation: 29106

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.

Upvotes: 1

Related Questions