从列表中删除重复项，同时维护右边的订单

Question

我只是阅读

这线并发现它很有趣。 i在几分钟内实现

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)

我知道我可以通过

is_member

或

Map

实施

hashtable

或

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

：

实施它。

remove_from_right

我想知道我们是否可以以另一种方式实施它？
    

这就是我将如何实施

Answer 1

：

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

都有其优势和缺点：

尽管是尾部递归，并且会持续空间，但它以相反的顺序折叠列表。因此，您需要

List.rev

结果。
1. 尽管不需要遵循一个

   List.fold_right

   List.rev

   ，但它需要线性空间而不是恒定空间来产生结果。
2. 希望有帮助

   即将累积的值累积到末端的途中，您可以在返回途中收集值：

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

l

和尾巴，并在每个尾巴上应用

h

。  不涉及逆转。

t

Answer 3