这里对Section 2进行翻译。

课程主页：

https://www.coursera.org/learn/programming-languages/home

B站搬运：

https://www.bilibili.com/video/BV1dL411j7L7

Coursera编程语言课程第2节总结

标准说明：本总结涵盖的材料与课堂视频以及随视频发布的材料（幻灯片、代码）大致相同。它有助于以叙述的方式阅读材料，并将整个课程部分的材料放在一份文件中，特别是在以后复习材料时。请在讨论板上报告这些笔记中的错误。

构建新类型的概念性方法
记录：另一种处理”Each-of”类型的方法
按名称与按位置，法糖，以及关于元组的真相
数据类型绑定：我们自己的“One-of”类型
ML如何不提供对数据类型值的访问
ML如何提供对数据类型值的访问：Case表达式
有用的”One-of”类型的例子
到目前为止，数据类型绑定和Case表达式的精确介绍
类型同义词
Lists和Options是数据类型
多态数据类型
Each-of类型的模式匹配：关于变量绑定的真相
题外话：类型推理
题外话：多态类型和等价类型
嵌套模式
嵌套模式的有用例子
可选：函数绑定中的多种情况
异常
尾递归和累加器.
尾递归的更多例子
尾部位置的精确定义

构建新类型的概念性方法

编程语言有基本类型，如int、bool、unit和component类型，这些类型在其定义中包含其他类型。我们已经看到了在ML中生成复合类型的方法，即使用元组类型、列表类型和选项类型。我们将很快学习新的方法来创建更灵活的复合类型，并为我们的新类型命名。要创建复合类型，实际上只有三个基本构建块。任何像样的编程语言都以某种方式提供这些构建块：

“Each-of”：复合类型t描述了包含t1, t2, …,tn类型的每个值的值。
“One-of”：复合类型t描述了包含t1, t2, …,tn类型的某个值的值。
“Self-reference”：复合类型t可以在其定义中引用自身，以描述递归数据结构，如列表和树。

Each-of类型都是大多数程序员最熟悉的。元组就是一个例子：int * bool描述包含int和bool的值。带有字段的Java类也是一种类似的东西。

One-of类型也很常见，但不幸的是，在许多编程入门课程中，它们并没有得到太多强调。int option是一个简单的示例：此类型的值包含int或不包含。对于在ML中包含int或bool的类型，我们需要数据类型绑定，这是本节课程的主要重点。在像Java这样的类的面向对象语言中，有一种类型是通过子类化实现的，但这是本课程后面要讨论的主题。

Self-reference允许类型描述递归数据结构。这对于Each-of类型和One-of类型的组合都很有用。例如，int list描述的值要么不包含任何内容，要么包含一个int和另一个int list。任何编程语言中的整数列表都可以用or、and和self-reference来描述，因为这就是整数列表的含义。

当然，因为复合类型可以嵌套，所以我们可以对each-of、one-of和self-reference进行任何嵌套。例如，考虑类型(int * bool) list list * (int option) list * bool。

记录：“Each-of”类型的另一种方法

记录类型是“Each-of”类型，其中每个组件都是一个命名字段。例如，类型{foo: int，bar: int*bool，baz: bool*int}用三个名为foo，bar和baz的字段描述记录。这只是一种新的类型，就像元组类型在我们学习时是新的一样。

记录表达式生成记录值。例如，表达式{bar = (1+2, true andalso true)，foo = 3+4，baz = (false, 9)}将计算为记录值{bar = (1+2, true)，foo = 7，baz = (false, 9)}，它有类型{foo: int，bar: int*bool，baz: bool*int}，因为字段的顺序并不重要（我们使用字段名）。一般来说，记录表达式的语法是{f1 = e1, …, fn = en}，其中，一如既往，每个ei可以是任何表达式。在这里，每个f可以是任何字段名（尽管每个字段名必须不同）。字段名基本上是任何字母或数字序列。

在ML中，我们不需要声明我们想要一个具有特定字段名和字段类型的记录类型——我们只需要写下一个记录表达式，类型检查器就会为它提供正确的类型。记录表达式的类型检查规则并不奇怪：对每个表达式进行类型检查，以获得一些类型ti，然后构建具有所有正确字段和正确类型的记录类型。因为字段名的顺序并不重要，所以打印时REPL总是按字母顺序排列，以保持一致性。

记录表达式的求值规则类似：将每个表达式求值为一个值，并创建相应的记录值。

既然我们知道了如何建立记录值，我们需要一种方法来访问它们的片段。现在，我们将使用#foo e，其中foo是一个字段名。类型检查要求e具有一个名为foo的字段的记录类型，如果该字段具有类型t，那么这就是#foo e的类型。评估将e评估为一个记录值，然后生成foo字段的内容。

根据名称 vs 根据位置，语法糖和元组的真相

记录和元组非常相似。它们都是允许任意数量组件的“each-of”结构。唯一真正的区别是记录是“按名称”的，元组是“按位置”的。这意味着对于记录，我们通过使用字段名来构建它们并访问它们的片段，因此我们在记录表达式中写入字段的顺序并不重要。但是元组没有字段名，所以我们使用位置（第一，第二，第三，…）以区分组件。

在设计语言结构或选择使用哪种语言结构时，按名称与按位置是一个典型的决定，在某些情况下，两者都很方便。作为一个粗略的指南，对于少量的组件来说，按位置是比较简单的，但是对于较大的复合类型来说，它变得很难记住哪个位置是哪个。

Java方法参数（以及我们到目前为止所描述的ML函数参数）实际上采用了一种混合方法：方法体使用变量名来引用不同的参数，但调用方按位置传递参数。在其他语言中，调用者按名称传递参数。（短语“按名称调用”实际上意味着与函数参数有关的其他内容，这是另一个话题。）

