structure - 标准 ML : Datatype vs. 结构

Question

我正在通读 Paulson 的ML For the Working Programmer，对数据类型和结构之间的区别有点困惑。

在第142，他为二叉树定义了一个类型如下:

datatype 'a tree = Lf
    | Br of 'a * 'a tree * 'a tree;

这似乎是一个递归定义，其中 'a 表示某种固定类型。因此，无论何时我看到 'a，它都必须指代相同的类型。

在第148，他讨论了二叉树的结构:

“...我们一直在关注一个假想的 ML session ，在该 session 中我们一次输入一个树函数。现在我们应该将这些函数中最重要的收集到一个结构中，称为 Tree。我们确实必须这样做，因为我们的一个函数 (size) 与内置函数冲突。使用结构的一个原因是为了防止此类名称冲突。

但是，我们将把 tree 的数据类型声明留在结构之外。如果它在内部，我们应该被迫通过 Tree.Lf 和 Tree.Br 来引用构造函数，这将使我们的模式不可读。因此，在续集中，假设我们做出了以下声明:

datatype 'a tree = Lf
    | Br of 'a * 'a tree * 'a tree;

structure Tree = 
    struct
    fun size Lf = 0
        | size (Br( v, t1, t2)) = 1 + size t1 + size t2;
    fun depth...
    etc...
    end;

我有点困惑。

1) 数据类型和结构之间的关系是什么？

2) “struct”在结构定义中的作用是什么？

3) 后来，保尔森讨论了字典的结构作为二叉搜索树。他执行以下操作:

structure Dict : DICTIONARY = 
    struct

    type key = string;
    type 'a t = (key * 'a) tree;
    val empty = Lf;

    <a bunch of functions for dictionaries>

这让我觉得 struct 指定了 Dict 定义中涉及的不同原始类型或复合类型。

虽然这是一个非常模糊的定义。有人想澄清一下吗？

感谢您的帮助，布莱曼

Answer 1

结构是一个模块。 struct 和 end 关键字之间的所有内容构成了该模块的主体。同样，您可以将签名视为抽象模块接口(interface) 的描述。将签名赋予结构(如 : DICTIONARY 语法在您的示例中所做的那样)将模块的 exports 限制为该签名中指定的内容(默认情况下，一切都会可访问)。这允许您隐藏模块的实现细节。

然而，ML 模块比这丰富得多。它们可以任意嵌套。还有 仿函数，它们是模块之间的有效函数(“参数化模块”，如果需要的话)。总而言之，ML 中的模块语言本身形成了一个完整的函数式语言，以结构作为基本实体、在它们之上的仿函数以及描述此类模块“类型”的签名。这种小语言是所谓的核心语言之上的一层，普通的值和类型存在于其中。

因此，回答您的个人问题:

1)数据类型和结构之间没有特定的关系。后者只是简单地使用了前者。

2) struct-end 只是一对关键字来分隔结构体(C 传统语言可能会在那里使用大括号)。

3) 如上所述，结构是一个基本模块。它可以包含(和导出)任意其他语言实体，包括其他模块。通过将定义组合在一起，并可能通过签名归属隐藏其中的一些定义，您可以表达命名空间和封装(特别是抽象数据类型)。

我还应该指出，保尔森的书关于模块的描述已经过时，因为它早于当前的语言版本。特别是，它没有描述如何通过模块来表达抽象数据类型，而是引入了将近 20 年没有人使用的过时的 abstype 声明。可以在 Harper 的 Programming in Standard ML 中找到对 ML 中模块化编程的更广泛和最新的介绍。 .