这次回顾Week3的内容,主要介绍了Standard ML的模式匹配。

课程主页:

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

B站搬运:

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

Week 3

构建新类型的方法

如何构建更大的类型

  • 已知:

    • 具有各种基本类型,如int bool unit char
    • 构建(嵌套)复合类型的方法:元组、列表、选项(option)
  • 即将推出:

    • 构建复合类型的更多方法
  • 首先:任何语言中3个最重要的类型构建块

    1. “每个”(“Each of”):一个t值包含t1 t2 ... tn中的每个值
    2. “其中一个”(“One of”):一个t值包含t1 t2 ... tn中的某一个值
    3. “自引用”(“Self reference”):一个t值可以引用其他t
    • 值得注意的是,很多数据都可以用这些构建块构件
    • 注意:这些不是这些概念的通用名称

例子

  • 元组构建each-of类型
    • int * bool包含intbool
  • 选项(option)构建one-of类型
    • int option包含一个int或不包含数据
  • 列表使用所有三个构建块
    • int list包含一个int和另一个int list或不包含数据
  • 当然,我们可以嵌套复合类型
    • ((int * int) option * (int list list)) option

即将推出

  • 另一种在ML中构建each-of类型的方法
    • 记录(Records):有命名字段
    • 和元组的关系以及语法糖的概念
  • 一种在ML中构建和使用我们自己的one-of类型的方法
    • 例如,包含intstring的类型
    • 将导致模式匹配,ML最酷、对Java程序员来说最奇怪的特性之一
  • 本课程后面部分:OOP是如何实现其中one-of类型的
    • 过程式和函数式编程的关键对比

记录(Records)

记录

  • 记录值有持有值的字段(任何名称)

    {f1 = v1, …, fn = vn}
  • 记录类型有持有类型的字段(和名称)

    {f1 : t1, …, fn : tn}
  • 记录值或类型中的字段的顺序并不重要

    • REPL按字母顺序排列字段,只是为了保持一致性
  • 建立记录:

    {f1 = e1, …, fn = en}
  • 访问片段:

    #myfieldname e

    (评估规则和类型检查符合预期)

例子

{name = “Amelia”, id = 41123 - 12}

评估为

{id = 41111, name = “Amelia”}

并且具有类型

{id : int, name : string}

如果一些表达式,如变量x有这种类型,那么就用如下方式得到字段:

#id x #name x

注意我们没有必要声明任何记录类型

  • 同样的程序也可以使用类型为{id:bool,ego:bool}{id=true,ego=false}

按名称与按位置

  • (4,7,9){f=4,g=7,h=9}之间没有什么区别。

    • 元组稍短一些
    • 记录更容易记住“什么在哪里”
    • 一般来说,这是一个品味问题,但对于许多字段,记录通常是一个更好的选择
  • 结构体语法的一个常见决定是,是通过位置(如元组)还是通过一些(字段)名称(如记录)来指代事物。

    • 一个常见的混合体就像Java方法参数(以及到目前为止使用的ML函数)。
      • 调用者使用位置
      • 被调用者使用变量
      • 可以采用不同的方式;有些语言可以这么做

元组作为句法糖

关于元组的真相

之前,我们给出了元组的语法、类型检查规则和评估规则,但我们可以用如下方式取代:

  • 元组语法只是写某些记录的不同方式
  • (e1,...,en)是表达{1=e1,...,n=en}的另一种方式
  • t1*...*tn是表达{1:t1,...,n:tn}的另一种方式
  • 换句话说,字段名为1、2、…的记录。

事实上,ML实际上是这样定义元组的

  • 除了程序和打印中的特殊语法外,它们并不存在
  • 你可以写{1=4,2=7,3=9},但这是不好的风格

语法糖

“元组只是字段名为1、2、…n的记录的语法糖”

  • 语法:可以完全通过相应的记录语法来描述语义
  • 糖:它们使语言更甜

将会看到更多的语法糖的例子

  • 简化了对语言的理解
  • 简化了语言的实现

为什么?因为即使我们有元组的语法便利性,也很少有语义需要担心。

我们看到的其他例子:

  • andalso, orelse vs. if then else

数据类型绑定

数据类型绑定

  • “奇怪的”(?)而且非常棒(!)制作以下类型之一的方法:

    • 一个datatype绑定

      datatype mytype = TwoInts of int * int
      			   | Str of string 
      			   | Pizza
  • 在环境中添加一个新的类型mytype

  • 在环境中添加构造函数:TwoInts, Str, 和Pizza

  • 构造函数是生成新类型值(或是新类型值)的函数:

    • TwoInts : int * int -> mytype
    • Str : string -> mytype
    • Pizza : mytype

