APartSML(4)——高阶函数和闭包

Posted Dec 30, 2024 Updated Jan 22, 2025

By ZoeyWang

24 min read

1.terms

first-class functions：一阶函数，可以被计算，传递和存储的函数，和值一样
high-order functions：高阶函数，可以读取和返回其它函数的函数
function closures：函数闭包，可以使用在函数外部定义的变量，让一阶函数更有用
functional programming：函数式编程，主要特征是大部分场景下不使用可变数据，把函数当成值使用

2.take functions as arguments

一阶函数比较普遍的用法是把他们当作参数传递给其它函数，下面函数中，f是一个函数，n_times代表执行f(x)函数n次

  
fun n_times(f,n,x) =
    if n=0
    then x
    else f(n_times(f,n-1,x));

- use "fun_arg.sml";
[opening fun_arg.sml]
val n_times = fn : ('a -> 'a) * int * 'a -> 'a

这样写的好处是可以重复利用代码，n_times不关心具体的f(x)，因此可以自定义各种f，将其传入n_times函数中，可以实现f的n次计算

  
fun double x=x+x;
val x1 = n_times(double, 4, 7);
fun increment x=x+1;
val x2 = n_times(increment,4,7);
val x3 = n_times(tl,2,[4,8,12,16]);

- use "fun_arg.sml";
[opening fun_arg.sml]
val double = fn : int -> int
val x1 = 112 : int
val increment = fn : int -> int
val x2 = 11 : int
val x3 = [12,16] : int list

一旦定义了这种抽象的函数，可以后面不断的扩展增加新的使用，比如定义一个新函数triple是翻3倍，那么就可以通过使用n_times实现函数triple_n_times，代表翻n次3倍

  
fun triple x=3*x;
fun triple_n_times(n,x) = n_times(triple,n,x);

- use "fun_arg.sml";
[opening fun_arg.sml]
val triple = fn : int -> int
val triple_n_times = fn : int * int -> int

3.polymorphic types and functions as arg

在上面的例子中，n_times函数的类型是('a -> 'a) * int * 'a -> 'a，这说明第一个和第三个参数的类型可以是多种，只需要保持两者类型相同即可，这称为参数多态（parametric polymorphism）或者泛型（generic types）。高阶函数通常是多态的，但是也有例外

存在一些高阶函数不是多态的：类型固定

  
fun time_until_zero(f,x) =
    if x=0
    then 0
    else 1+time_until_zero(f,f x);

val time_until_zero = fn : (int -> int) * int -> int

存在一些多态的函数不是高阶的：列表的类型可以是int list或string list

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

val len = fn : 'a list -> int

4.Anonymous functions

在第3节中定义一个新函数triple是翻3倍，使用n_times实现函数triple_n_times，代表翻n次3倍，实际上这个代码是可以优化写法的

  
fun triple x=3*x;
fun triple_n_times(n,x) = n_times(triple,n,x);

（1）不需要在最顶部就定义好triple函数，只需要在使用时定义即可，使用let expression表达式来局部定义triple函数

  
fun triple_n_times(n,x) =
    let fun triple x = 3 * x
    in
    n_times(triple, n, x)
    end;

（2）triple函数实际上只是n_times函数的第一个参数，给第一个参数定义triple函数即可

  
fun triple_n_time(n,x) =
    n_times((let fun triple x = 3 * x in triple end), n, x);

（3）这样的写法实际上是多余的，因为我们不需要知道函数名称，只需要传入一个函数即可

  
fun triple_n_time(n,x) =
    n_times((fn y=> 3*y), n, x);

上述函数中定义了一个匿名函数（anonymous function）fn y=> 3*y，传入参数y，函数体为3*y，这个函数没有名称，是匿名的。使用匿名函数作为其它函数的传参是比较普遍的用法，匿名函数可以看成就是一个值value，不需要使用fun绑定，缺点是不能用于递归。fun bingding实际上也是一个syntactic sugar，由于支持了递归，因此很重要

  
fun increment x=x+1;
val increment = fn x=> x+1;

- use "anony.sml";
[opening anony.sml]
val increment = fn : int -> int
val it = () : unit

