标准ML:数据类型与结构

Question

我正在阅读Paulson的ML For the Working Programmer,对数据类型和结构之间的区别感到有点困惑.

在p.142,他定义了二叉树的类型如下:

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

这似乎是一个递归定义,其中'a表示某种固定类型.因此,每当我看到'a'时,它必须始终引用相同的类型.

在p.148,他讨论了二叉树的结构:

"...我们一直在关注一个想象中的ML会话,我们一次一个地输入树函数.现在我们应该将这些函数中最重要的函数收集到一个名为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定义中涉及的不同原语或复合类型.

但这是一个非常模糊的定义.有人想澄清一下吗？

谢谢你的帮助,bclayman

Answer 1

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

然而,ML模块比这更丰富.它们可以任意嵌套.还有仿函数,它们从模块到模块有效地起作用(如果需要,可以使用"参数化模块").总而言之,ML中的模块语言本身就形成了一个完整的功能语言,结构作为基本实体,基于它们的算符,以及描述这些模块"类型"的签名.这种小语言是所谓的核心语言之上的一层,其中存在普通的价值观和类型.

那么,回答你的个人问题:

1)数据类型和结构之间没有特定的关系.后者只使用前者.

2)struct- end只是一个关键字对来划分结构体(C传统中的语言可能会使用花括号).

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

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