我们创造的值

  • 任何mytype类型的值都是由其中一个构造函数构成的
  • 该值包含:
    • “哪个构造函数”的“标签”(例如,TwoInts)。
    • 相应的数据(例如(7,9))。
  • 例子:
    • TwoInts(3+4,5+4)被评估为TwoInts(7,9)
    • Str(if true then "hi" else "bye")被评估为Str("hi")
    • Pizza是一个值

使用他们

  • 所以我们知道如何建立数据类型的值;下一步是需要访问它们
  • 访问一个数据类型的值有两个方面
    • 检查它是什么变体(什么构造函数生成了它)
    • 提取数据(如果该变体有任何数据)
  • 注意我们的one-of类型是如何使用函数来实现的
    • nullisSome检查变体
    • hd, tl, valOf提取数据(在错误的变体上引发异常)
  • ML对数据类型的绑定也可以这样做
    • 例如,isStrgetStrData等函数。
    • 但是,它做得更好

Case表达式

Case

ML结合了使用case表达式和模式匹配访问one-of值的两个方面

  • 模式匹配更加通用/强大(很快!)

例子:

fun f x = 
    case x of 
	    Pizza => 3 
      | Str s => 8
      | TwoInts(i1,i2) => i1 + i2
  • 一个多分支的条件表达式,根据变量选择分支
  • 提取数据并绑定到该分支的本地变量上
  • 类型检查:所有分支必须具有相同的类型
  • 评估:在case…和正确分支之间进行评估

模式

一般形式的语法是:

case e0 of 
	 p1 => e1
   | p2 => e2 
     … 
   | pn => en

对于今天来说,每个模式都是一个构造函数的名称,后面跟着正确数量的变量(即CC xC(x, y))。

  • 从语法上讲,大多数模式(今天所有的模式)看起来都像表达式
  • 但模式不是表达式
    • 我们不对它们进行评估
    • 我们看e0的结果是否与它们匹配

为什么这种方式更好

  1. 你可以使用模式匹配来编写你自己的测试和数据提取函数,如果你必须这样做的话
    • 但不要在你的作业上这样做
  2. 你不能忘记一个case(不完整的模式匹配警告)
  3. 你不能重复一个case(类型检查错误)
  4. 你不能忘记正确地测试变体,否则可能得到一个异常(像hd []
  5. 模式匹配可以被泛化并变得更加强大,从而导致优雅和简洁的代码

有用的Datetype

有用的例子

让我们修正一下,到目前为止,我们唯一的例子数据类型是愚蠢的……

  • 枚举,包括携带其他数据

    datatype suit = Club | Diamond | Heart | Spade
    datatype rank = Jack | Queen | King
    			 | Ace | Num of int
  • 识别现实世界事物/人的另一种方式

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

不要这样做

不幸的是,糟糕的培训和使one-of类型不方便的语言导致了常见的不良风格,即在one-of类型是正确的工具的地方使用each-of类型:

(* use the student_num and ignore other fields unless the student_num is ~1 *)
{ student_num : int,
  first 	  : string,
  middle      : string option,
  last        : string }
  • 这种方法放弃了语言的所有好处,强制每个值都是一个变体,你不会忘记分支,等等。
  • 而且它使你不太清楚你在做什么

这就是说…

但如果相反,如果你代码中的每一个”人”都有名字,也许还有一个学生号,那么应该使用each-of:

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

表达式树

一个更令人兴奋的数据类型的例子,使用自引用:

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

ML中的exp类型的表达式:

Add (Constant (10+9), Negate (Constant 4))

如何在你的脑海中描绘出结果值:

递归

这并不奇怪,递归数据类型上的函数通常是递归的:

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)

迄今为止的模式匹配:精确

仔细的定义

当一个语言结构是”新和陌生的”,就有更多的理由来精确地定义评估规则,所以让我们回顾下”到目前为止”的数据类型绑定和case表达式(将会有一些扩展,但依然是”到目前为止”的内容)。

数据类型(Datatype)绑定

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

添加类型t和类型ti->t的构造函数Ci

  • Ci v是一个值,也就是说,结果”包括标签”

省略“of t”,因为构造函数只是标签,没有底层数据

  • 这样的Ci是一个类型为t的值

