发现还是好多没懂orz 先记一些概念后面学一门语言看看吧

函数式编程

先放一下 wiki

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm in that programming is done with expressions or declarations instead of statements. In functional code, the output value of a function depends only on its arguments, so calling a function with the same value for an argument always produces the same result.

函数式编程是一种编程范式，将计算视为对数学函数的评估，避免状态变化和可变数据的发生。 它是声明式编程范例，使用表达式或声明而不是语句来完成编程。 在函数式编程中，函数的输出值仅取决于其参数，用相同的参数调用函数始终会产生相同的结果。

也就是说，函数式编程是一种无状态的编程。

举个例子，我们希望得到一个计算余额的程序。下面的代码就是简单的实现，然而它是命令式编程：引入了局部变量balance， 使得用相同的参数调用函数始会产生不同的结果。

1
2
3
4
5
6
7
8
9
10
11
(define (make-simplified-withdraw balance)
  (lambda (amount)
    (set! balance (- balance amount))
    balance))

(define W (make-simplified-withdraw 25))

(W 10)
15
(W 10)
5

纯函数式编程应该写为：

1
2
3
4
5
6
7
8
9
10
(define (make-decrementer balance)
  (lambda (amount)
    (- balance amount)))

(define D (make-decrementer 25))

(D 10)
15
(D 10)
15

当然这就不能实现我们想要得功能了，想要用函数式编程处理这些问题，可能需要引入可变变量或通过 Monad 进行封装（我还不会emmm）。

不看函数式编程产生的结果，它最大的特点在于函数式编程更倾向于通过是什么解决问题，而命令式编程通过怎么做解决问题。

举个例子，一个经典的换零钱问题：

总数为a的现金换成n中硬币的不同方式的数目等于

  • 将现金数 $a$ 换成除第一种硬币之外的所有其他硬币的不同方式数，加上
  • 将现金数 $a-d$ 换成所有种类的硬币的不同方式数，其中 $d$ 是第一种硬币的币值。

这就是一种函数式编程的思想，没有考虑解决问题的过程，而仅仅表达了问题是什么。换句话说，函数式编程是通过函数描述从输入到输出的直接映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

Conventional Interfaces

不知道应该怎么翻译emmm 就是将程序分解成不同功能的部分，通过组合达到需要的效果。或者说，将程序抽象，从而产生一个序列。

考虑两个问题：

  • 输入一棵树，求值为奇数的叶子的平方和
  • 构造出偶数的斐波那契数 $Fib(k)$ 的表，其中 $k\le n$

将程序抽象为枚举器，过滤器，映射，累积器。

image-20200124115320662

要组织好这些程序，使之能够更清晰地反应上面信号流的结构，最关键的一点就是将注意力集中在处理过程中从一个步骤流向下一个步骤的 “信号”。如果我们用一些表来表示这些信号，那么就可以利用表操作实现每一步骤的处理。

为什么要说 ‘如果’ 呢？因为后面介绍的流就不是这样的 hhh

用表来表示信号是简单的, 以过滤器为例子

