Coursera - Programming Language - 课程笔记 - Week 4

Week 4

一级函数 First-Class Functions

• 函数式编程的意义：
  • 在绝大多数情况下避免异变的发生
  • 将函数视为一种值来使用
  • 鼓励递归的代码风格以及递归的数据结构
  • 接近数学定义的代码风格
  • 使用“懒汉方式”编程
• 函数式语言，没有确切定义，可以认为是一切简化函数式编程的语言
• 一级函数：可以被当作值使用的函数
  • 函数也可以作为值，并视其为值用于各种场景
  • 大多数的使用情况是作为另外一个函数的参数或者结果
  • 上述情况下，使用一级函数的函数称为高阶函数，是一种分解常规函数的有效方法
• 函数闭包：能够使用函数定义外部绑定的函数

函数作为参数 Functions as Arguments

• 将函数作为另一个函数的参数，并在后面这个函数的函数体中被调用
• 可以是一种比较优雅的策略，将多个类似的实现的公共部分提取出来，只需要指定参数，就可以一次调用可以获取不同的实现

多型类型 Polymorphic Types

• 高阶函数通常十分泛化和重用性以至于其具有多型类型
• 但是有一些高阶函数是不多型的
• 同时，存在一些一阶函数是多型的
• 当完成一个函数的声明时，应当仔细思考其类型（参数类型）

匿名函数 Anonymous Functions

• 一种不使用fun进行绑定的函数定义
• 简化思路：我们只需要一个函数的逻辑，并不需要对他进行额外绑定，只要确保我们用它的时候出现即可
• 函数表达式，定义了一个函数，但是不是绑定，只是一个表达式，其评估值为函数
• fn arg => body
• 这个表达式中的函数内容没有名字（因为没有发生绑定）
• 这样，我们就可以在只需要作为参数的函数的使用上采用这种表达式方式（高阶函数的参数）
• 但是对于一个递归函数，则不能使用匿名函数
• 如果没有递归的问题，那么函数绑定实际上使变量绑定和fn表达式的语法糖，即fun name arg = body可以写作val var = fn arg => body

不必要的函数封装 Unnecessary Function Wrapping

• 一些不应当使用匿名函数导致代码风格很差
• 比如对一些既有的库函数，我们不应该在封装一次去使用，如fun rev xs = List.rev xs，更不应该使用fn表达式val rev = fn xs => List.rev xs，这些都实际上加入了不必要的封装（甚至以为额外调用一次函数导致性能上的冗余），而应当直接绑定到对应函数fun rev = List.rev，没有过多封装，只是加了一个“别名”，也没有多一步的调用

映射和过滤器 Map and Filter

• map是一个高阶函数，其输入一个函数和一个列表，并输出一个列表，输出元素为被函数处理过的对应输入元素

fun map (f,xs) = 
	case xs of
		[] => []
	  | x :: xs' => (f x) :: (map(f, xs')) 

• val map : ('a -> 'b) * 'a list -> 'b list

• map函数是一个明星函数

  • 名称标准化
  • 有效，简洁，小物件完成大任务
  • 标准库中有一个相同功能的函数List.map（使用柯里化方法）

• filter函数同样是一个明星高阶函数，同样以一个函数和一个列表为输入，但是输出一个同序子集，参数函数要求返回布尔值，过滤掉那些使参数函数输出false的元素

fun filter (f,xs) =
	case xs of
        [] => []
      | x::xs’ =>   if f x
        			then x::(filter(f,xs’))
                    else filter(f,xs’)

