Ocaml: Как я могу удалить все повторяющиеся элементы из списка?

Question

Изучая Ocaml, я увидел код, удаляющий повторяющиеся элементы из списка.

let rec remove =
function
  | []       -> []
  | x::[]    -> x::[]
  | x::y::tl ->
     if x=y then remove (y::tl)
     else x::remove (y::tl)

Однако я обнаружил, что этот код удаляет только последовательные дубликаты, поэтому, если я попробую несколько дубликатов, требующихПоместите отдельно, например, [6; 6; 8; 9; 4; 2; 5; 1; 5; 2; 3], код имеет дело с 6, который имеет последовательный дубликат, но не с 2 или 5, которые разделены.

Как мне сделать так, чтобы в списке были только уникальные элементы? как удалить [6; 6; 8; 9; 4; 2; 5; 1; 5; 2; 3] -> [6; 8; 9; 4; 2; 5; 1; 3].

ps Мне удалось удалить дубликаты, которые идут первыми, но я не мог понять, как удалить дубликаты, которые появляются позже.

Answer 1

Из вашего описания вы закодировали квадратичную версию алгоритма. Существует также версия O (n log n), использующая набор уже просмотренных значений:

let remove_duplicates (type a) (l: a list) =
  let module S = Set.Make(struct type t = a let compare = compare end) in
  let rec remove acc seen_set = function
      | [] -> List.rev acc
      | a :: rest when S.mem a seen_set -> remove acc seen_set rest
      | a :: rest -> remove (a::acc) (S.add a seen_set) rest in
  remove [] S.empty l

(в приведенном выше коде используется полиморфное сравнение, вы можете указать аргумент функции сравнения в реальном коде). )

Answer 2

Я наконец разобрался. Без сортировки я сделал проверку элементов и удаление элементов, поэтому я могу проверить, есть ли в конце списка дубликат заголовка, и решить добавить заголовок и хвост после удаления дубликатов в хвосте. Делая основную функцию рекурсивной, она, наконец, удаляет все дубликаты без изменения порядка (а также сохраняет первый дубликат.) Спасибо, glennsl.