OCaml：从列表中删除重复项，同时保持右侧的顺序

Question

我刚读 this thread 觉得很有趣。

我在几分钟内实现了remove from the left功能：

(*
 * 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)

我知道我可以通过 Map 或 hashtable 实现 is_member 以使其更快，但目前这不是我关心的问题。

在实现remove from the right的情况下，我可以通过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))

我想知道我们是否可以通过其他方式实现它？

Answer 1

您可以在递归的过程中收集值，而不是在递归到最后的过程中累加值：

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

Answer 2

这就是我要实现的方式 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 []

同样，你可以实现remove_from_left如下：

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)

两者各有优缺点：

虽然 List.fold_left 是尾递归的并且采用常量 space 但它会以相反的顺序折叠列表。因此，您需要 List.rev 结果。
虽然 List.fold_right 不需要后跟 List.rev 但它需要线性 space 而不是常量 space 来产生结果。

希望对您有所帮助。

OCaml：从列表中删除重复项，同时保持右侧的顺序

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

ocaml