CODEWITHSUNDEEP
listduplicatesocaml
KLeeT
KLeeT

Reputation: 47

Ocaml: How can I delete all the duplicate element from list?

While learning Ocaml, I saw a code that removing duplicate elements from the list.

let rec remove =
function
  | []       -> []
  | x::[]    -> x::[]
  | x::y::tl ->
     if x=y then remove (y::tl)
     else x::remove (y::tl)

However, what I found is that this code only removes successive duplicates so if I try some duplicates that takes a place separately such as [6;6;8;9;4;2;5;1;5;2;3], the code deals with 6 which has successive duplicate but not with 2 or 5 which are separated.

How can I completely make the list have only unique elements? like remove [6;6;8;9;4;2;5;1;5;2;3] -> [6;8;9;4;2;5;1;3].

p.s. I managed to delete duplicate which comes first but cannot have figured out how to delete duplicates that come later.

Upvotes: 1

Views: 3463

Answers (3)

ice-wind
ice-wind

Reputation: 868

This question is pretty old but here is a solution that doesn't use sets, in case that's useful :

let rec remove_duplicates l =
  let rec contains l n =
    match l with
    | [] -> false
    | h :: t ->
      h = n || contains t n
  in
  match l with
  | [] -> []
  | h :: t ->
    let acc = remove_duplicates t in
    if contains acc h then acc else h :: acc
;;

Upvotes: 1

octachron
octachron

Reputation: 18892

From your description, you coded the quadratic version of the algorithm. There is also a O(n log n) version, using a set of already seen values:

let remove_duplicates (type a) (l: a list) =
  let module S = Set.Make(struct type t = a let compare = compare end) in
  let rec remove acc seen_set = function
      | [] -> List.rev acc
      | a :: rest when S.mem a seen_set -> remove acc seen_set rest
      | a :: rest -> remove (a::acc) (S.add a seen_set) rest in
  remove [] S.empty l

(the code above uses the polymorphic compare, you may want to provide a compare function argument in real code)

Upvotes: 2

KLeeT
KLeeT

Reputation: 47

I finally figured out. Without sorting, I made an element check and element remove functions, so I can check if the tail of the list has a duplicate of head and decide to append head and tail after deleting the duplicates in the tail. Making the main function as recursive it finally removes all duplicates without changing orders(and also preserves the first coming duplicate.) Thanks you, glennsl.

Upvotes: 0

Related Questions