ocaml удалить дубликаты в списке

Question

Привет, ребята, у меня возникли небольшие проблемы. У меня есть общее представление о том, каким должен быть код, но я не знаю, что делать дальше.

Вопрос в том, чтобы определить функцию remove_elts, принимающую списокэлементы, а также список элементов, которые необходимо удалить из первого списка, и возврат списка со всеми вхождениями элементов, которые должны быть удалены, исчезли.

Мой код:

         let remove_elts l reml = 
           match l with
           [] -> false
           | hd :: tl -> if hd = l then reml
             else hd :: remove_elts l tl;;

Answer 1

Любая функция фильтрации, т. Е. Функция, которая принимает контейнер и возвращает другой контейнер, содержащий элементы входного контейнера, которые удовлетворяют некоторому свойству, реализуется с использованием следующего алгоритма:

output-sequence = []
foreach element in the input-sequeunce:
   if element satisfies condition:
      output-sequence := output-sequence + element

Эта итерация имеетдва элемента, которые отличаются с каждым шагом, переменная element, которая принимает в порядке элементы input-sequence, и выходная последовательность, которая увеличивается каждый раз, <element> удовлетворяет условию.

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

filter input-sequence output-sequence =
  if is-empty input-sequence then output-sequence
  else 
      let element = first-element-of input-sequence in
      let rest = drop-first-element input-sequence in
      if element satisfies condition 
      then filter rest (output-sequence + element)
      else filter rest output-sequence

Итерация называется

filter input-sequence []

Так что она немного более многословна, чем foreach, но этопотому что foreach - это, по сути, синтаксический сахар.

Теперь ваша задача - реализовать это в OCaml, имея в виду две вещи:

1) В OCaml вы можете использовать сопоставление с образцом,вместо is-empty, first-element-of и drop-first-element примитивов.

2) Вы используете односвязный список в качестве последовательности, поэтому добавление элемента в конец его очень дорого,это O (N) (так как вы должны пройти через все элементы, пока не дойдете до конца), и выполнение этого в цикле сделает ваш алгоритм O (N ^ 2), так что вместо этого вы должны перейти к началу (что являетсяO (1)) и в конце рекурсии переверните список.