将'列表转换为集合? [英] Convert 'a list to a Set?

问题描述

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

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

如果是这种情况，是否可以制作通用函数list_to_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.

推荐答案

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

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.

实际问题:标准库的Set模块是仿函数的:它以表示元素类型及其比较操作的 module 作为输入，并生成 module 代表集合.使用列表的简单参数多态性来进行这项工作有点麻烦.

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.

为此，最简单的方法是将set_of_list函数包装在函子中，这样它本身就可以由比较函数进行参数设置.

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

然后，您可以将其与例如String模块一起使用，该模块提供合适的compare函数.

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 *)

还可以使用非功能化的集合的不同实现，例如Batteries和Extlib'PSet'实现(

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.

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

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)

然后，我可以使用StringSet.add和StringSet.empty轻松编写stringset_of_list:

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)

这篇关于将'列表转换为集合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！