函数式编程简介

这是我为了学校的一个活动准备的讲稿,这几天会不断编辑。

伪代码

为了便于理解,这里用类似 JavaScript 的代码,在文中可能不会给出函数的具体实现,但都是容易实现的。

在这里,我尽量使用比较通用的名词,但是因为语言不同也会有差异。

另外,JavaScript 也算是函数式编程语言,所以文中的伪代码在简单的修改以后应该可以运行。

什么是函数式编程?

广义上很多编程语言都是函数式编程语言,比如说 Python、Ruby,而在最近 Java 8 和 C++ 11 都引入了很多函数式特性。

概括说,函数式编程往往有这些特点,而且这些特点是有关联的:

  • “第一级”(first class)的函数,常常使用高阶函数来抽象。
  • 利用递归进行循环。
  • 将程序看作表达式的组合,尽量避免“副作用”——很少使用变量!
  • 惰性求值。

下面就稍微说一说。

什么是第一级的函数?

在非函数式编程语言中,函数都是被压迫的奴隶,有很多事情函数不能干,而在函数式编程中函数终于翻身奴隶做主人了。

其实就是把函数看作编程语言中最重要的东西之一,完全像数据一样:

能被当做参数传入!

在一些情况下(比如说求不动点)我们可能会把一个函数应用两次或者更多次,那么在函数式编程里面可以这样写:

一个函数并不需要知道传进来的是什么函数就可以对它进行操作和调用,这样的好处有很多,比如说你可以写一些数学函数,比如说求导或者求不动点,然后直接把你的函数传入进去;另外,你可以用高阶函数进行更高的抽象,这是之后要讨论的。

能在函数中动态生成,然后再返回一个新的函数!!

还是之前那个例子,现在,我们手里有一个函数 f,为了不每次调用上面的“我是函数”所以可能我们会想,如果能生成一个函数 g(x) = f(f(x)) 就好了,也就是说,对新的函数传入一个值就会调用两次原函数。

但是我们不能直接写,比如这样:

因为我们可能不知道什么函数需要重复,而且如果有N个函数,那么你就必须手写 2N 的函数,谁都知道这是非常机械的,能不能用一种方法来生成这种重复函数呢?

这就是闭包出场的时候了!闭包能让我们在函数中根据参数动态的生成两个函数:

看,我在一个函数里面又定义了一个函数,根据传入 x2 这个函数的参数函数 f,我动态生成了函数 g 并且返回。

不需要名字!能赋值给变量!能放在数据结构里面!

上面的代码实际上可以简化成这样子:

x2 生成的函数竟然没有起名字就直接返回了!这是不是不符合语法?其实这就是标准的 JavaScript 语法,没有名字的函数就叫匿名函数,实际上函数必须命名是对函数的歧视,一个数组或者一个数据以及各种各样的对象为什么都可以不命名直接用?(比如说 foobar(40+2),这里两个数字完全不需要命名。)

现在函数翻身奴隶做主人了,当然要要求消除不平等待遇,现在函数已经能没有名字地随便创建了。不过一些语言还是不能很好地做到这一点,比如说 Python。

再来看看我们调用了 x2 以后,返回的函数放在哪里

放在变量里面!这也是意料之中的事情,但是再想想,既然能放到变量里面,那为何不能放到任意数据结构里面呢?

如果我们有一大堆函数要处理的话,我们可以放在链表里面处理:

在这里 f_list 是需要操作的函数的链表,result 是存放结果的链表,for 循环将 f_list 的每一个值取出来,传入 x2,并将返回值存入 result。

注意,在本文中如果没有特别说明,类似数组的结构其实都是链表,这是伪代码和 JavaScript 的不同之处。因为在函数式编程中链表往往有很重要的地位。接下来会通过链表的一些特点来帮助函数式编程的。

上面的代码其实写得不函数式,现在,我们有了强有力的工具,那么就可以看看高阶函数了。

使用高阶函数来抽象