尽管“按名称vs.按位置”，记录和元组仍然非常相似，我们可以完全根据记录来定义元组。以下是方法：

当你写(e1,…,en)时，这是另一种写{1=e1,...,n=en}的方法，也就是说，元组表达式是字段名为$1,2,\ldots,n$的记录表达式
t1 * ... * tn只是另一种写{1:t1,…,n:tn}的方式。
请注意，#1 e、#2 e等，现在已经表示正确的事情：获取名为1、2等的字段的内容。

事实上，ML就是这样定义元组的：元组就是一个记录。也就是说，元组的所有语法只是记录和使用记录的一种简便方式。REPL总是在可能的情况下使用元组语法，因此如果计算{2=1+2, 1=3+4}，它会将结果打印为(7,3)。使用元组语法是更好的风格，但我们不需要赋予元组自己的语义：我们可以使用上面的“另一种编写方式”规则，然后对记录重用语义。

这是我们将看到的许多语法糖例子中的第一个。我们说，“元组只是字段名为$1,2,\ldots,n$的记录的语法糖。”它是关于语法的，因为我们可以用等价的记录语法来描述元组的一切。它是糖，因为它使语言更甜。语法糖这个词被广泛使用。语法糖是一种很好的方法，可以使编程语言中的关键思想保持小（使其更易于实现），同时为程序员提供方便的编写方法。事实上，在家庭作业1中，我们使用元组时并不知道记录的存在，即使元组是记录。

数据类型绑定：我们自己的“One-of”类型

我们现在介绍数据类型绑定，这是继变量绑定和函数绑定之后的第三种绑定。我们从一个愚蠢但简单的例子开始，因为它将帮助我们了解数据类型绑定的许多不同方面。我们可以写：

datatype mytype = TwoInts of int * int
                | Str of string
			   | Pizza

粗略地说，这定义了一种新类型，其中值为int * int，字符串，或者什么都没有。任何值都会被信息“标记”，让我们知道它是哪种变体：这些“标记”，我们称之为构造函数，是TwoInts、Str和Pizza。可以使用两个构造函数标记相同类型的基本数据；事实上，这很常见，尽管我们的示例对每个变体使用不同的类型。

更准确地说，上面的示例向环境中添加了四件事：

一个新类型mytype，我们现在可以像任何其他类型一样使用它
三个构造函数TwoInts、Str和Pizza

一个构造函数是两个不同的东西。首先，它要么是一个用于创建新类型值的函数，要么实际上是一个新类型值。在我们的示例中，TwoInts是int * int -> mytype类型的函数，Str是string -> mytype类型的函数，Pizza是mytype类型的值。其次，我们在case表达式中使用构造函数，如下所述。

所以我们知道如何构建mytype类型的值：使用正确类型的表达式调用构造函数（它们是函数）（或者只使用Pizza值）。这些函数调用的结果是“知道它们是哪个变量”（它们存储一个“标记”）的值，并将底层数据传递给构造函数。REPL用例如TwoInts(3,4)或Str “hi”表示这些值。

剩下的就是找回piece的方法。

ML如何不提供对数据类型值的访问

给定mytype类型的值，我们如何访问其中存储的数据？首先，我们需要找出它是哪种变体，因为mytype类型的值可能是由TwoInts、Str或Pizza生成的，这会影响可用的数据。一旦我们知道我们有什么变体，我们就可以访问该变体携带的片段（如果有的话）。

回想一下我们是如何为列表和选项这样做的，它们也是一种类型：我们有用于测试我们拥有的变量（null或isSome）的函数，以及用于获取片段（hd、tl或valOf）的函数，如果使用错误的参数，这些函数会引发异常。

ML可以对数据类型绑定采用相同的方法。例如，它可以采用上面的数据类型定义，并向环境添加mytype -> bool类型的函数isTwoInts、isStr和isPizza。它还可以添加一些函数，比如mytype -> int*int类型的getTwoInts和mytype->string类型的getStr，这可能会引发异常。

但ML不采用这种方法。相反，它做得更好。你可以用更好的东西自己编写这些函数，尽管这样做通常不太合适。事实上，在学习了更好的东西之后，我们将不再像以前那样使用列表和选项的函数——我们只是从这些函数开始，以便我们可以一次学习一件事情。

ML如何提供对数据类型值的访问：Case表达式

更好的是case表达式。下面是我们的数据类型绑定示例的一个基本例子：

fun f x = (* f has type mytype -> int *) 
		case x of
        Pizza => 3
      | TwoInts(i1,i2) => i1 + i2
      | Str s => String.size s

在某种意义上，case表达式就像一个更强大的if-then-else表达式。就像条件表达式一样，它评估两个子表达式：首先是关键字case和of之间的表达式，其次是第一个分支中匹配的表达式。但是，我们可以为我们的数据类型的每个变体有一个分支，而不是有两个分支（一个为true，一个为false）（我们将在下面进一步概括）。与条件表达式一样，每个分支的表达式必须具有相同的类型（在上面的例子中是int），因为类型检查器无法知道将使用哪个分支。

每个分支都有p => e的形式，其中p是一个模式，e是一个表达式，我们用|字符来分隔这些分支。模式看起来像表达式，但不要把它们看成是表达式。相反，它们被用来与评估case的表达式（case后面的部分）的结果进行匹配。这就是为什么评估一个case表达式被称为模式匹配。

在本讲座中，我们保持模式匹配的简单性。每个模式都使用一个不同的构造函数，模式匹配会根据case后面的表达式挑选出”正确的”分支。评估该分支的结果就是总体答案；不评估其他分支。例如，如果 TwoInts(7,9)被传递给f，那么第二个分支将被选择。

