Ocaml 中记录内的容器

发布于 2025-01-02 00:29:16 字数 200 浏览 5 评论 0原文

我想到的数据结构涉及一个带有存储唯一字符串的成员的记录。抽象地说，这是我想要的记录：

struct A {
name: string;
neighbors: Set of String;
};

但我似乎无法在 Ocaml 中的记录内创建 Set 容器。鉴于 Set 是一个函子而不是传统类型，我不确定如何做到这一点。

原文

The data structure I have in mind involves a record with a member which stores unique strings.
Abstractly this is the record I have in mind:

struct A {
name: string;
neighbors: Set of String;
};

But I can't seem to create a Set container inside a record in Ocaml. Given that a Set is a functor and not a traditional type, I am not sure how this can be done.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

吃→可爱长大的 2025-01-09 00:29:16

Set 是一个函子，它为您想要的每种类型的集合实例化一个新类型；因为它需要知道比较函数，所以您不能像 string list 那样执行 string set （除非您使用 PSet，多态设置，来自附带的电池或extlib）。所以：

module StringSet = Set.Make(String);; (* or use BatSet.StringSet *)
type record = {
    name: string;
    neighbors: StringSet.t;
};

使用电池的多态集（要小心，因为它不会对您使用相同的比较函数进行类型检查）：

type record = {
    name: string;
    neighbors: string BatSet.t
};

Set is a functor that instantiates a new type for each type of set you want; since it needs to know the comparison function, you can't do string set like you can string list (unless you use PSet, the polymorphic set, from Batteries Included or extlib). So:

module StringSet = Set.Make(String);; (* or use BatSet.StringSet *)
type record = {
    name: string;
    neighbors: StringSet.t;
};

With Batteries' polymorphic sets (be careful with it, as it doesn't type-check that you're using the same comparison function):

type record = {
    name: string;
    neighbors: string BatSet.t
};

回复收藏 0 原文

ゝ偶尔ゞ 2025-01-09 00:29:16

例如，您需要了解“字符串列表”和您想要构建的“字符串集”之间的区别。

对于列表，类型是“列表”，因为您不需要了解列表的内容即可构建列表。对于集合，您需要 log(N) 时间访问，为此，您希望根据元素的顺序来组织集合。因此，您需要能够对它们进行比较。 OCaml 提供了一个默认的比较函数（Pervasives.compare），但该函数并不总是最好的：使用起来很昂贵（例如对于整数），并且它并不总是有效（它使用字典顺序）值的结构，这并不总是您想要的顺序）。

在 OCaml 中，当类型依赖于值时，即“集合”的情况，但也可能是“排序列表”的情况，您需要使用函子来定义类型，并应用函子获得新类型。

这就是这段代码为您做的事情：

模块 StringSet = Set.Make(String)

相当于：

module StringSet = Set.Make(struct
  type t = string
  let compare = compare
end)

其中“letcompare =compare”表示比较函数是默认函数（第二个compare指的是Pervasives.compare）。您可以直接使用“String”，因为 String 模块已经包含“type t = string”和“let Compare = Compare”。

You need to understand the difference between a "string list", for example, and the "string set" that you want to build.

For lists, the type is 'a list, because you need to know nothing about the content of the list to build the list. For a set, you want log(N) time access, and for that, you want to organize the set depending on the order of the elements. So, you need to be able to compare them. OCaml provides a default comparison function (Pervasives.compare), but that function is not always the best one : it is expensive to use (for integers for example), and it does not work all the time (it uses a lexicographical order on the structure of the value, that is not always the order you want).

In OCaml, when a type depends on a value, which is the case of the "set", but would also be the case of a "sorted list", you need to use a functor to define the type, and to apply the functor to get the new type.

That's what this code does for you:

module StringSet = Set.Make(String)

is equivalent to :

module StringSet = Set.Make(struct
  type t = string
  let compare = compare
end)

where "let compare = compare" means that the comparison function is the default one (the second compare refers to Pervasives.compare). You can use directly "String" instead, as the String modules already contains "type t = string" and "let compare = compare".

回复收藏 0 原文

~没有更多了~