functional-programming - 删除重复字符串和空字符串

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²。