Ocaml: Removing Duplicates from a List While Maintaining Order from the Right

Question

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?

Accepted Answer

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:

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.
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.

Accepted Answer

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

Ocaml: Removing Duplicates from a List While Maintaining Order from the Right

2 Answers

Must Read

Your Answer

Robert Thorne

Ocaml: Removing Duplicates from a List While Maintaining Order from the Right

2 Answers

Must Read

Your Answer

Sign up or log in

Post as a guest

Robert Thorne