将列表转换为集合?

问题描述 投票:11回答:6

OCaml确实没有将列表转换为集合的功能吗?

如果是这种情况,是否可以创建通用函数list_to_set?我试图制作一个多态集合而没有运气。

最诚挚的问候,Lasse Espeholt

ocaml
6个回答
18
投票

基本问题:列表可以包含任何类型的元素。相反,集合(假设您的意思是标准库的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_listStringSet.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)

11
投票

Ocaml 3.12具有扩展名(7,13 Explicit naming of type variables7,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)

5
投票

如果您不介意非常粗糙的方法,则可以使用多态哈希表界面。元素类型为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

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


2
投票

只需扩展原始类型,如图所示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;;

0
投票

确定,这不是答案,而是后续操作... Set.Make返回的模块应该具有[of_list]函数(根据库引用...),但似乎不存在。有人知道为什么将其删除吗?无论如何,我去了:

List.fold_right ( add ) l empty

因为我不期望庞大的列表,而且我已经扩展了集合。


0
投票

使用核心库,您可以执行以下操作:

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"]
© www.soinside.com 2019 - 2024. All rights reserved.