这就解决了使用one-of类型的”检查变体”部分，但模式匹配也解决了”取出底层数据 “部分。由于TwoInts有两个”携带”的值，它的模式可以（而且现在必须）使用两个变量（(i1,i2)）。作为匹配的一部分，值的相应部分（继续我们的例子，7和9）被绑定到i1和i2的环境中，用来评估相应的右边（i1+i2）。在这个意义上，模式匹配就像一个let-表达式。它将变量绑定在一个局部范围内。类型检查器知道这些变量有什么类型，因为它们是在创建模式中使用的构造函数的数据类型绑定中指定的。

为什么在测试变体和提取片段时，case表达式比函数更好？

我们永远不会”搞砸”并试图从错误的变体中提取东西。也就是说，我们不会像使用hd []那样得到异常。
如果一个case表达式忘记了一个变体，那么类型检查器将给出一个警告信息。这表明评估case表达式找不到匹配的分支，在这种情况下它会引发一个异常。如果你没有这样的警告，那么你知道这种情况不会发生。
如果一个case表达式两次使用一个变体，那么类型检查器将给出一个错误信息，因为其中一个分支不可能被使用。
如果你还想要null和hd这样的函数，你可以很容易地自己写出来（但不要为你的家庭作业这样做）。
模式匹配比我们到目前为止所指出的要普遍和强大得多。我们在下面给出关于模式匹配的”全部真相”。

“One-of”类型的有用例子

现在让我们考虑几个”one-of”类型有用的例子，因为到目前为止我们只考虑了一个愚蠢的例子。

首先，它们适合于枚举一组固定的选项，比起使用小整数的风格好得多，例如：

datatype suit = Club | Diamond | Heart | Spade

许多语言都支持这种枚举，包括Java和C，但ML更进一步，让变体携带数据，所以我们可以做这样的事情：

datatype rank = Jack | Queen | King | Ace | Num of int

然后我们可以用each-of类型组合这两块： suit * rank。

One-of类型在不同情况下有不同数据时也很有用。例如，假设你想通过id-numbers来识别学生，但如果有的学生没有id-numbers（也许他们是新来的），那么你就用他们的全名来代替（包括名字，可选的中间名和姓氏）。这个数据类型绑定直接抓住了这个想法：

datatype id = StudentNum of int
            | Name of string * (string option) * string

如果程序员对one-of类型缺乏理解，坚持使用each-of类型，就会像把锯子当作锤子一样（尽管可以工作，但实际上做错了），考虑像这样的不好代码：

(* If student_num is -1, then use the other fields, otherwise ignore other fields *)
 {student_num : int, first : string, middle : string option, last : string}

这种方法要求所有的代码都要遵循注释中的规则，没有类型检查器的帮助。它还浪费了空间，在每条记录中都有不应该使用的字段。

另一方面，如果我们想为每个学生存储他们的ID号码（如果他们有的话）和他们的全名，那么each-of类型都是正确的方法：

{ student_num : int option,
	first	  : string,
	middle	  : string option,
	last	  : string }

我们的最后一个例子是一个包含常数、负数、加法和乘法的算术表达式的数据定义：

datatype exp = Constant of int
             | Negate of exp
             | Add of exp * exp
             | Multiply of exp * exp

由于自引用，这个数据定义真正描述的是树，其中叶子节点是整数，内部节点是子节点取相反数，两个子节点的加法或有两个子节点的乘法。我们可以写一个函数，接收一个exp并对其进行评估：

fun eval e =
    case e of
        Constant i => i
      | Negate e2  => ~ (eval e2)
      | Add(e1,e2) => (eval e1) + (eval e2)
      | Multiply(e1,e2) => (eval e1) * (eval e2)

所以下面的结果是15：

eval (Add (Constant 19, Negate (Constant 4)))

请注意，构造函数只是我们用其他表达式（通常是由构造函数构建的其他值）调用的函数。

我们可以在exp类型的值上编写许多函数，其中大部分都会以类似的方式使用模式匹配和递归。下面是你可以编写的处理exp参数的其他函数。

表达式中最大的常数
表达式中所有常数的列表（使用列表apeend）
表示表达式中是否至少有一个乘法操作的bool变量
表达式中加法表达式的数量

这里是最后一个函数：

fun number_of_adds e =
    case e of
        Constant i		=> 0
      | Negate e2	    => number_of_adds e2
      | Add(e1,e2)	    => 1 + number_of_adds e1 + number_of_adds e2
      | Multiply(e1,e2) => number_of_adds e1 + number_of_adds e2

数据类型绑定和Case表达式到目前为止，准确地描述

我们可以把到目前为止对数据类型和模式匹配的了解总结如下：绑定

datatype t = C1 of t1 | C2 of t2 | ... | Cn of tn

引入了一个新的类型t，每个构造函数Ci都是一个ti->t类型的函数。对于”不携带任何东西”的变体，可以省略”of ti“，这样的构造函数只有类型t。为了”获得t的piece”，我们使用case表达式：

case e of p1 => e1 | p2 => e2 | ... | pn => en

一个case表达式将e评估为一个值v，找到第一个与v相匹配的模式pi，并评估ei以产生整个case表达式的结果。到目前为止，模式看起来像Ci(x1,...,xn)，其中Ci是一个类型为t1 * ... * tn -> t的构造函数（或者如果Ci没有携带任何东西，则只有Ci）。这样的模式与形式为Ci(v1,...,vn)的值相匹配，并将每个xi与vi绑定，以评估相应的ei。

类型同义词

