CODEWITHSUNDEEP
ocaml
alwaysday1
alwaysday1

Reputation: 1783

OCaml: Removing duplicates from a list while maintaining order from the right

I just read this thread and find it interesting.

I implement the remove from the left function in a few minutes:

(*
 * remove duplicate from left:
 * 1 2 1 3 2 4 5 -> 1 2 3 4 5
 * *)
let rem_from_left lst =
  let rec is_member n mlst =
    match mlst with
    | [] -> false
    | h::tl ->
        begin
          if h=n then true
          else is_member n tl
        end
  in
  let rec loop lbuf rbuf =
    match rbuf with
    | [] -> lbuf
    | h::tl ->
        begin
          if is_member h lbuf then loop lbuf tl
          else loop (h::lbuf) rbuf
        end
  in
  List.rev (loop [] lst)

I know I could implement the is_member by Map or hashtable to make it faster, but in this moment that's not my concern.

In the case of implementing the remove from the right, I can implement it by List.rev:

(*
 * remove duplicate from right:
 * 1 2 1 3 2 4 5 -> 1 3 2 4 5
 * *)
let rem_from_right lst =
  List.rev (rem_from_left (List.rev lst))

I'm wondering if we can implement it in another way?

Upvotes: 5

Views: 18582

Answers (2)

Aadit M Shah
Aadit M Shah

Reputation: 74204

This is how I would implement remove_from_right:

let uniq_cons x xs = if List.mem x xs then xs else x :: xs

let remove_from_right xs = List.fold_right uniq_cons xs []

Similarly, you can implement remove_from_left as follows:

let cons_uniq xs x = if List.mem x xs then xs else x :: xs

let remove_from_left xs = List.rev (List.fold_left cons_uniq [] xs)

Both have their advantages and disadvantages:

  1. Although List.fold_left is tail recursive and takes constant space yet it folds the list in reverse order. Hence, you need to List.rev the result.
  2. Although List.fold_right doesn't need to be followed by a List.rev yet it takes linear space instead of constant space to produce the result.

Hope that helps.

Upvotes: 6

zw324
zw324

Reputation: 27190

Instead of accumulating the values on the way recursing to the end, you can collect the values on the way back up:

let rem_from_right lst =
  let rec is_member n mlst =
    match mlst with
    | [] -> false
    | h::tl ->
        begin
          if h=n then true
          else is_member n tl
        end
  in
  let rec loop lbuf =
    match lbuf with
    | [] -> []
    | h::tl ->
        begin
        let rbuf = loop tl
        in
          if is_member h rbuf then rbuf
          else h::rbuf
        end
  in
  loop lst

Upvotes: 0

Related Questions