将“列表”转换为“集合”？

Question

OCaml 真的没有从列表转换为集合的函数吗？

如果是这样的话，是否可以制作一个通用函数list_to_set？我尝试制作一个多态集，但没有成功。

Answer 1

基本问题：列表可以包含任何类型的元素。集合（假设您指的是标准的 Set 模块相反，依赖元素比较操作来保持平衡树。如果您没有对 t 进行比较操作，则不能希望将 t 列表 转换为集合。

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

为此，最简单的方法是将 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' 实现 (文档）。建议使用函子化设计，因为它具有更好的类型保证——您不能使用不同的比较操作来混合相同元素类型的集合。

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

module StringSet = Set.Make(String)

然后我可以使用 StringSet.add 和 StringSet 轻松编写 stringset_of_list .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)

Answer 2

Ocaml 3.12 有扩展 (7,13 显式命名类型变量和7,14 一流模块)这使得实例化和传递多态值的模块成为可能。

在此示例中，make_set 函数为给定的比较函数返回一个 Set 模块，build_demo 函数根据给定的模块和列表构造一个集合值：

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

但这并不能完全解决问题，因为编译器不允许返回值具有依赖于模块参数的类型：

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

可能的解决方法是返回操作的函数集合隐藏设定值：

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 3

如果您不介意非常粗暴的方法，您可以使用多态哈希表接口。元素类型为unit的哈希表只是一个集合。

# let set_of_list l = 
      let res = Hashtbl.create (List.length l)
      in let () = List.iter (fun x -> Hashtbl.add res x ()) l
      in res;;
val set_of_list : 'a list -> ('a, unit) Hashtbl.t = <fun>
# let a = set_of_list [3;5;7];;
val a : (int, unit) Hashtbl.t = <abstr>
# let b = set_of_list ["yes";"no"];;
val b : (string, unit) Hashtbl.t = <abstr>
# Hashtbl.mem a 5;;
- : bool = true
# Hashtbl.mem a 6;;
- : bool = false
# Hashtbl.mem b "no";;
- : bool = true

如果您只需要测试成员资格，这可能就足够了。如果您想要其他集合操作（​​例如并集和交集），这不是一个很好的解决方案。从打字的角度来看，它绝对不是很优雅。

Answer 4

只需扩展原始类型即可，如图
http://www.ffconsultancy.com/ocaml/benefits/modules.html
对于列表模块：

module StringSet = Set.Make (* define basic type *)
  (struct
     type t = string
     let compare = Pervasives.compare
   end)
module StringSet = struct (* extend type with more operations *)
  include StringSet
  let of_list l =
    List.fold_left
      (fun s e -> StringSet.add e s)
      StringSet.empty l
end;;

Answer 5

使用核心库，您可以执行以下操作：

let list_to_set l = 
List.fold l ~init:(Set.empty ~comparator:Comparator.Poly.comparator)
~f:Set.add |> Set.to_list

例如：

list_to_set [4;6;3;6;3;4;3;8;2]
-> [2; 3; 4; 6; 8]

或者：

list_to_set ["d";"g";"d";"a"]
-> ["a"; "d"; "g"]