在上面的例子中,我们取出函数表中的每一个函数,然后对每一个函数应用一个函数,把结果保存在另外一个表的相应位置,这种操作在编程中很常见。比如说把原来的表中每个数乘以2,放到新的表中,或者可以在列表中放一些 SQL 语句,将数据库查询的结果放到新的列表对应的位置,都会有类似的操作。

在写这些函数的时候,程序员会发现控制结构是大同小异的,只有几个函数不一样。现在我们有了高阶函数,能不能把控制结构给抽象出来,让函数作为参数传递并且运用呢?

当然可以,这种函数在函数式编程中一般叫做 map 函数。在大多数语言中,map 函数的第一个参数是一个函数,这个函数只有一个参数,第二个参数是一个表(或者任何一个可迭代的结构),下面给出一个例子:

可以看到,map 函数使用第一个参数函数,对第二个表进行了缩放,形成了一个新的表。

请注意,新的表是一个返回值,对于原来的数组并没有更改。在函数式编程中,赋值是被尽量避免的。这一点留到后面再说。

另外,map 函数具体实现在这里不写。

有兴趣自己试试,请注意,为了避免赋值循环可以用递归来代替,这就是为什么要用链表的原因之一,比起数组,链表和递归配合地更自然。

好了,我们看看上一节的例子如何用函数式的方法改写:

虽然对习惯命令式编程的人来说,可能刚开始会感觉有点抽象,但是习惯了以后会发现这种方式既简洁又易读。因为将无关的细节用高阶函数抽象了。

有了高阶函数,下面这种数学求和过程也能很自然地实现了。
  \sum\limits_{n=a}^{b}f\left( n\right)

实际上,有了高阶函数,我们可以进行更通用的数据处理过程,看看下面几个描述:

  • 将所有的用户从数据库取出来 -> 去掉年龄大于二十岁的用户 -> 获取剩下用户的评分 -> 求出他们评分的平均值
  • 找出所有一百以内的数 -> 去掉所有合数(不是素数的数) -> 将素数相加
  • 在 [1, 100] 区间,列出三条线段为一组 -> 去掉不能组成三角形的那些线段组 -> 将符合条件的三角形存放到列表中

可以很清楚地看见,这些计算过程的结构是相近的,那么既然如此,我们就敢抽象。

  1. 第一阶段,是把所有要处理的数据提取出来。
  2. 第二阶段,是把所有提取出来的数据做一次过滤。
  3. 第三阶段,是把过滤后的数据进行一次处理。
  4. 第四阶段,把处理以后的数据按照某种方式组合到一起

这就是经典的序列操作模型,当然不一定是钉死的,比如说有时候不需要第一阶段的过滤,有时候不需要第三阶段的处理,有时候不需要第四阶段的组合。

第一阶段我们称作枚举器,这个函数具体是什么样的函数视情况而定,但是会返回一个列表(或者别的可迭代数据结构)。

第二阶段我们称作过滤器(filter),这是一个高阶函数,第一个参数是一个判断函数,对第二个参数的列表中每一个元素应用判断函数,如果为真就保留在列表的返回值,如果为假就会被过滤掉:

第三阶段就是之前说的 map 了!

第四阶段被称作累加器,不过名字在不同语言中是不同的,有的时候叫 accmulate ,有的时候叫 fold ,有的时候叫 reduce。

在这里就用 reduce 啦,reduce 说起来有点困难,第一个参数函数有三个参数,第二个参数依然是一个列表,下面是例子:

这就是一个列表求和的过程,最后的结果是 45。

reduce 是一个迭代的运算过程,第一个参数函数有两个参数,其中 a 被传入的就是上一次迭代的结果,然后 b 被传入的是新的列表元素。(最初 reduce 的 a, b 分别是列表的第一个和第二个元素。)

而 reduce 第三个参数是 reduce 进行处理的初始值,有的时候是可选的,在这里省略了以后 reduce 会把传入的表的第一个元素当作初始值,所有处理从第二个元素开始。

一般的列表数据处理流程就是,假设获得了需要处理的列表 list:

这样很抽象,是极其美丽的代码,但是性能不怎么样。