在继续讨论数据类型之前，让我们把它们与另一种有用的绑定进行对比，它也引入了一个新的类型名称。一个类型同义词只是为一个现有的类型创建了另一个名字，这个名字完全可以和现有的类型互换。

例如，如果我们写

type foo = int

那么我们就可以在写int的地方写foo，反之亦然。因此，给定一个foo->foo类型的函数，我们可以对该函数调用参数3，并将结果加到4中。 REPL有时会打印foo，有时会打印int，这取决于情况；细节不重要，由语言实现决定。对于像int这样的类型，这样的同义词不是很有用（尽管以后当我们研究ML的模块系统时，我们将建立在这个特性上）。

但是对于更复杂的类型，创建类型同义词可能会很方便。下面是我们上面创建的类型的一些例子：

type card = suit * rank
type name_record = { student_num : int option,
                     first		: string,
                     middle		: string option,
                     last		: string }

只要记住这些同义词是完全可以互换的。例如，如果一个家庭作业问题需要一个类型为card -> int的函数，而REPL报告你的解决方案的类型为suit * rank -> int，这没有问题，因为这些类型是”相同的”。

相反，数据类型绑定引入了一个与任何现有类型都不相同的类型。它创建了构造函数，产生这个新类型的值。因此，唯一与suit相同的类型是suit，除非我们以后为它引入一个同义词。

列表和选项是数据类型

因为数据类型的表示可以是递归的，我们可以用它们来为列表创建我们自己的类型。例如，这种绑定方式对整数链表很有效：

datatype my_int_list = Empty
				   | Cons of int * my_int_list

我们可以使用构造函数Empty和Cons来创建my_int_list的值，我们可以使用case表达式来使用这些值（在这个例子中，我们使用了变量xs'。许多语言不允许在变量名中使用’这个字符，但ML允许，而且在数学中通常使用它，并将这样的变量读作 “exes prime”。）：

val one_two_three = Cons(1,Cons(2,Cons(3,Empty)))
fun append_mylist (xs,ys) =
    case xs of
    	Empty => ys
      |	Cons(x,xs') => Cons(x, append_mylist(xs',ys))

原来，“内置的”列表和选项（即。预设了一些特殊的语法支持）只是一些数据类型。作为风格问题，使用内置的广为人知的功能比自己发明的要好。

更重要的是，使用模式匹配来访问列表和选项的值是更好的风格，而不是我们之前看到的null, hd, tl, isSome, valOf函数。(我们使用它们是因为我们还没有学模式匹配，我们不想耽误练习函数式编程的技能）。

对于选项，你只需要知道SOME和NONE是构造函数，我们用它们来创建值（就像以前一样），并在模式中访问这些值。下面是一个关于后者的简短例子：

fun inc_or_zero intoption =
    case intoption of
    	NONE => 0
      | SOME i => i+1

列表的情况类似，但有一些方便的语法特点。[]实际上是一个不携带任何内容的构造函数，而::实际上是一个携带两个东西的构造函数，但::是不寻常的，因为它是一个infix操作符（它被放在它的两个操作数之间），在创建内容和模式中都是如此：

fun sum_list xs =
    case xs of
    	[] => 0
      |	x::xs' => x + sum_list xs'
    
fun append (xs,ys) =
    case xs of
    	[] => ys
      | x::xs' => x :: append(xs',ys)

注意这里x和xs'只不过是通过模式匹配引入的局部变量。我们可以使用任何我们想要的变量的名字。我们甚至可以使用hd和tl，这样做只是对外部环境中预设的函数进行shadow。

在访问列表和选项时，你通常应该选择模式匹配，而不是像null和hd这样的函数，其原因与一般的数据类型绑定相同：你不能忘记某些情形，你不能应用错误的函数，等等。那么，如果方法不够好，为什么ML环境会预设这些函数呢？部分原因是它们在作为参数传递给其他函数时很有用，这是本课程下一节的一个主要话题。

多态数据类型

除了[]和::的奇怪语法外，内置列表和选项与我们的数据类型绑定示例的唯一区别是，内置列表和选项是多态的——它们可以用来携带任何类型的值，正如我们所看到的int list, int list list, (bool * int) list等。你也可以为你自己的数据类型绑定做到这一点，事实上，这对于构建”通用”数据结构非常有用。虽然我们在这里不会重点讨论这个功能的使用（也就是说，你没有责任知道如何去做），但这并没有什么非常复杂的地方。例如，这正是选项在环境中的预设方式：

datatype 'a option = NONE | SOME of 'a

这样的绑定并没有引入类型选项。相反，它使得如果t是一个类型，那么t option也是一个类型。你也可以设计多态数据类型，它可以接受多种类型。例如，这里有一棵二叉树，内部节点持有'a类型的值，叶子持有'b类型的值：

datatype ('a,'b) tree = Node of 'a * ('a,'b) tree * ('a,'b) tree
					| Leaf of 'b

然后我们就有了(int, int) tree（其中每个节点和叶子都持有一个int）和(string, bool) tree（其中每个节点持有一个字符串，每个叶子节点持有一个bool）等类型。对于普通数据类型和多态数据类型，使用构造函数和模式匹配的方式是一样的。

Each-Of类型的模式匹配：关于值绑定的真相

到目前为止，我们已经将模式匹配用于one-of类型，但我们也可以将其用于each-of类型。给定一个记录值{f1=v1,...,fn=vn}，模式{f1=x1,...,fn=xn}匹配并将xi绑定到vi。正如你所期望的，模式中字段的顺序并不重要。如前所述，元组是记录的语法糖：模式(x1,...,xn)与{1=x1,...,n=xn}相同，并且与元组值(v1,...,vn)匹配，后者与{1=v1,...,n=vn}相同。所以我们可以写如下函数来求一个int * int * int的三个部分的和：