给定一个类型为t的表达式,使用case表达式来:

  • 看看它有哪个变体(标签)
  • 一旦你知道了哪个变体,就提取底层数据
case e of p1 => e1 | p2 => e2 | … | pn => en
  • 像往常一样,可以在表达式的任何地方使用case表达式
    • 不需要是整个函数体,但通常是这样的
  • e评估为一个值,称之为v
  • 如果pi是第一个与v相匹配的模式,那么结果就是在”通过匹配扩展”的环境中对ei进行评估
  • 模式Ci(x1,...,xn)与值Ci(v1,...,vn)相匹配,并将环境扩展为x1 to v1 ... xn to vn
    • 对于”无数据”构造函数,模式Ci匹配值Ci

另一个表达式的例子

把它们放在一起

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

我们来定义max_constant : exp -> int

这是一个很好的例子,我们可以在编程时将几个主题结合起来:

  • Case表达式
  • 本地辅助函数
  • 避免重复递归
  • 通过使用库函数实现更简单的解决方案
fun max_constant e =
    let fun max_of_two (e1,e2) =
	    let val m1 = max_constant e1
		val m2 = max_constant e2
	    in 
		if m1 > m2 then m1 else m2 
	    end
    in
	case e of
	    Constant i      => i
	  | Negate e2       => max_constant e2
	  | Add(e1,e2)      => max_of_two(e1,e2)
	  | Multiply(e1,e2) => max_of_two(e1,e2)
    end

val test_exp = Add (Constant 19, Negate (Constant 4))
val nineteen = max_constant test_exp

(* Note: Using Int.max, we don't need a local helper function. 
This second version is fewer lines, but there is a bit more
code copying. *)

fun max_constant2 e =
    case e of
	Constant i      => i
      | Negate e2       => max_constant2 e2
      | Add(e1,e2)      => Int.max(max_constant2 e1, max_constant2 e2)
      | Multiply(e1,e2) => Int.max(max_constant2 e1, max_constant2 e2)

类型同义词(Synonyms)

创造新类型

  • 一个数据类型绑定引入了一个新的类型名称

    • 区别于所有现有的类型
    • 创建新类型的值的唯一方法是构造函数
  • 一个类型同义词是一种新的绑定方式

    type aname = t
    • 只是为一个类型创建了另一个名字
    • 类型和名称在各方面都是可以互换的
    • 不要担心REPL打印的内容:选择它想要的内容,就像选择记录字段名称的顺序一样

为什么有这个?

  • 现在,类型同义词只是为了方便谈论类型:

  • 例子(已经定义了suit和rank):

    type card = suit * rank
  • 写一个类型的函数

    card -> bool
  • 好的,如果 REPL 说你的函数的类型是

    suit * rank -> bool
  • 这很方便,但并没有让我们”做”任何新的事情

  • 本课程后面将看到与模块化相关的另一个用法

列表(List)和选项(Option)是数据类型

递归数据类型

数据类型绑定可以描述递归结构

  • 见过算术表达式
  • 现在是链表
datatype my_int_list = Empty 
                     | Cons of int * my_int_list
					 
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))

选项(Option)是数据类型

选项只是一种预定义的数据类型绑定

  • NONESOME是构造函数,而不仅仅是函数。
  • 所以使用模式匹配而不是isSomevalOf
fun inc_or_zero intoption =
    case intoption of
        NONE => 0
      | SOME i => i+1

列表(List)是数据类型

不需要使用hd, tl, null

  • []::也都是构造函数
  • (奇怪的语法,尤其是中缀)
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)

为什么要进行模式匹配

  • 模式匹配对于选项和列表来说是更好的,原因与所有数据类型相同
    • 没有遗漏的情况,没有错误的变体的例外情况,等等。
  • 我们只是为了教学而先学了另一种方法
    • 在作业2中不要使用isSome, valOf, null, hd, tl
  • 那么为什么null, tl等是预定义的?
    • 为了作为参数传递给其他函数(下周)
    • 因为有时它们很方便
    • 但不是什么大事:可以自己定义它们

多态数据类型

完成故事

  • 内置选项和列表不是必需的/特殊的
    • 除了列表构造函数的特殊语法之外
  • 但这些数据类型的绑定是多态类型构造函数
    • int liststring list以及int list list都是类型,都不是list
    • 函数可能是多态的,也可能不是多态的
      • val sum_list : int list -> int
      • val append : 'a list * 'a list -> 'a list
  • 好的语言设计:可以定义新的多态数据类型
  • 半可选:作业2不需要了解这个

