Convert 'a list to a Set?

Question

Is it really true that OCaml doesn't have a function which converts from a list to a set?

If that is the case, is it possible to make a generic function list_to_set? I've tried to make a polymorphic set without luck.

Answer 1

Ocaml 3.12 has extensions (7,13 Explicit naming of type variables and 7,14 First-class modules) that make it possible to instantiate and pass around modules for polymorphic values.

In this example, the make_set function returns a Set module for a given comparison function and the build_demo function constructs a set given a module and a list of values:

let make_set (type a) compare =
  let module Ord = struct
    type t = a
    let compare = compare
  end
  in (module Set.Make (Ord) : Set.S with type elt = a)

let build_demo (type a) set_module xs =
  let module S = (val set_module : Set.S with type elt = a) in
  let set = List.fold_right S.add xs S.empty in
    Printf.printf "%b\n" (S.cardinal set = List.length xs)

let demo (type a) xs = build_demo (make_set compare) xs

let _ = begin demo ['a', 'b', 'c']; demo [1, 2, 3]; end

This doesn't fully solve the problem, though, because the compiler doesn't allow the return value to have a type that depends on the module argument:

let list_to_set (type a) set_module xs =
  let module S = (val set_module : Set.S with type elt = a) in
    List.fold_right S.add xs S.empty

Error: This `let module' expression has type S.t
In this type, the locally bound module name S escapes its scope

A possible work-around is to return a collection of functions that operate on the hidden set value:

let list_to_add_mem_set (type a) set_module xs =
  let module S = (val set_module : Set.S with type elt = a) in
  let set = ref (List.fold_right S.add xs S.empty) in
  let add x = set := S.add x !set in
  let mem x = S.mem x !set in
    (add, mem)

Answer 2

Fundamental problem: Lists can contain elements of any types. Sets (assuming you mean the Set module of the standard library), in contrary, rely on a element comparison operation to remain balanced trees. You cannot hope to convert a t list to a set if you don't have a comparison operation on t.

Practical problem: the Set module of the standard library is functorized: it takes as input a module representing your element type and its comparison operation, and produces as output a module representing the set. Making this work with the simple parametric polymoprhism of lists is a bit sport.

To do this, the easiest way is to wrap your set_of_list function in a functor, so that it is itself parametrized by a comparison function.

module SetOfList (E : Set.OrderedType) = struct
  module S = Set.Make(E)
  let set_of_list li =
    List.fold_left (fun set elem -> S.add elem set) S.empty li
end

You can then use for example with the String module, which provides a suitable compare function.

  module SoL = SetOfList(String);;
  SoL.S.cardinal (SoL.set_of_list ["foo"; "bar"; "baz"]);; (* returns 3 *)

It is also possible to use different implementation of sets which are non-functorized, such as Batteries and Extlib 'PSet' implementation (documentation). The functorized design is advised because it has better typing guarantees -- you can't mix sets of the same element type using different comparison operations.

NB: of course, if you already have a given set module, instantiated form the Set.Make functor, you don't need all this; but you conversion function won't be polymorphic. For example assume I have the StringSet module defined in my code:

module StringSet = Set.Make(String)

Then I can write stringset_of_list easily, using StringSet.add and StringSet.empty:

let stringset_of_list li =
  List.fold_left (fun set elem -> StringSet.add elem set) StringSet.empty li

In case you're not familiar with folds, here is a direct, non tail-recursive recursive version:

let rec stringset_of_list = function
  | [] -> StringSet.empty
  | hd::tl -> StringSet.add hd (stringset_of_list tl)