fun sum_triple (triple : int * int * int) =
    case triple of
    	(x,y,z) => z + y + x

而用记录（和ML的字符串连接运算符）的类似例子可以是这样：

fun full_name (r : {first:string,middle:string,last:string}) =
    case r of
    	{first=x,middle=y,last=z} => x ^ " " ^ y ^ " " ^z

然而，只有一个分支的case-expression的风格很差，因为这种表达方式的目的是区分cases（多个case）。那么，当我们知道一个单一的模式将确定匹配时，我们应该如何对每个类型使用模式匹配，以为了方便提取值？事实证明，你也可以在值绑定中使用模式！所以如下方法是更好的风格：

fun full_name (r : {first:string,middle:string,last:string}) =
    let val {first=x,middle=y,last=z} = r
    in
    	x ^ " " ^ y ^ " " ^z
    end

fun sum_triple (triple : int*int*int) =
    let val (x,y,z) = triple
    in
    	x + y + z
    end

实际上我们可以做得更好。就像在val绑定中可以使用模式将变量（如x、y和z）绑定到表达式（如triple）的各个部分一样，我们可以在确定函数绑定时使用模式，模式将通过与函数调用时传递的值进行匹配来引入绑定。因此，对于我们的示例函数，这里是第三种也是最好的方法：

fun full_name {first=x,middle=y,last=z} =
	x ^ " " ^ y ^ " " ^z

fun sum_triple (x,y,z) =
	x + y + z

这个版本的sum_triple应该让你感兴趣。它接受triple作为参数，并使用模式匹配将三个变量绑定到三个片段上，以便在函数主体中使用。但它看起来完全像一个接受三个int类型参数的函数。事实上，int*int*int->int类型是用于三参数函数还是用于的单参数triple函数？

事实证明，我们基本上一直在撒谎。在ML中不存在多参数函数：ML中的每个函数都只接收一个参数! 每当我们写一个多参数函数时，我们实际上是在写一个单参数函数，它以一个元组为参数，使用模式匹配来提取片段。这是一个很常见的习语，很容易让人忘记，而且在和朋友讨论ML代码时，完全可以说成是”多参数函数”。但就实际的语言定义而言，它确实是一个单参数函数：用单case表达式扩展出sum_triple的第一个版本的语法糖。

这种灵活性有时是很有用的。在像C和Java这样的语言中，你不能让一个函数/方法计算的结果立即传递给另一个多参数函数/方法。但是对于作为元组的单参数函数，这就很好用。这里有一个愚蠢的例子，我们通过”向左旋转三元组两次”来得到“向右旋转三元组”：

fun rotate_left (x,y,z) = (y,z,x)
fun rotate_right triple = rotate_left(rotate_left triple)

更一般地说，你可以计算元组，然后将它们传递给函数，即使该函数的作者是以多参数的方式思考的。

那么零参数的函数呢？它们也不存在。绑定函数f () = e是使用单位模式()来匹配传递单位值()的调用，这是unit类型唯一的值。unit类型只是一个只有一个构造函数的数据类型，它不需要参数，并且使用不寻常的语法()。基本地，数据类型unit = ()是预先设定好的。

题外话：类型推理

通过使用模式来访问元组和记录值，而不是#foo，你会发现不再需要在函数参数上写类型。事实上，在ML中，传统的做法是不写类型，你可以随时使用REPL来找出函数的类型。我们以前需要它们的原因是#foo没有提供足够的信息对函数进行类型检查，因为类型检查器不知道记录应该有哪些其他的域，但是上面介绍的记录/元组模式提供了这些信息。在ML中，每个变量和函数都有一个类型（否则你的程序就无法进行类型检查）——类型推理只是意味着你不需要写下类型。

所以我们上面使用模式匹配而不是#middle或#2的例子都不需要参数类型。写这些不那么杂乱的版本往往是更好的风格，其中又以最后一个版本为最佳：

fun sum_triple triple =
    case triple of
    	(x,y,z) => z + y + x
    	
fun sum_triple triple =
    let val (x,y,z) = triple
    in
    	x + y + z
    end

fun sum_triple (x,y,z) =
	x + y + z

这个版本的参数需要一个显式类型：

fun sum_triple (triple : int * int * int) =
	#1 triple + #2 triple + #3 triple

原因是类型检查器不能从fun sum_triple triple = #1 triple + #2 triple + #3 triple中推断出参数必须有int*int*int类型，因为它也可能有int*int*int*int*string或int*int*int*bool*string或无限数量的其他类型。如果你不使用#，由于类型推理的便利，ML几乎不需要明确的类型注释。

事实上，类型推理有时会让函数比你想象的更通用。考虑一下这段代码，它确实使用了元组/记录的一部分：

fun partial_sum (x,y,z) = x + z
fun partial_name {first=x, middle=y, last=z} = x ^ " " ^ z

在这两种情况下，推断的函数类型揭示了y的类型可以是任何类型，所以我们可以调用partial_sum (3,4,5)或 partial_sum (3,false,5) 。

我们将在以后的章节中讨论这些多态函数以及类型推理如何工作，因为它们本身就是主要的课程主题。现在，只要停止使用#，停止写参数类型，如果你偶尔看到像'a或'b这样的类型，也不要感到困惑，因为类型推理在接下来会有更多讨论。

题外话：多态类型和等价类型

