удалить дублирующую строку и пустую строку

Question

let undefined = ["string"; ""; "string"; "boolean";"";"innermost"]

У меня есть список, и я хочу написать функцию, которая возвращает список без дублирующегося и пустого списка строк.Например, приведенный выше список undefined вернет:

["string"; "boolean"; "innermost"]

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

let rec uniquify = function
| [] -> []
| x::xs -> x :: uniquify (List.filter ((<>) x) xs)

Большое спасибо

Answer 1

Вы можете использовать набор уже увиденных строк:

module StringSet = Set.Make(String)
let uniquify list =
  let rec iter acc set list =
    match list with
     | [] -> List.rev acc
     | s :: tail ->
       if StringSet.mem s set then
          iter acc set tail
       else
          iter (s :: acc) (StringSet.add s set) tail
  in
  iter [] StringSet.empty list

Первая строка определяет тип набора строк.

Затем uniquify вызывает вспомогательную функцию, чтобы либо добавить невидимую строку в список и набор, либо просто отбросить строку. acc используется, чтобы сделать хвост итерации рекурсивным (и, таким образом, избежать переполнения стека в длинных списках).

Использование этой схемы лучше, так как сложность в O (N.log N) вместо N².

Answer 2

Просто передайте результат в List.filter (fun s -> s <> ""), чтобы впоследствии удалить пустую строку. Это простой, композиционный способ, вы также можете взломать вашу функцию, чтобы молча отбросить ее

let rec uniquify = function
| [] -> []
| x::xs ->
  (if x = "" then [] else [x]) @ uniquify (List.filter ((<>) x) xs)

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

let do_stuff list =
  let open Batteries in
  List.remove (List.sort_unique String.compare list) ""