定义多态数据类型

  • 语法:将一个或多个类型变量置于数据类型名称之前

    datatype 'a option = NONE | SOME of 'a
    
    datatype 'a mylist = Empty | Cons of 'a * 'a mylist
    
    datatype ('a,'b) tree = 
    			    Node of 'a * ('a,'b) tree * ('a,'b) tree
    		      | Leaf of 'b
  • 可以在构造函数定义中使用这些类型变量

  • 绑定然后引入一个类型构造器,而不是一个类型

    • 必须是int myliststring mylist'a mylist
    • 不能是mylist

其他方面没有变化

照常使用构造函数和case表达式

  • 不改变评估规则
  • 类型检查将确保类型的使用是一致的
    • 例如:不能混合列表的元素类型
  • 函数将根据数据的使用方式而具有多态性或非多态性

each-of类型的模式匹配:函数参数的真相

一个令人兴奋的部分

  • 了解一些关于”真正发生了什么”的深刻真相
    • 使用的语法糖比我们意识到的要多得多
  • 每个值绑定和函数绑定都使用模式匹配
  • ML中的每个函数都只需要一个参数
  • 首先需要扩展我们对模式匹配的定义……

Each-of类型

  • 到目前为止,我们对其中一个类型使用了模式匹配,因为我们需要一种方法来访问这些值
  • 模式匹配也适用于记录和元组:
    • 模式(x1,...,xn)匹配元组值(v1,...,vn)
    • 模式{f1=x1, ..., fn=xn}匹配记录值{f1=x1, ..., fn=xn}(并且字段可以重新排序)。

例子

这是很差的风格,有效但风格拙劣,只有一个case分支:

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

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

Val-binding模式

  • 新功能:值绑定可以使用一个模式,而不仅仅是一个变量

    • 结果发现变量只是模式的一种,所以我们只是在第1讲中告诉了你一个半真半假的事实

      val p = e
  • 对于从每个类型中获取(所有)部分是非常好的

    • 也可以只获取部分内容(这里没有显示)
  • 通常情况下,把构造函数模式放在val-binding中的风格很差

    • 测试一个变体,如果有不同的变体,则引发异常(如hd, tl, valOf

更好的例子

这是好的风格

  • 尽管我们接下来会再次改进它
  • 语义上与单分支case写表达式相同
fun full_name2 (r : {first:string,middle:string,last:string}) =
    let val {first=x,middle=y,last=z} = r
    in
		x ^ " " ^ y ^ " " ^z
    end

fun sum_triple2 triple =
    let val (x,y,z) = triple 
    in 
        x + y + z 
    end

函数——参数模式

函数参数也可以是一个模式,针对函数调用中的参数进行匹配:

fun f p = e

例子(很好的风格!):

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

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

一种新的方式

  • 对于作业2。
    • 不要使用#字符
    • 不需要写下任何明确的类型

其他

一个函数,它接收一个int*int*int类型的,并返回一个int,即它们的总和:

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

一个接收三个int参数并返回一个int作为其总和的函数:

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

看到区别了吗?(我也没有。)

关于函数的真相

  • 在ML中,每个函数都只需要一个参数(*)

    • “零参数”是指单位模式()与单位值()相匹配
  • 我们所称的多参数函数只是需要一个元组参数的函数,在函数绑定中用元组模式来实现

  • 优雅而灵活的语言设计

  • 实现了在Java中无法做到的可爱而有用的事情,例如:

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

一些类型推理

一种新的方式

  • 对于家庭作业2

    • 不要使用#字符
    • 不需要写下任何明确的类型
  • 这些都是相关的

    • 类型检查器可以使用模式来计算出类型
    • 只用#foo#1,它不能确定”其他什么字段”

为什么没有问题

便于类型检查器确定函数类型:

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

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

在没有明确类型注释的情况下获得错误信息:

(* these versions will not type-check without type annotations because
   the type-checker cannot figure out if there might be other fields *)
fun sum_triple2 (triple : int*int*int) =
	   #1 triple + #2 triple + #3 triple

fun full_name2 (r : {first:string, middle:string,
                    last:string}) =
      #first r ^ " " ^ #middle r ^ " " ^ #last r

意外的多态性

  • 有时类型检查器”比你预期的更聪明”

    • 某些部分的类型可能比你想象的要少

    • 例如:如果你不使用某个东西,那么它可以有任何类型

      (* these functions are polymorphic: type of y can be anything *)
      
      fun partial_sum (x, y, z) = 
          x + z
      
      fun partial_name {first=x, middle=y, last=z} =
          x ^ " " ^ z
  • 这没什么问题!

    • 比你需要的更通用的类型总是可以接受的
    • 当然,前提是你的函数是正确的
    • 下一段对”更通用类型”有更精确的定义

多态类型和相等类型

例子

  • “写一个函数,将两个字符串列表相加”

    fun append (xs,ys) =
       case xs of
           [] => ys
         | x::xs' => x :: append(xs',ys)
  • 你期望string list * string list -> string list

  • 实现是'a list * 'a list -> 'a list

  • 这没什么问题:为什么?