我们现在鼓励你在程序中不做明确的类型注释，但正如上面所看到的，这可能会导致令人惊讶的一般类型。假设你被要求写一个类型为int*int*int->int的函数，其行为类似于上面的partial_sum，但是REPL正确地指出partial_sum的类型为int*'a*int->int。这没关系，因为多态性表明partial_sum有一个更通用的类型。如果你能把一个包含'a, 'b, 'c等的类型，并把这些类型变量的每一个都替换成你想要的类型，那么你就有一个比你想要的类型更通用的类型。

再举个例子，我们写的append的类型是'a list * 'a list -> 'a list，所以通过持续地用string替换'a，我们可以使用append，好像它的类型是string list * string list -> string list。我们可以对任何类型做这个操作，而不仅仅是字符串。我们实际上没有做任何事情：这只是一个练习，检查一个类型是否比我们需要的类型更通用。注意，像'a这样的类型变量必须被一致替换，这意味着append的类型不比string list * int list -> string list更通用。

你也可能会看到有两个前导撇号的类型变量，比如''a。这些被称为平等类型，它们是ML的一个相当奇怪的特征，与我们目前的研究不相关。基本上，ML中的=运算符（用于比较事物）对许多类型都有效，不仅仅是int，但它的两个操作数必须具有相同的类型。例如，它对字符串和元组类型都有效，元组中的所有类型都支持等号（例如，int * (string * bool)）。（它对函数不起作用，因为无法判断两个函数是否总是做同样的事情。它也不适用于real类型，因为由于四舍五入的原因，比较它们在算法上几乎总是错误的。）像''a这样的类型只能用一个”平等类型 “来代替它，但它并不是对每个类型都有效。

fun same_thing(x,y) = if x=y then "yes" else "no" (* has type ''a * ''a -> string *)
fun is_three x = if x=3 then "yes" else "no" (* has type int -> string *)

同样，我们将在后面更多地讨论多态类型和类型推理，但这个题外话对避免作业2的混淆有帮助：如果你写一个函数，REPL给它一个比你需要的更一般的类型，这是好的。也要记住，如上所述，如果REPL使用的类型同义词与你期望的不同，也是可以的。

嵌套模式

事实证明，模式的表示是递归的：在我们的模式中，凡是有变量的地方，我们都可以放上另一个模式。粗略地说，模式匹配的语义是，被匹配的值必须具有与模式相同的”形状”，并且变量被绑定到”正确的部分”。(这是粗略的解释，这就是为什么下面会描述一个精确的说法)。例如，模式a::(b::(c::d))将匹配任何至少有3个元素的列表，它将把a绑定到第一个元素，b绑定到第二个元素，c绑定到第三个元素，d绑定到包含所有其他元素的列表（如果有）。另一方面，模式a::(b::(c:[]))将只匹配正好有三个元素的列表。另一个嵌套模式是(a,b,c)::d，它匹配任何非空的三元素列表，将a绑定到头部的第一个组件，b绑定到头部的第二个组件，c绑定到头部的第三个组件，d绑定到列表的尾部。

一般来说，模式匹配是指接受一个值和一个模式，

(1)决定模式是否与该值匹配，
(2)如果匹配，则将变量绑定到该值的正确部分。

以下是模式匹配的优雅递归表示的一些关键部分：

一个变量模式(x)匹配任何值v，并引入一个绑定（从x到v）。
模式C匹配值C，如果C是一个不携带数据的构造函数。
模式C p，其中C是一个构造函数，p是一个模式，如果p匹配v（即嵌套模式匹配携带的值），则匹配形式为C v的值（注意构造函数是一样的）。它引入了p匹配v所引入的绑定关系。
如果p1匹配v1，p2匹配v2，…，pn匹配vn，那么模式(p1,p2,...,pn)匹配(v1,v2,...,vn)。它引入了所有递归匹配所引入的绑定关系。
(对于形式为{f1=p1,...,fn=pn}的记录模式也有类似的情况…)

这个递归表示以两种有趣的方式扩展了我们以前的理解。首先，对于携带多个参数的构造函数C，我们不必写像C(x1,...,xn)这样的模式，尽管我们经常这样做。我们也可以写C x；这将把x与C(v1,...,vn)对应的元组绑定。真正的情况是，所有构造函数都接受0或1个参数，但参数本身可以是一个元组。所以C(x1,...,xn)实际上是一个嵌套模式，其中(x1,...,xn)部分只是一个匹配所有具有$n$个部分的元组的模式。其次，更重要的是，当我们想只匹配具有某种”形状”的值时，我们可以使用嵌套模式而不是嵌套case表达式。

还有其他类型的模式。有时我们不需要将变量与值的一部分绑定。例如，考虑一下这个计算列表长度的函数：

fun len xs =
    case xs of
    	[] => 0
      |	 x::xs' => 1 + len xs'

我们不使用变量x，在这种情况下，不引入变量是更好的风格。\通配符模式_匹配一切（就像变量模式匹配一切），但不引入绑定。所以我们应该写：

fun len xs =
    case xs of
    	[] => 0
      |	 _::xs' => 1 + len xs'

就我们的一般定义而言，通配符模式是简单的：

通配符模式（_）匹配任何值v，并且不引入任何绑定。

最后，你可以在模式中使用常整数。例如，模式37匹配值37，并且不引入任何绑定关系。

嵌套模式的有用例子

使用嵌套模式而不是嵌套case表达式的一个优雅的例子”压缩”或解压缩”列表（下面将讨论例外情况，但不是这个例子的重要部分）：

exception BadTriple

fun zip3 list_triple =
    case list_triple of 
	    ([],[],[]) => []
      | (hd1::tl1,hd2::tl2,hd3::tl3) => (hd1,hd2,hd3)::zip3(tl1,tl2,tl3)
      | _ => raise ListLengthMismatch

