Как создать новый список в рекурсивной функции F #?

Question

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

Пока у меня есть этот код.

let newList = []
let rec filtered inputList = 
  match inputList with
    | [] -> []
    | h::t -> if List.contains h newList then filtered t else h::(filtered t)

Я знаю, что в своем утверждении else я не добавляю этот элемент в newList. Есть ли способ сделать несколько строк кода в операторе if при использовании оператора match? Как я могу это исправить?

Answer 1

У решения dee-see есть одно приятное свойство - хвостовая рекурсия. Это означает, что он может легко обрабатывать очень большие списки.

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

Это на самом деле очень близко к тому, что у вас есть. Логика, которую вам необходимо реализовать, заключается в следующем:

• , если в остальной части списка есть элемент, тогда мы пропускаем его
• , если элемент отсутствует в остальной части списка. список, мы добавляем его

Для этого вам не нужен newList. Вы можете просто проверить List.contains h t, поскольку это гарантирует, что вы будете возвращать только последнее вхождение каждого дублированного элемента:

let rec filtered inputList = 
  match inputList with
  | [] -> []
  | h::t -> if List.contains h t then filtered t else h::(filtered t)

filtered [1;2;3;2;3;4;5;4;1]

Единственное отличие от вашей функции заключается в условии. Решение от dee-see более сложное, но оно достигает того же результата. Как и в другом ответе, вы можете сделать это более элегантно, используя when:

let rec filtered inputList = 
  match inputList with
  | [] -> []
  | h::t when List.contains h t -> filtered t 
  | h::t -> h::(filtered t)

Answer 2

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

let distinct list =
    let rec filtered inputList outputList = 
      match inputList with
        | [] -> outputList
        | h::t -> if List.contains h outputList then (filtered t outputList) else (filtered t (h::outputList))

    filtered list []

printf "%A" (distinct [1; 2; 2; 3]) // [3; 2; 1]

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

Теперь это больше вопрос стиля, чем чего бы то ни было, но я также разбил бы разделивэто

let distinct list =
    let rec filtered inputList outputList = 
      match inputList with
        | [] -> outputList
        | h::t when List.contains h outputList -> filtered t outputList
        | h::t -> filtered t (h::outputList)

    filtered list []

printf "%A" (distinct [1; 2; 2; 3]) // [3; 2; 1]

Answer 3

Другой способ:

let rec distinct = function
    | []   -> []
    | h::t -> h :: distinct (List.filter ((<>) h) t)