函数式编程

函数式编程是一种编程典范, 比起指令式(过程式)编程的复杂执行过程, 函数式编程更加强调程序执行的结果, 倡导利用若干简单的执行单元让计算结果不断渐进, 仔细定义每个运算的输入, 以及每个运算返回的内容, 逐层推导复杂的运算, 并且避免使用程序状态以及易变对象.

以一个多项式求值 a * (b + c) 举例 (假设存在 add 和 mul 方法):

指令式(过程式)编程:

x = add(b, c)
y = mul(a, x)

函数式编程:

mul(a, add(b, c))

解释函数式代码的步骤是 求值-应用 这两大步骤的轮转: 为了对一个组合式求值, 例如: mul(a, add(b, c)), 必须先对组合式里的每个元素执行求值过程, 然后将求值的结果应用于组合式, 而每个元素的内部又可能包含新的求值过程, 例如 mul(a, add(b, sub(c, d))), 所以, 在规则性质上 (即将 mul, add, sub 这些不同的函数均视为相同的抽象求值过程), 这一解释过程其实是递归的:

在函数式思想中, 只有纯的、没有副作用的函数, 才是合格的函数.

• 副作用指当调用函数时, 除了返回函数值之外, 还对主调用函数产生附加的影响, 例如修改全局变量 (函数外的变量) 或修改参数.
• 纯函数是指函数与外界交换数据只有一个唯一渠道——参数和返回值, 如果函数从外界获取数据, 或者向外部输出数据 (比如读取全局变量, 修改全局变量), 那么, 该函数就是非纯函数.

Lisp

序对

(cons x y) 构造一个 [x, y] 序对

(car p) 选择序对 p 的首元素

(cdr p) 选择序对 p 的尾元素

元素可以是任意数据, 包括另一个序对.

表

如果我们想要表示 [1, 2, 3, 4] 这个数据, 使用序对, 会有很多种可能, 例如:

((1, 2), (3, 4))

(1, (2, 3), 4))

因此就需要一种约定来进行规范, 这就是表, 即序对的序列, 它使用下面这种试来构建多元素数据:

即:

(cons 1
    (cons 2
        (cons 3
            (cons 4 ()))))  ; null? 可以判断序对是否为空 ()

但是如果每次构造表都要写一堆 cons 是个很麻烦的事, 所以 lisp 提供了 list 函数: (list 1 2 3 4).

虽然 list 很方便, 但本质上, 它只是一个语法糖, 用来简便地书写嵌套的 cons.

变量

let (局部)

let 可以一次对多个变量赋值, 但变量只能在 let 的子域中使用.

(let ((var1 exp1) (var2 exp2) ... (varn expn))
    exps)

例如:

(let ((a 1) (b 2) (c (+ 5 3)))
    (+ a (* b c)))

define (全局)

define 一次只能对一个变量赋值, 变量可在与 define 同一级的域中使用.

(define num 10)
num ; => 10

(define sum (+ 10 20))
sum ; => 30

数据的不变性

高级语言中, 变量是一块内存区域的标识, 可以通过修改这个内存区域的存储内容来修改变量的值;

而在 Lisp 家族中, 变量用于绑定常量与函数. 虽然也可以重定义一个变量, 但这只是让变量换了一个绑定而已.

(define a 1)
a ; => 1

(define l (cons a 2))
l ; => (1 . 2)

(define a 3)
a ; => 3

l ; => (1 . 2)

函数

(define square (lambda (x) (* x x)))

; 这是通常的写法, 但本质还是上面那种, 只是个语法糖
(define (square x) (* x x))

(square 10) -> 100

(define (sum) (+ 10 20)) 无参函数

分支

(define (abs x)
    (if (< x 0)
        (- x)
        x))

(define (abs x)
    (cond
        ((< x 0) (- x))
        ((= x 0) 0)
        ((> x 0) x)))

(define (abs x)
    (cond
        ((< x 0) (- x))
        ((= x 0) 0)
        (else x)))

cond 有点类似 switch

递归/尾递归

递归其实是延迟运算, 先分解问题到最小粒度, 计算小问题再将结果向上传递, 最终归并解决原始问题.

