OCaml：在保持右侧顺序的同时从列表中删除重复项 [英] OCaml: Removing duplicates from a list while maintaining order from the right

问题描述

我刚读了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))

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

推荐答案

不是在递归到末尾的过程中累加值，而是可以在返回的过程中收集值：

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：在保持右侧顺序的同时从列表中删除重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！