remove duplicate string and empty string

Question

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

I have a list and I want to write a function that return a list without duplicate and empty string list. For example the undefined list above will return :

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

I write this function it return for me without duplicate but how can I add the condition with testing an empty string.

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

Thank you very much

Answer 1

You can use a set of already seen strings:

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

The first line define the type of set of strings.

Then, uniquify calls an auxiliary function to either add a never seen string to both the list and the set, or just discard the string. The acc is used to make the iteration tail recursive (and thus, avoid stack overflows on long lists).

Using this scheme is better since the complexity is in O(N.log N) instead of N².

Answer 2

Just pipe the result to List.filter (fun s -> s <> "") to remove the empty string afterwards. That's the simple, compositional way, yo u could also hack your function to drop it silently

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

Note that your function is quadratic, you can have better complexity by sorting the list first, or by converting to a set and back. Batteries has functions to do that for you.

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