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

Question

我刚刚读了这个帖子，觉得很有趣。

我在几分钟内实现了从左侧删除函数：

(*
 * 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以使其更快，但此时这并非我的关注重点。

在实现从右侧删除时，我可以使用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))

我在想是否可以用另一种方式实现它？

- alwaysday1

Answer 1

这是我实现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)

两种方式各有优缺点：

1. List.fold_left虽然是尾递归，且占用的空间是常数级别，但它会以相反的顺序折叠列表。因此，你需要对结果进行List.rev。
2. List.fold_right虽然不需要跟随List.rev，但它占用的空间是线性的，而非常数级别，以生成结果。

希望这能帮到你。

- Aadit M Shah

---

这个算法的时间复杂度是多少？ - Yejus

Answer 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

- zw324

---

这似乎是一个非常复杂和低效的解决方案。为什么不从右到左遍历列表，而不是从左到右呢？ - Aadit M Shah

@AaditMShah: fold 明显更好，另一方面，这个答案更接近 OP 的需求，因此可能更具指导性，并且它表明了一些最小的改动就足以使程序正常运行。也给你点赞。 - zw324

嗯，is_member函数只是List.mem函数，而loop函数有点像List.fold_left函数。除非你想了解轮子的工作原理，否则没有必要重新发明轮子。 - Aadit M Shah

@AaditMShah 我同意，但我们的哲学似乎有所不同 - 在现实世界中，“折叠”肯定是正确的选择，但我宁愿让OP稍后发现这一点，而我认为向OP说明这种递归将会很棒。 - zw324