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) 

Я знаю, что я мог бы реализовать 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)) 

Я интересно, если мы можем реализовать это по-другому?

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) 

Оба имеют свои преимущества и недостатки:

1. Хотя List.fold_left является хвостом рекурсивным и занимает постоянное пространство, он складывает список в обратном порядке. Следовательно, вам нужно получить результат List.rev.
2. Хотя List.fold_right не должен сопровождаться List.rev, но для получения результата требуется линейное пространство вместо постоянного пространства.

Надеюсь, что это поможет.