fun unzip3 lst =
    case lst of
	    [] => ([],[],[])
      | (a,b,c)::tl => let val (l1,l2,l3) = unzip3 tl
		              in
			   			(a::l1,b::l2,c::l3)
		       		  end

这个例子检查一个整数列表是否被排序：

fun nondecreasing xs =
    case xs of
		[] => true
       | x::[] => true
       | head::(neck::rest) => (head <= neck andalso nondecreasing (neck::rest))

有时通过对两个值的匹配来比较也是很优雅的。这个例子是在不执行乘法的情况下确定一个乘积的符号，这个例子有点傻，但展示了这个想法：

datatype sgn = P | N | Z

fun multsign (x1,x2) = 
  let fun sign x = if x=0 then Z else if x>0 then P else N 
  in
      case (sign x1,sign x2) of
	  (Z,_) => Z
	| (_,Z) => Z
	| (P,P) => P
	| (N,N) => P
	| _     => N (* many say bad style; I am okay with it *)
  end

这最后一种case的风格值得讨论。当你像这样在底部加入一个”catch-all”案例时，你就放弃了对你没有忘记任何case的检查：毕竟，它与前面的case没有匹配的东西都匹配，所以类型检查器肯定不会认为你忘记了任何case。因此，如果使用这种技术，你需要格外小心，列举剩余的情况（在本例中为(N,P)和(P,N)）可能更容易出错。然后，类型检查器仍将确定没有遗漏的情况，因为它必须对使用(Z,_）和(_,Z)进行推理，以确定没有遗漏sgn*sgn类型的可能性。

可选的：函数绑定中的多个case

到目前为止，我们已经看到在case表达式中对one-of类型进行模式匹配。我们还看到了在val或函数绑定中对each-of类型进行模式匹配的良好风格，这就是”多参数函数”的真正含义。但是有没有办法在val/function绑定中对one-of类型进行匹配？这似乎是个坏主意，因为我们需要多种可能性。但事实证明，ML有特殊的语法可以在函数名称中做到这一点。这里有两个例子，一个是我们自己的数据类型，一个是列表：

datatype exp = Constant of int 
             | Negate of exp 
             | Add of exp * exp
             | Multiply of exp * exp

fun eval (Constant i) = i
  | eval (Negate e2) = ~ (eval e2)
  | eval (Add(e1,e2)) = (eval e1) + (eval e2)
  | eval (Multiply(e1,e2)) = (eval e1) * (eval e2)

fun append ([],ys) = ys
  | append (x::xs',ys) = x :: append(xs',ys)

作为一个品味问题，你的导师一直不太喜欢这种风格，你必须在正确的地方使用括号。但这在ML程序员中很常见，所以也欢迎你这样做。从语义上讲，它只是一个单一函数体case表达式的语法糖：

fun eval e =
    case e of
        Constant i => i
      | Negate e2  => ~ (old_eval e2)
      | Add(e1,e2) => (old_eval e1) + (old_eval e2)
      | Multiply(e1,e2) => (old_eval e1) * (old_eval e2)

fun append e =
    case e of
    	([],ys) => ys
     | 	(x::xs',ys) => x :: append(xs',ys)

一般来说，语法

fun f p1 = e1
| 	f p2 = e2
...
| 	f pn = en

只是如下形式的语法糖（从技术上讲，x必须是一些尚未在外部环境中定义并由函数中的表达式之一使用的变量。）：

fun f x =
    case x of
    p1 => e1
  | p2 => e2
...
  | pn => en

注意append的例子使用了嵌套模式：每个分支匹配一对列表，通过把模式（例如[]或x::xs'）放在其他模式里面。

异常

ML有一个内置的异常概念。你可以用raise基元来引发（也被称为抛出）一个异常。例如，标准库中的hd函数在用[]调用时引发了List.Empty异常。

fun hd xs =
    case xs of
    	[] => raise List.Empty
      | x::_ => x

你可以用异常绑定来创建你自己的异常种类。异常可以选择性地携带值，这让引发异常的代码提供更多的信息：

exception MyUndesirableCondition
exception MyOtherException of int * int

异常的种类很像数据类型绑定的构造器。事实上，它们是函数（如果它们携带值）或值（如果它们不携带值），它们创建的是exn类型的值而不是数据类型的类型。所以Empty, MyUndesirableCondition, MyOtherException(3,9)都是exn类型的值，而MyOtherException的类型是int*int->exn。

通常我们只是把异常构造函数作为raise的参数，比如raise MyOtherException(3,9)，但我们可以更广泛地使用它们来创建exn类型的值。例如，这里有一个函数的版本，它返回一个整数列表中的最大元素。如果用[]调用的话，它没有像List.Empty那样返回一个选项或引发一个特殊的异常，它需要一个exn类型的参数并抛出它。所以调用者可以传入其选择的异常。(类型检查器可以推断出ex必须有exn类型，因为那是raise对其参数的期望类型。)

fun maxlist (xs,ex) =
    case xs of
    	[] => raise ex
    |  	x::[] => x
    | 	x::xs' => Int.max(x,maxlist(xs',ex))

注意，调用maxlist([3,4,0], List.Empty)不会引发一个异常；这个调用将异常值传递给函数，然后函数不会引发这个异常。

与异常有关的另一个特征是处理（也被称为捕获）异常。为此，ML有异常处理，它看起来像e1 handle p => e2，其中e1和e2是表达式，p是一个匹配异常的模式。其语义是对e1进行评估，并将其结果作为答案。但是如果e1引发了一个与p匹配的异常，那么e2就会被评估，这就是整个表达式的答案。如果e1引发了一个与p不匹配的异常，那么整个句柄表达式也会引发这个异常。同样地，如果e2引发了一个异常，那么整个表达式也会引发一个异常。