• val filter : ('a -> bool) * 'a list -> 'a list
• 同样是一个明星函数
  • 只要需要过滤器就可以使用之
  • 标准库中有List.filter（同样使用柯里化方法）

生成优先主题 Generalizing Prior Topics

• 一级函数的作用

  • 将一个函数作为另一个函数的参数
  • 在一个函数中处理一个列表
  • 将多个函数作为参数传递
  • 将函数放在数据结构里面（元组，记录等）
  • 能够作为结果返回
  • 完成能够处理自定义数据结构的高阶函数

• 通律：函数是一级值

fun double_or_triple f =
    if f 7
    then fn x => 2*x
    else fn x => 3*x

• 上述高级函数的类型为(int -> bool) -> (int -> int)
• 但是本身类型转换符有优先级，因此在REPL中的输出结果为(int -> bool) -> int -> int
• 断言（predicate）：传进一个函数，用来评估出一个布尔值

词法作用域 Lexical Scope

• 函数体可以使用该函数定义的作用域内的所有绑定

• 函数如何在一个已经不存在的就环境中进行评估：函数的实现

• 函数的语义内容：

  • 函数有两个值：代码本身和定义时的环境，二者统称为一个闭包
  • 可以认为闭包是一个“对”，但我们不允许单独访问其中一个片段
  • 函数的代码之评估在其对应的环境中进行

• 函数调用时的环境并不重要，我们应该关注函数定义时的环境，这对于一级函数同样适用

• 词法作用域和动态作用域

  • 词法作用域：使用函数定义时的环境
  • 动态作用域：使用函数调用时的环境

• 更应该使用词法作用域的原因：

  • 函数推断并不依赖于使用的变量名（方便地修改变量名以及移去不起作用的代码）
  • 函数能够在定义时进行类型检查和推断
  • 闭包可以存储其需要的数据

• 解决一个异常更像是一个动态作用域（只管里面抛出了什么异常，跟之前的定义没有任何关系）

闭包与重计算 Closures and Recomputation

• 三个有趣的事实：
  • 函数体直到其被调用时才会被评估
  • 函数体每次被调用时都会被评估
  • 而变量的绑定在其绑定被评估时，其表达式便被评估，而不是使用时
• 使用闭包可以避免一些不依赖于函数参数的重复计算
• 重复使用且无关参数的值可以被保存在函数闭包中

叠层 Fold

• 一个迭代于可递归数据结构的迭代器
• 重复对acc施以函数f以累加当前为止的acc
• fold(f, acc, [x1, x2, x3, x4])
• 迭代器的好处：向环境中传递任何的私有数据，同时又不必知晓数据或者数据的类型（泛化）

组合函数 Combing Functions

• 将函数组合到一起，符合数学计算的习惯
• 可以使用嵌套方法，同样地也可以使用符号o，就像在数学中那样，f(g(x))可以表示为(f o g)(x)
• 和数学中的过程类似，函数的作用顺序从右到左
• 为了阅读方便，也可以采用类似F#中的管道符号|>实现从左到右，但是在ML需要自己定义
  • 自定义infix运算符infix |>，在使用函数绑定确定运算符作用

柯里化 Currying

• 一种处理概念上多个参数函数的另一种方法
• 传一个参数进去，返回一个函数来处理另外一个参数
• 按照定义，柯里化的多参数函数的调用很容易变成((f x)y)z，很奇怪也很麻烦
• ML语法糖：
  • e1 e2 e3 e4，通常表示((((e1 e2) e3) e4)
  • 那么上面的调用就可以改成f x y z
  • 可以用这种方式直接定义一个柯里化函数（参数空格隔开）

部分应用 Partial Application

• 使用柯里化定义函数时，如果调用者提供太少的参数，我们会得到一个“等待剩余参数”的闭包
• 相比于对柯里化函数进行在此封装并传入特定参数来表现这种“等待机制”，这种方法更简洁，代码更短（避免了不必要的封装）
• 迭代器的相关函数更多地使用这种方式进行迭代
• 如果将部分应用用于创建一个多型函数，那么会因为值限制（value restriction）而无法起作用，此时必须直接指明参数类型 或者给出完成参数内容

柯里化封装 Currying Wrapup

• 解决一些元组参数函数和柯里化函数之间的转换等奇怪的问题（真的很奇怪）
• 元组化转柯里化fun curry f x y = f(x, y)
• 柯里化转元组化fun uncurry f (x, y) = f x y
• 调整参数顺序fun other_curry f x y = f y x
• 实际上，SML使用柯里化函数会更慢，但实际上在现代语言中使用柯里化函数会更快

可异变引用 Mutable Reference

• 一些情况下我们正是需要不断更新的内容，因此我们需要可异变数据结构
• ML具有一类完全独立的可异变数据结构：引用
• 新类型t ref
• 创建并赋初值ref e
• 更新内容e1 := e2
• 读取内容!e
• 允许出现别名（两个引用指向同一个内容）
• 不能直接对引用进行非引用类型的操作，必须先提取内容，再对内容进行操作
• 引用是一个一类值
• 引用只对应（包含）一个数据域，就算是对应了一个元组，其指向的是元组而不是元组的值

回调 Callbacks

• 函数库包含一个晚一些才会使用（当一些事件发生）的函数
• 将某个函数传到一个库函数内，在某个事件发生后调用之，这个过程称为回调
• 一个库可能接受多种回调，而不同的回调可能需要不同类型的不同私有数据，幸好在ML中函数类型和内部环境中的绑定类型没有必然联系
• 可异变的状态：可能需要一个跟踪“已注册回调函数“的状态量
• 对于需要的数据，应当确保其在闭包的环境中

标准库文档 Standard-Library Documentation

• 设计一门语言时，应将两类内容放入标准库
  • 不能依靠当前这门语言完成的事情（读文件，设置一个计时器等）
  • 太过于普遍，以致于需要一个标准实现的内容
• 文档被组织成有签名的结构体中（ML的模块系统中）
• REPL可以查询相关文档

抽象数据类型与闭包 Abstract Data Types with Closures

• 使用闭包实现抽象数据类型
  • 将多个函数放到一个记录中
  • 这些函数可以共享相同的私有数据
  • 私有数据可以可异变，也可以不可异变
  • 与OOP有着很做的相似性

没有闭包？ Without Closure