Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

ocaml

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?

like image 862
hellotli Avatar asked Jun 04 '15 02:06

hellotli


People also ask

How do you remove duplicates from a list whilst preserving order?

If you want to preserve the order while you remove duplicate elements from List in Python, you can use the OrderedDict class from the collections module. More specifically, we can use OrderedDict. fromkeys(list) to obtain a dictionary having duplicate elements removed, while still maintaining order.

How will you remove duplicates without changing the order?

To remove duplicates from a Python list while preserving the order of the elements, use the code list(dict. fromkeys(list)) that goes through two phases: (1) Convert the list to a dict using the dict. fromkeys() function with the list elements as keys and None as dict values.

How do you remove duplicates from a list without changing the order in Java?

Iterate through array (via iterator, not foreach) and remove duplicates. Use set for find duplicates. Iterate through array and add all elements to LinkedHashSet, it isn't allows duplicates and keeps order of elements. Then clear array, iterate through set and add each element to array.


1 Answers

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.

like image 138
Aadit M Shah Avatar answered Nov 08 '22 12:11

Aadit M Shah