ocaml - 将'列表转换为集合？

Question

OCaml 没有将列表转换为集合的函数，这真的是真的吗？

如果是这种情况，是否可以制作通用函数list_to_set ?我试图在没有运气的情况下制作一个多态集。

Answer 1

基本问题:列表可以包含任何类型的元素。相反，集合(假设您的意思是标准库的 Set 模块)依靠元素比较操作来保持平衡树。您不能希望转换 t list如果您在 t 上没有比较操作，则设置为一组.

实际问题:Set标准库的模块是函数化的:它将代表元素类型及其比较操作的模块作为输入，并生成代表集合的模块作为输出。使用列表的简单参数多态性来完成这项工作有点运动。

为此，最简单的方法是将 set_of_list 函数包装在仿函数中，以便它本身由比较函数参数化。

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

然后，您可以使用例如 String 模块，它提供了一个合适的 compare功能。

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

也可以使用非仿函数化的集合的不同实现，例如电池和 Extlib 'PSet' 实现 ( documentation)。建议使用仿函数化设计，因为它具有更好的类型保证——您不能使用不同的比较操作混合相同元素类型的集合。

注意:当然，如果你已经有一个给定的 set 模块，从 Set.Make 仿函数实例化，你不需要这一切；但是你的转换函数不会是多态的。例如假设我有 StringSet我的代码中定义的模块:

module StringSet = Set.Make(String)

然后我可以写 stringset_of_list很容易，使用 StringSet.add和 StringSet.empty :

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

如果您不熟悉折叠，这里有一个直接的、非尾递归的递归版本:

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