1
2
3
4
5
6
7
8
9
(define (filter predicate sequence)
  (cond ((null? sequence) nil)    ;; 空表
        ((predicate (car sequence))
         (cons (car sequence);; 第一项符合，构建新表，继续检查
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
              ;; 第一项不符合，检查下一项
(filter odd? (list 1 2 3 4 5))
(1 3 5)

构造出偶数的斐波那契数 $Fib(k)$ 的表, 只需：

1
2
3
4
5
6
(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))

惰性求值与流

考虑我们刚刚构建的序列，事实上它是低效的：在工作的每一步都必须构造或记录整个表。

举个例子：我们需要程序计算一个区间内所有质数的和。使用序列的实现，我们需要构造出整个区间的表，得到整个区间内的质数后再计算他们的和。而传统的迭代风格则是对每个数判断是否为质数，若是质数则加到和中。可以看到，用序列实现需要使用很多额外的空间。

一个很好的解决方式是惰性求值。惰性求值是指：表达式不是在绑定到变量时立即计算，而是在求值程序需要产生表达式的值时进行计算。

假设各种组成是一个个的方框，数据是一条线

image-20200124133045909

那么之前的实现方式就是将整条线一次穿过各个方框；

image-20200124133054790

image-20200124133112207

而惰性求值则是在累加器需要时在最后拉线，从而使线依次穿过方框。

image-20200124133123534

image-20200124133130863

流（Stream）就是使用惰性求值的方法来实现的序列，可以看成一种延迟的表。

Java 8 API添加了一个新的抽象：流Stream，可以以声明的方式处理数据，就有惰性求值的特性。

流的实现

流的特点是惰性求值。

一种实现 [SICP]

将流的 cdr [lisp中表示一个表除了第一项之外的项] 求值等到访问它的时候再做，而不是构造流的时候做。使用基于 delay 的特殊形式，对于 (delay <exp>) 的求值将不对表达式 <exp> 求值，而是返回一个延时对象，可以看作对未来的某个时刻求值的许诺。而 force 过程则以一个延时对象为参数，执行相应的求值工作。

定义流和它的car，cdr

1
2
3
4
(define cons-stream <a> <b>
	cons <a> (delay <b>))
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))

当我们需要流后面的内容时，通过 stream-cdr 进行求值，而在构造流时不进行求值。

下面通过一个例子来看流的运行过程：求10000-1000000中的第二个质数, 也就是10000-1000000所有质数的表中除了第一项之外 cdr的第一项car。

1
2
3
4
(stream-car
 (stream-cdr
  (stream-filter prime?
                 (stream-enumerate-interval 10000 1000000))))

在之前的实现中，我们需要求出10000-100000中的所有质数，然后取表中的第二个，这显然是低效的。下面看stream的运行：

首先，(stream-enumerate-interval 10000 1000000) 会返回从10000到1000000的流，但不会显式的表现出来，而是10000和一个延时对象：

1
2
3
4
5
6
7
8
(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(cons 10000 (delay (stream-enumerate-interval 10001 1000000)))

之后，stream-filter 检查得到的流中的 car ，发现他不是一个质数，于是继续检查流的 cdr。调用 stream-cdr 也就是需要流对下一项进行求值，于是通过force得到下一个数即 10001。

1
2
3
4
5
6
7
(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))

知道得到 10007，检查发现它是一个质数，于是stream-filter返回一个流：

1
2
3
4
(cons 10007 (delay
              (stream-filter prime?
                (cons 10008 (delay
                 (stream-enumerate-interval 10009  1000000))))))

这个结果送到程序中的 stream-cdr， 于是它需要继续寻找下一个质数，直到返回 10009，程序结束。

也就是说，在这种实现中，我们只对流的第一项进行计算，流的后续作为一个延时的许诺返回，在需要时再进行计算，从而减少额外空间时间的使用。

delay和force的实现其实也很简单：

1
2
3
4
5
(define (delay <exp>)
  (lambda () <exp>))

(define (force delayed-object)
  (delayed-object))

我们还能得到无穷流：如无穷正整数流：

1
2
3
4
(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

另一种实现

期末考试需要用自己的函数式编程语言写流的实现，然后不会 T T

首先定义终断操作：即一个流的最后操作，这个操作会返回一个表或一个值。而非终断操作则会继续返回一个流。

我们已经知道，流和表最大的区别就是流的惰性求值，在前面中也看到，返回的流中包含了中间的操作。在非终断操作中，如果直接将表传入进行操作生成另一个表不符合流的基本思想。

因此，一种想法是将非终断操作延时进行。换句话说，就是 map，filter 等函数不对数据进行处理，而是将传入的函数包装在传递的流中。直到遇到一个终断操作，再对流中的数据进行处理。

在上面的例子中，只有 stream-car 是一个终断操作， stream-cdr 依然是非终断操作。

等我学一门语言再来实现orz

参考资料：

Structure and Interpretation of Computer Programs