而尾递归是迭代性质的, 即分解问题的过程中直接计算出结果, 并将结果直接应用于下一次计算, 问题分解完了结果也就出来了. (感觉高级语言中的循环迭代, 就像是尾递归的语法糖).

加法 (1+ -1+ 是内建操作)

; 递归
(define (+ x y)
    (cond
        ((= x 0) y)
        (else (1+ (-1+ x) y))))

; 迭代 (尾递归)
(define (+ x y)
    (cond
        ((= x 0) y)
        (else (+ (-1+ x) (1+ y)))))

斐波那契数列

; 递归
(define (fib n)
    (cond
        ((< n 2) n)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; 迭代 (尾递归), 这也展示出了递归优化的一般模式 -- 引入一个内部函数来累积结果
(define (fiba n)
    (define (fib-iter a b count)
        (if (= count 0)
            b
            (fib-iter (+ a b) a (- count 1))))
    (fib-iter 1 0 n))

高阶抽象和公共模式

以下内容中的模块均指函数.

高阶抽象, 是至少满足下列一个条件的函数:

• 接受一个或多个函数作为输入
• 输出一个函数

公共模式: 提取不同功能中各模块的组合方式, 注意, 这和模块的具体含义无关, 提取的是模块间的 组合方式. 一般实现公共模式时, 需要用到高阶抽象.

; 从 a 加到 b
(define (sum-int a b)
    (cond
        ((> a b) 0)
        (else (+ a (sum-int (1+ a) b)))))

; 从 a 的平方加到 b 的平方
(define (sum-sq a b)
    (cond
        ((> a b) 0)
        (else (+ (sq a) (sum-sq (1+ a) b)))))

; 从 a 间隔 2 加到 b
(define (sum-interval a b)
    (cond
        ((> a b) 0)
        (else (+ a (sum-interval (+ a 2) b)))))

从以上过程提取公共模式如下:

(define (<name> a b)
    (cond
        ((> a b) 0)
        (else (+ (<term> a)
                 (<name> (<next> a) b)))))

开始重构:

; 高阶抽象, 即公共模式的过程
(define (sum term a next b)
    (cond
        ((> a b) 0)
        (else (+ (term a)
                 (sum term (next a) next b)))))

(define (sum-int a b)
    (define (term x) x)
    (define (next x) (1+ x))
    (sum term a next b))

(define (sum-sq a b)
    (define (term x) (sq a))
    (define (next x) (1+ x))
    (sum term a next b))

高阶抽象有点类似 OOP 的多态/接口, 公共模式则有点像模板方法模式.

所以将问题拆分成尽可能多的模块很重要, 并且每一个模块要能够被独立地解释 (如果能够为一段代码块所做的事取一个很好的名字, 那这段代码块就可以抽象出一个新模块, 所以 关键 就在于取名), 这有利于发现公共模式.

愿望思维法

愿望思维法 是一种有效”发现”新模块的实践 (有利于发现 公共模式):

先用自然语言描述过程, 然后从描述中提取可能的模块, 并假设模块是已经实现好的 (即有完整的函数签名), 然后组合这些模块, 最后再去实现那些愿望.

例如, 需要实现从一个坐标点走到另一个坐标点的功能, 那么我们可以先假定 坐标点 的构造函数与选择函数:

• make-point
• x-point
• y-point

然后就可以实现目标功能 move-point:

(define (move-point p1 p2)
    (make-point (+ (x-point p1) (x-point p2))
                (+ (y-point p1) (y-point p2))))

(define p1 (make-point 1 2))
(define p2 (make-point 3 4))
(move-point p1 p2) ; => 4, 6

最后, 我们去实现 坐标点 的函数:

(define (make-point x y)
    (cons x y))

(define (x-point p)
    (car p))

(define (y-point p)
    (cdr p))

MAP

一些语言中会提供 map 操作, 例如 Python, map 接收一个函数 f 和一个 list, 并通过把函数 f 依次作用在 list 的每个元素上, 得到一个新的 list 并返回.

map 其实只是一个 公共模式. 例如现要把一个 1 到 10 的 list 放大 10 倍和缩小 5 倍, 那么在没有 map 之前, 就会写出两个函数:

(define 1-to-10 (list 0 1 2 3 4 5 6 7 8 9))

; 放大
(define (magnify l)
    (if (null? l)
        ()
        (cons (* (car l) 10)
              (magnify (cdr l)))))

; 缩小
(define (shrink l)
    (if (null? l)
        ()
        (cons (/ (car l) 5)
              (shrink (cdr l)))))

很快就可以提取出公共模式:

(define (<name> l)
    (if (null? l)
        ()
        (cons (<operator> (car l))
              (<name> (cdr l)))))

然后重构出来的高阶抽象就是 map:

; 递归版本
(define (map p l)
    (if (null? l)
        ()
        (cons (p (car l))
              (map p (cdr l)))))

; 迭代(尾递归)版本
(define (map p l)
    (define (map-iter remain result)
        (if (null? remain)
            result
            (map-iter (cdr remain)
                      (cons (p (car remain))
                            result))))
    (map-iter l ()))

; 使用 map 重构
(define (magnify l)
    (map (lambda (x) (* x 10)) l))

迭代(尾递归)版本的 map 实现有个问题, 返回的新列表是倒置的, 所以需要再反转一下. 原因是因为 cons 连接元素时, 子 cons 必须位于第二个参数, 这样才会优化成 list, 否则就会成为 (((((0 . 10) . 20) . 30) . 40) . 50) 这样的结构.

For-Each

(define (for-each p list)
    (cond ((null? list) *done*)
          (else (p (car list)
                (for-each p (cdr list))))))

在网络上, 一些说法将 map, reduce, filter, for-each 等高阶函数做为函数式语言的标准之一, 本人并不认同, 因为只要语言支持高阶抽象 (函数是第一等公民) 就能自己实现出那些高阶函数.

数据抽象

在函数式思想中, 没有类的概念, 建立数据抽象是利用 高阶抽象 以及 闭包. 例如我们可以自己实现 序对:

; 序对的构造函数
(define (cons a b)
    (lambda (pick)
        (cond ((= pick 1) a)
              ((= pick 2) b))))

; 序对的选择函数
(define (car x) (x 1))

; 序对的选择函数
(define (cdr x) (x 2))

这也是一种将数据的使用 (例如构造函数与选择函数) 与表示分隔开的 编程方法学: 当我们使用 序对 时, 其实只是在使用一些函数, 但在”外部”表现上, 它是一种叫 序对 的数据结构. 即当我们使用 序对 时, 并不知道它的底层表示, 我们只是定义了 序对 的 数据公理 (即 cons car cdr), 然后使用这些公理. 这种数据抽象的能力让函数与数据的边界变得越来越模糊.

对象状态

在构建大型系统时, 将其看成是由一批相互作用的对象组成是一种有用的策略 (另一种策略是流, 即把系统看作一种信号处理系统). 我们已经有了 数据抽象 去进行映射, 但真实系统中的对象会随着时间的流逝不断变化, 而映射它们的软件对象也要适应相应地变化, 因此就需要某种方式来维护对象的状态, 这是一种新的计算模型:

(define (MAKE-COUNTER x)
    (lambda ()
        x
        (set! x (1+ x))))

(define c (MAKE-COUNTER 0)) ; c 是从 0 开始的计数器

(c) ; => 1
(c) ; => 2
(c) ; => 3

函数 MAKE-COUNTER 返回了另一个函数, 构建出了一个 闭包 环境, 即返回的函数可以访问 MAKE-COUNTER 的作用域.

引入状态的对象具有副作用, 特别是在并发程序中问题会更严重.

面向对象

(define (make-account balance)

    (define (withdraw amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds"))

    (define (deposit amount)
        (set! balance (+ balance amount))
            balance)

    (define (dispatch m)
        (cond ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                m))))

    dispatch)

(define A1 (make-account 100)) ; 生成一个初始有 10 0元、名为 A1 的银行账户

((A1 'withdraw) 20) ; => 80