删除重复的字符串和空字符串

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 2.

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) ""