更一般

类型

'a list * 'a list -> 'a list

比以下类型更一般

string list * string list -> string list
  • 它”可以被用作”任何不太通用的类型,例如

    int list * int list -> int list
  • 但它并不比以下类型更通用

    int list * string list -> int list

“更一般”的规则

你(和类型检查器)可以不假思索地应用的简单规则:

一个类型t1比类型t2更通用,如果你能把t1,一致地替换其类型变量,并得到t2

  • 例子:用int * int替换每个'a
  • 例子:用bool替换每个'a,用bool替换每个'b
  • 例子:用bool替换每个'a,用int替换每个'b
  • 例子:用'a替换每个'b,用'a替换每个'a

其他规则

  • 可以将”更一般”的规则与等价的规则结合起来
    • 类型同义词的使用并不重要
    • 字段名的顺序并不重要

例子,给定

type foo = int * int

类型

{quux : 'b, bar : int * 'a, baz : 'b}

比如下更加普遍

{quux : string, bar : foo, baz : string}

这等价于

{bar : int*int, baz : string, quux : string}

相等类型

  • 你也可能看到带有第二个”引号”的类型变量
    • 例如:''a list * ''a -> bool
  • 这些是使用 = 运算符产生的”相等类型”。
    • = 运算符适用于很多类型:int、string、tuples包含所有相等类型,…
    • 但不是所有的类型:函数类型、real,…
  • 更一般的规则是完全一样的,除了你必须用可与=一起使用的类型来替换相等类型变量
    • ML的一个”奇怪”的特征,因为=是特殊的

例子

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

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

嵌套模式

嵌套模式

  • 我们可以随心所欲地嵌套模式
    • 就像我们可以随心所欲地嵌套表达式一样
    • 通常可以避免难于阅读、字数繁多的嵌套case表达式
  • 所以模式匹配的全部含义是将模式与”相同形状”的值进行比较,并将变量绑定到”正确的部分”
    • 更加精确的递归定义将在例子之后出现

有用的例子:zip/unzip 3 lists

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

(* and the inverse *)
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

更多嵌套模式

风格

  • 嵌套模式可以带来非常优雅、简洁的代码
    • 如果嵌套模式更简单,则避免嵌套的case表达式,并避免不必要的分支或let表达式
      • 例如:unzip3和nondecrease
    • 一个常见的习惯是针对一个数据类型的元组进行匹配,以比较它们
      • 例子:zip3multsign
  • 通配符是很好的风格:当你不需要数据时,用它们代替变量。
    • 例子:lenmultsign

精确嵌套模式

(大部分的)完整定义

模式匹配的语义需要一个模式p和一个值v,并决定

  • (1)它是否匹配,
  • (2)如果匹配,将引入什么变量绑定。

由于模式可以嵌套,该定义是优雅的递归,每一种模式都有单独的规则。其中一些规则是:

  • 如果p是变量x,则匹配成功,x被绑定到v
  • 如果p_,则匹配成功,不引入绑定
  • 如果p(p1,...,pn)v(v1,...,vn),当且仅当p1匹配v1,…,pn匹配vn时,匹配成功。绑定是来自子匹配的所有绑定的结合体
  • 如果pC p1,如果vC v1(即同一个构造函数)并且p1匹配v1,则匹配成功。
  • (还有其他几种类似的模式形式)

例子

  • 模式a::b::c::d匹配所有>=3个元素的列表
  • 模式a::b::c:[]匹配所有有3个元素的列表
  • 模式((a,b),(c,d))::e匹配所有非空的成对pair的列表

可选:函数模式

更多的模式匹配

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

fun old_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 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)

没有比这更强大的了

一般的

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

可以写成

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

如果您愿意(假设x未在任何分支中使用)。

异常

异常

异常绑定引入了一种新的异常类型

exception MyFirstException
exception MySecondException of int * int

raise原语会引发(又称抛出)一个异常。