和case-expressions一样，handle-expression也可以有多个分支，每个分支都有一个模式和表达式，在语法上用|分隔。

尾递归和累加器

本专题涉及新的编程习惯，但没有新的语言结构。这里定义了尾递归，描述了它与在ML等函数式语言中编写高效递归函数的关系，并介绍了如何使用累加器作为一种技术来使一些函数成为尾递归。

为了理解尾递归和累加器，请考虑这些用于对一个列表中的元素进行求和的函数。

fun sum1 xs =
    case xs of
        [] => 0
      | i::xs’ => i + sum1 xs’
      
fun sum2 xs =
    let fun f (xs,acc) =
            case xs of
                [] => acc
              | i::xs’ => f(xs’,i+acc)
    in
    	f(xs,0)
    end

这两个函数计算的结果是一样的，但是sum2更复杂，它使用了一个本地辅助函数，需要一个额外的参数，叫做acc，代表”累加器”。在f的基本情况下，我们返回acc，最外层调用的值是0，与sum1的基本情况下使用的值相同。这种模式很常见：非累加器风格的基本情形成为初始累加器，累加器风格的基本情形只是返回累加器。

当sum2显然更复杂时，为什么会选择它呢？要回答这个问题，我们需要了解一点关于函数调用的实现方式。从概念上讲，有一个调用栈，它是一个堆栈（具有push和pop操作的数据结构），每个已经开始但尚未完成的函数调用（在其中）都有一个元素。每个元素都存储着诸如局部变量的值以及函数的哪一部分还没有被评估。当一个函数体的评估调用另一个函数时，一个新的元素被push到调用栈上，当被调用的函数完成时，它被pop。

所以对于sum1来说，每一次对sum1的递归调用都会有一个调用堆栈元素（有时只称为”栈帧”），也就是说，堆栈会和列表一样大。这是必要的，因为在弹出每个堆栈帧之后，调用者必须“完成正文的其余部分”——即将i添加到递归结果并返回。

鉴于到目前为止的描述，sum2也没有更好：sum2调用f，然后为每个列表元素进行一次递归调用。然而，当f对f进行递归调用时，在被调用者返回后，除了返回被调用者的结果外，调用者没有其他事情可做。这种情况被称为尾部调用（我们不要试图弄清楚为什么叫这个名字），像ML这样的函数式语言通常会承诺一个基本的优化。当一个调用是尾部调用时，调用者的堆栈框架在调用前被弹出——被调用者的栈帧只是取代了调用者的栈帧。这是有道理的：反正调用者只是要返回被调用者的结果。因此，对sum2的调用永远不会使用超过1个栈帧。

为什么函数式语言的实现包括这种优化？通过这样做，递归有时可以像while-loop一样高效，也不会使调用栈变大。这个”有时”是指当调用是尾部调用时，程序员可以对此进行推理，因为你可以看一下代码，确定哪些调用是尾部调用。

所有调用都不需要指向同一个函数（f可以调用g），所以比while-loops更灵活，因为后者总是要”调用”同一个循环。使用累加器是将递归函数变成”尾递归函数”（所有的递归调用都是尾部调用）的一种常见方式，但并不总是如此。例如，处理树（而不是列表）的函数通常有与树的深度一样大的调用栈，但这在任何语言中都是真实的：while-loops对于处理树来说不是很有用。

尾部位置的精确定义

虽然大多数人依靠直觉来判断 “哪些调用是尾部调用”，但我们可以通过递归地定义尾部位置，并说如果一个调用处于尾部位置，它就是一个尾部调用。这个定义对每一种表达式都有定义，这里有几个部分：

在fun f(x) = e中，e在尾部位置。
如果一个表达式不在尾部位置，那么它的所有子表达式都不在尾部位置。
如果if e1 then e2 else e3在尾部位置，那么e2和e3都在尾部位置（但不是e1）,（Case表达式类似）
如果let b1 ... bn in e end在尾部位置，那么e在尾部位置（但是绑定中没有表达式在尾部位置）。
函数调用参数不在尾部位置。
…

Programming Languages Part A Section2 翻译

Coursera编程语言课程第2节总结

目录

构建新类型的概念性方法

记录：“Each-of”类型的另一种方法

根据名称 vs 根据位置，语法糖和元组的真相

数据类型绑定：我们自己的“One-of”类型

ML如何不提供对数据类型值的访问

ML如何提供对数据类型值的访问：Case表达式

“One-of”类型的有用例子

数据类型绑定和Case表达式到目前为止，准确地描述

类型同义词

列表和选项是数据类型

多态数据类型

Each-Of类型的模式匹配：关于值绑定的真相

题外话：类型推理

题外话：多态类型和等价类型

嵌套模式

嵌套模式的有用例子

可选的：函数绑定中的多个case

异常

尾递归和累加器

更多尾递归示例

尾部位置的精确定义

Coursera编程语言课程 第2节总结

目录

构建新类型的概念性方法

记录：“Each-of”类型的另一种方法

根据名称 vs 根据位置，语法糖和元组的真相

数据类型绑定：我们自己的“One-of”类型

ML如何不提供对数据类型值的访问

ML如何提供对数据类型值的访问：Case表达式

“One-of”类型的有用例子

数据类型绑定和Case表达式到目前为止，准确地描述

类型同义词

列表和选项是数据类型

多态数据类型

Each-Of类型的模式匹配：关于值绑定的真相

题外话：类型推理

题外话：多态类型和等价类型

嵌套模式

嵌套模式的有用例子

可选的：函数绑定中的多个case

异常

尾递归和累加器

更多尾递归示例

尾部位置的精确定义

Coursera编程语言课程第2节总结