使用匿名函数是比较方便的，但是注意不能过度使用，用一个不必要的函数包装(function wrapping)，比如fn y=> tl y可以直接写成tl

  
fun nth_tail_poor(n,x) =
    n_times((fn y=> tl y),n,x);

fun nth_tail_poor(n,x) =
    n_times(tl,n,x);

5.maps and filters

对列表操作有两个非常有用的高阶函数

（1）map函数：对list中的每个元素都应用某个函数，ML标准库中有提供函数List.map。

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

fun increment x=x+1;
val x1 = map(increment, [1,2,3,4]);
val x2 = map(hd, [[1,2],[3,4,5]]);

- use "map_filter.sml";
[opening map_filter.sml]
val map = fn : ('a -> 'b) * 'a list -> 'b list
val increment = fn : int -> int
val x1 = [2,3,4,5] : int list
val x2 = [1,3] : int list
val it = () : unit

用map的定义是一种非常重要的写法，比较常规的通过递归来对每个元素执行特定操作，但是这个任务可以分成两个部：map实现者inplementer负责遍历递归数据，map代理client负责对每个数据进行操作

（2）filter函数：只保留list中满足某个函数要求的元素

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

fun get_all_even_snd xs = filter((fn v => v mod 2 = 0), xs);

- use "map_filter.sml";
[opening map_filter.sml]
val filter = fn : ('a -> bool) * 'a list -> 'a list
val get_all_even_snd = fn : int list -> int list
- get_all_even_snd [1,2,3,4];
val it = [2,4] : int list

6.returning functions

函数也能返回函数

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

（* 类型等同于(int -> bool) -> (int -> int) *)
val double_or_triple = fn : (int -> bool) -> int -> int

函数也可以在自定义数据结构中使用，不仅仅是list

  
fun true_of_all_constants(f,e) =
    case e of
    Constant i => f i
  | Negate e1 => true_of_all_constants(f, e1)
  | Add(e1, e2) => true_of_all_constants(f, e1) andalso true_of_all_constants(f, e2)
  | Multiply(e1,e2) => true_of_all_constants(f, e1) andalso true_of_all_constants(f, e2);

fun is_even v =
    (v mod 2 = 0)

fun all_even e = true_of_all_constants(is_even, e);

7.lexical scope

目前为此学习到的函数都是封闭的，即函数内部只使用函数的参数和任何局部定义的变量，实际上函数可以使用范围内的任何bindings，根据作用域不同主要分成：

（1）词法作用域lexical scope：函数体在被定义的环境里评估，而不是被调用的环境

  
val x = 1;
fun f y = x+y;
val x = 2;
val y = 3;
val z = f(x+y);

- use "lexical.sml";
[opening lexical.sml]
val z = 6 : int

函数f被定义时的环境中，x值为1，因此即便后来重新绑定了x，最后结果也是1+y

（2）动态作用域dynamic scope：函数体在被调用的环境里评估，与词法范围相反

词法作用域：变量查找基于函数定义时的作用域链，查找顺序是静态确定的，查找路径依赖于代码结构。
动态作用域：变量查找基于当前调用栈中的作用域链，查找路径依赖于函数调用的顺序和调用栈的上下文。

在动态范围这种，最后z的取值会是2+3+2=7

8.environment and closures

函数都是值，但是这种说法不是很明确。函数值有两个部分：

code part：函数的代码，是绝对的
environment part：创建函数时的当前环境

每次调用，代码部分需要使用环境部分来评估值，code+environment组合一起称为函数闭包（function closure）。使用必包的原因是函数代码可能会有自由变量，即在代码外部绑定的变量，闭包在环境中携带了作用域里的bindings，这样调用的时候在给订参数后就可以生成值，函数fun f y = x+y的闭包环境部分x=1，因此任何对这个闭包调用的结果都是y+1

  
val x = 1;
fun f y =
    let
        val x = y+1
    in
        fn z => x+y+z
    end;
val x = 3;
val g = f 4;
val y = 5;
val z = g 6;

虽然函数f定义时x=1，但是let expression覆盖了x，因此函数f的闭包是fn z => 2y+z+1，对于val g = f 4，返回的函数闭包一定是9+z，因此最后的z值为15.