raise MyFirstException
raise (MySecondException(7,9))

一个handle表达式可以处理(又称捕获)一个异常

  • 如果不匹配,异常继续传播
e1 handle MyFirstException => e2
e1 handle MySecondException(x,y) => e2

实际上

异常很像数据类型的构造函数…

  • 声明一个异常会增加一个exn类型的构造函数
  • 可以在任何地方传递exn的值(例如,函数参数)。
    • 这样做并不常见,但可能很有用
  • handle可以有多个分支,并有exn类型的模式

尾递归

递归

现在应该能适应递归了。

  • 不比使用循环更难
  • 通常比循环容易得多
    • 当处理树时(例如,评估一个算术表达式)
    • 像追加列表的例子
    • 即使对局部变量也避免了突变
  • 现在:
    • 如何推理递归的效率
    • 尾递归的重要性
    • 使用累加器来实现尾递归
    • [这里没有新的语言特征]

调用堆栈

当一个程序运行时,有一个已经开始但尚未返回的函数调用堆栈

  • 调用函数f会将f的实例push到栈上
  • 当对f的调用结束时,它(f的实例)从栈中弹出

这些堆栈框架存储了一些信息,如局部变量的值和函数中的”剩余工作”。

由于递归的原因,多个栈帧可能是对同一个函数的调用。

例子

fun fact n = if n=0 then 1 else n*fact(n-1)
val x = fact 3

修订后的例子

仍然是递归,更复杂,但递归调用的结果是调用者的结果(没有剩余的乘法)。

fun fact2 n =
    let fun aux(n,acc) = if n=0 then acc else aux(n-1,acc*n)
    in
        aux(n,1)
    end

调用栈

一个优化

没有必要为了得到一个被调用者的结果而保留一个栈帧,并在没有任何进一步评估的情况下返回它。ML在编译器中识别了这些尾部调用,并对它们进行了不同的处理。

  • 在调用前弹出调用者,允许被调用者重新使用相同的堆栈空间
  • (与其他优化一起,)与循环一样高效

有理由认为所有函数式语言的实现都会进行尾部调用优化

实际发生的

累加器(Accumulators)

尾递归的寓意

  • 在合理优雅、可行和重要的情况下,将函数重写为尾递归会更有效率
    • 尾递归:递归调用是尾部调用
  • 有一种方法可以经常指导这种转换
    • 创建一个接收累加器的辅助函数
    • 旧的基本情况为初始累加器
    • 新的基本情况为最终累加器

例1

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

例2

fun rev1 xs =
   case xs of
       [] => []
     | x::xs' => (rev1 xs') @ [x]

fun rev2 xs =
    let fun aux(xs,acc) =
            case xs of
                [] => acc
              | x::xs' => aux(xs', x::acc)
    in
        aux(xs,[])
    end

分析

  • 对于factsum,尾递归更快,但两种方式都是线性时间
  • 非尾递归rev是二次时间复杂度,因为每次递归调用都使用append,它必须遍历第一个列表
    • 而1+2+…+(length-1)几乎是length*length/2。
    • 道理:小心列表追加,特别是在外部递归中。
  • 尾递归优点是恒定时间(和快速),所以累加器版本更好。

尾递归:视角和定义

总是尾递归?

  • 当然,在某些情况下,递归函数不能在恒定的空间内进行计算
  • 最明显的例子是处理树的函数
  • 在这些情况下,自然递归的方法才是正确的选择
    • 你可以让一个递归调用成为一个尾部调用,但很少值得这样复杂化
  • 要小心过早优化
    • 喜欢清晰、简明的代码
    • 但如果输入可能很大,则要减少空间的使用

什么是尾部调用

  • 通常”没有什么留给调用者做”的直觉就足够了
    • 如果f x的结果是包围函数体的”直接结果”,那么f x就是一个尾部调用
  • 但我们可以递归地定义”尾部位置”
    • 那么”尾部调用”就是”尾部位置”的函数调用

精确的定义

尾部调用是指在尾部位置的函数调用:

  • 如果一个表达式不在尾部位置,那么就没有子表达式在尾部位置
  • fun f p = e中,主体e在尾部位置
  • 如果if e1 then e2 else e3在尾部位置,那么e2e3都在尾部位置(但e1不在)
    • (对于case表达式也类似)
  • 如果let b1 ... bn in e end在尾部位置,那么e就在尾部位置(但没有绑定表达式在尾部位置)
  • 函数调用参数e1 e2不在尾部位置