OCaml确实没有将列表转换为集合的功能吗?
如果是这种情况,是否可以创建通用函数list_to_set
?我试图制作一个多态集合而没有运气。
最诚挚的问候,Lasse Espeholt
基本问题:列表可以包含任何类型的元素。相反,集合(假设您的意思是标准库的Set模块)依赖于元素比较操作来保持平衡树。如果您没有对t list
进行比较操作,就不能希望将t
转换为集合。
实际问题:标准库的Set
模块是函数化的:它以表示元素类型及其比较操作的module作为输入,并产生表示集合的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'实现(documentation)。建议使用仿函数设计,因为它具有更好的键入保证-您不能使用不同的比较操作来混合相同元素类型的集合。
NB:当然,如果您已经有一个给定的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)
Ocaml 3.12具有扩展名(7,13 Explicit naming of type variables和7,14 First-class modules),使得可以实例化并传递模块以获取多态值。
在此示例中,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)
如果您不介意非常粗糙的方法,则可以使用多态哈希表界面。元素类型为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
如果只需要测试成员资格,这可能就足够了。如果您需要其他集合操作(例如联合和交叉),那么这不是一个很好的解决方案。从打字的角度来看,它绝对不是很优雅。
只需扩展原始类型,如图所示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;;
确定,这不是答案,而是后续操作... Set.Make返回的模块应该具有[of_list]函数(根据库引用...),但似乎不存在。有人知道为什么将其删除吗?无论如何,我去了:
List.fold_right ( add ) l empty
因为我不期望庞大的列表,而且我已经扩展了集合。
使用核心库,您可以执行以下操作:
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"]