9. why lexical scope

多数编程语言里词法作用域lexical scope，因为使用动态作用域会产生一些问题

词法作用域可以修改局部变量的名称而不会影响全局

比如在8节的列子中，局部变量x换成q，在词法作用域下无影响。但是如果是动态作用域，调用g 6时会去查找q，但是q不在调用时的环境里

  
fun f y =
    let
        val q = y+1
    in
        fn z => q+y+z
    end;

很少语言会使用dynamic scope，比较常见的场景是：异常捕捉exception handling，当异常发生的时候，需要去查找使用哪个处理异常，而这是通过查找动态调用栈实现的。

10.closure example

前面提到的map和filter函数实际上都是基于闭包实现的。比如allGreaterThan函数中，n在定义的时候传入，后面调用filter函数会一直使用这个n

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


fun allGreaterThanSeven xs = filter(fn x => x > 7, xs);
fun allGreaterThan (xs, n) = filter(fn x => x > n, xs);

fun allShorterThan(xs, s) =
    let
    val i = String.size s
    in
    filter(fn x => String.size x < i, xs)
    end;

- use "closure.sml";
[opening closure.sml]
val filter = fn : ('a -> bool) * 'a list -> 'a list
val allGreaterThanSeven = fn : int list -> int list
val allGreaterThan = fn : int list * int -> int list
val allShorterThan = fn : string list * string -> string list
val it = () : unit

11.closure idiom: fold

除了map和filter，还有一些其他的高阶函数，比如fold，也可能成为reduce或者inject

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

fold函数传入初始值acc，然后对列表中的每个元素，使用函数f来结合acc和该元素，是一种迭代方式，比如求列表的元素和

  
fun sum_list foo = fold(fn (x,y) => x+y, 0, foo);

- sum_list([1,2,3]);
val it = 6 : int

计算元素取值在特定范围内的数量

  
fun number_in_range(xs, lo, li) =
    fold(fn (x,y) => x + (if y>=lo andalso y<=li then 1 else 0),0,xs);

- number_in_range([1,2,3],1,2);
val it = 2 : int

判断元素的长度是不是都小于指定长度

  
fun are_all_shorter(xs,s) =
    let
        val length = String.size s
    in
        fold((fn (x,y) => x andalso String.size y < length), true, xs)
    end;

- are_all_shorter(["a","ae","aad"],"q");
val it = false : bool

12.closure idiom: combine

有时间编程会需要很多函数，组合函数可以把多个函数连接起来

  
fun compose (f,g) = fn x => f(g x);
val compose = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

compose函数输入两个函数f和g，返回一个函数，对其参数先执行g，然后执行f，比如对一个值取绝对值，然后变成整数，再取平方。

infix operator：ML定义了infix运算符o，作为函数组合

  
fun sqrt_of_abs i = Math.sqrt(Real.fromInt(abs i));
fun sqrt_of_abs i = (Math.sqrt o Real.fromInt o abs) i;
val sqrt_of_abs = Math.sqrt o Real.fromInt o abs;

pipeline operator：|>，从左到右的组合写法

infix operator是从右到左执行函数，更方便的写法是希望还原对参数的执行过程，从左到右

  
infix |>
fun x |> f = f x
fun sqrt_of_abs i = i |> abs |> Real.fromInt |> Math.sqrt

pipeline operator在F#编程中比较普遍使用

13.closure idiom:curry

柯理化curry：让一个函数接受第一个概念参数，并返回另一个接受第二个概念参数的函数，依此类推。

比如判断三个元素是否正序，通常写法是输入参数为一个tuple，也可柯理化处理，依次读取参数，输入x，返回一个函数，这个函数输入y，返回另一个函数，这个函数输入z，返回bool值，这样就可以不必一次性输入所有的x,y,z

  
(* 普通函数 *)
fun sorted3_tupled (x,y,z) = z >= y andalso y >= x;
(* 柯理化函数 *)
val sorted3 = fn x => fn y => fn z => z >= y andalso y >= x;
fun sorted3_curry x y z = x >= y andalso y >= x;

- use "curry.sml";
[opening curry.sml]
val sorted3_tupled = fn : int * int * int -> bool
val sorted3 = fn : int -> int -> int -> bool
val sorted3_curry = fn : int -> int -> 'a -> bool

偏应用partial application：由于柯理化是依次读取参数，因此可以对一个偏函数先只传入概念参数的子集，然后返回一个函数，等待剩下的参数传入

用柯理化的方式来写fold函数，可以只传入f和acc，得到函数sum2，再传入任意xs

  
fun fold f acc xs =
    case xs of
    [] => acc
      | x::xs' => fold f (f(acc,x)) xs';
val sum2 = fold (fn (x,y) => x+y) 0;

- use "curry.sml";
[opening curry.sml]
val fold = fn : ('a * 'b -> 'a) -> 'a -> 'b list -> 'a
val sum2 = fn : int list -> int

由于偏函数的便利性，ML标准库中的许多迭代器使用currying函数作为第一个参数

  
val map = List.map;
val filter = List.filter;
val foldl = List.foldl;

- use "curry.sml";
[opening curry.sml]
val map = fn : ('a -> 'b) -> 'a list -> 'b list
val filter = fn : ('a -> bool) -> 'a list -> 'a list
val foldl = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

如果已经存在一个偏函数，但是参数的顺序不是你想进行偏应用的顺序，或者想把偏函数写成使用元组，想把元组写成偏函数，可以通过combine函数来实现

  
fun other_curry2 f x y = f y x;
fun curry f x y = f(x,y);
fun uncurry f (x,y) = f x y;

- use "curry.sml";
[opening curry.sml]
val other_curry2 = fn : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c
val curry = fn : ('a * 'b -> 'c) -> 'a -> 'b -> 'c
val uncurry = fn : ('a -> 'b -> 'c) -> 'a * 'b -> 'c

无论是tuple还是curry，性能差别不是很大，重点在于实现的功能

14.ML reference

之前讲的ML中的bingdings大多是不可变的，ML也支持可变性，在函数式编程语言中，当你想要更新一些东西的状态，这样所有使用者都可以看到这个变化时，可以通过创建引用reference支持可变

r = ref e：创建引用，初始值为e
!r：获取引用的值
r := e：修改引用的值
t ref：引用类型

  
val x = ref 0; 
val x2 = x; (* x和x2指向相同引用 *)
val x3 = ref 0;

val y = (!x) + 1; (* 值为1 *)
val _ = x := (!x) + 7; (* 引用x的值修改为7 *)
val z1 = !x;（* z1=7 *)
val z2 = !x2;（* z2=7 *)
val z3 = !x3;（* z3=0 *)

- use "mutation.sml";
[opening mutation.sml]
val x = ref 0 : int ref
val x2 = ref 0 : int ref
val x3 = ref 0 : int ref
val y = 1 : int
val z1 = 7 : int
val z2 = 7 : int
val z3 = 0 : int
val it = () : unit

15.closure idiom:callback

回调callback：当事件发生时被调用的函数

比如当用户点击某个button，就要调用这个button执行的函数。用一个reference来存储回调列表，当一个事件发生时，函数onEvent就会被调用，然后回调列表里的每个callback也都会被调用，onKeyEvent对一个callback被调用时所需要的额外数据类型没有限制

  
val cbs:(int -> unit) list ref = ref [];
fun onKeyEvent f = cbs := f::(!cbs);
fun onEvent i =
    let fun loop fs =
        case fs of
            [] => ()
          | f::fs' => (f i; loop fs')
    in
        loop (!cbs)
    end;

- use "callback.sml";
[opening callback.sml]
val cbs = ref [] : (int -> unit) list ref
val onKeyEvent = fn : (int -> unit) -> unit
val onEvent = fn : int -> unit
val it = () : unit

16.总结

没有最好的语言，只有最适合的语言
可以不用了解每种语言的语法和特征，但是要知道编程语言的基本概念模型
特定语言的语法特征可以帮助成为更好的编程者
大多数语言都是有共性的，但是也有不同的原语和多样性，编程的时候不应该只是想到实现就行，而是去针对每种语言寻找更优雅的编程方式

Coursera, ProgrammingLanguage

programming

This post is licensed under CC BY 4.0 by the author.