为什么呢?首先, reduce map 和 filter 都需要对列表进行一次遍历,加起来就有三次循环了,其次每个高阶函数的返回值都是一个新构造的链表,这样的会让内存读写的开销变大。

难道那么美丽的概念就是中看不中用吗?不是的,聪明的计算机科学家有妙招,惰性求值。

惰性求值

惰性求值,其实就是伪装成数据的计算过程。可以想像考试的时候,有的人做好万全的准备,刷刷刷下笔如飞;有的人耍小聪明,要做一题的时候偷偷用手机查。但是两个人最后的分数一样。

考试就是数据被使用,勤奋的方法是在数据被使用前处理好所有的数据(这叫及早求值),懒惰的方法是等数据要被用到的时候才准备数据(这就是惰性求值)。

上面也看到了,勤奋的每次生成所有的数据常常会做无用功,白白地占了空间,浪费了计算能力。

其次,“吾生也有涯,而知也无涯,以有涯随无涯,殆已”,有的时候,要处理的数据是无限的,用勤奋的办法学到死也学不会。

大致的描述一下,前面提到过的流式处理代码,先忽略 reduce,因为 reduce 不可以是惰性的:

假如这里面的函数都是惰性的,那么你输入上面这些代码了以后,map 会立刻返回给你一个表,速度非常快,就算你的运算再复杂速度也非常快。

速度如此之快的秘诀,不是“惰性”掌握了什么高级优化技巧,而是因为……还没开始计算!!!

坑爹呢这是!

其实不是坑爹,你可以像用普通数据结构一样用返回的表,而不用管它到底有没有计算,按照惰性求值的机制,当你用到一个值的时候它会自动计算并返回,你完全感受不到一个惰性表和普通的表的区别。

把上面代码的返回值命名为 list,我们看看访问 list 这个结构的时候发生了什么,另外请注意,这个 list 我们应该视作链表,所以获取当前节点的数据的操作是 list.data ,获取下一个链表节点的操作是 list.next 。

当我们用 list.data 请求一个数据的时候,因为这时候还没开始计算,所以 map 不能马上返回一个值,它需要先找到 filter 返回的第一个值才能处理,但是 filter 也是惰性的,所以受到 map 的要求,filter 仅仅返回了一个值就不干了。

map 得到了 filter 的一个值,终于可以用 f2 处理了然后返回了,但是不会继续循环,除非调用 map 的操作需要下一个值,毕竟,如果不这样懒惰,如果获得 map 的返回值的函数也同样是循环函数(比如说再套一层 filter),那么岂不是要多循环一遍了?而且保存值也需要空间开销。

就这样,返回的是一个惰性表,等真正要用到的时候才从 map 和 filter 获取值,那么到最后就只循环了一遍,也没有多余的储存空间被浪费,而且可以用惰性表处理无穷的数据。

下面看看无穷数据的例子,写一个最美妙的菲波那契数列。

在写出这个程序之前,需要一点解释。

在我们的伪代码里面,如果 “+” 的两边都是惰性表的话,会生成一个新的惰性表,每一个位置上的值就是两个惰性表相应位置上值的和。

另外,我们通过函数 cons(a, b) 来创建惰性表,因为惰性表是一种链表,所以a是数据,b是指向下一个节点的指针,因为是惰性表,所以 b 不会被马上求值,直到真正用到的时候才会被求值。

大功告成!

请注意 fib 的定义中递归的引用了自己,如果不是惰性求值就会造成死循环,但是在惰性求值的情况下就变成非常优雅的写法了。

这里仅仅说了一丁点

  • Lambda 演算 柯里化
  • 元编程
  • 列表推导式
  • 续延传递风格(Continuation Passing Style
  • 不确定编程
  • 逻辑编程语言
  • 单子
  • ……

为什么要用函数式编程?

时间是一种设施,发明它是为了不让一切都同时发生。

——剑桥建筑墙

以后再详细写……

  • 拓展思维,学习新方法。
  • 极致的抽象,并且在抽象中取舍。
  • 并发。

如何开始学习?

计算机程序的构造和解释》+ Racket

函数式编程简介》上有5条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注