函数式编程的几个小例子

发表于 分类于 本文字数： 1.7k 阅读时长 ≈ 6 分钟

前言

我怎么开始搞函数式编程了呢？其实两年前就开始接触所谓的函数式编程了，当时是看了那本《黑客与画家》然后就产生了“Lisp 好厉害，我要学 Lisp”的想法……但是呢，当时就只是随便玩玩，根本就没入门，只是会使用一些 map 或者 filter 之类的东西。

两年后，看了一部动漫：《玲音（Serial Experiments: Lain）》，赛博朋克和意识流的佳作，里面也有函数式编程：

后来，不知道是什么缘分，知乎上有个人找到我，问我会不会 Racket 编程语言，能不能给她的孩子补习一下 Racket，我想我也会一点 Racket，就说好的，然后就谈妥了开始一对一网课。

妈呀，不上不知道，一上吓一跳，他们的 Racket 怎么这么不一样啊，map 呢？filter 呢？怎么全是 cons？噢，滑铁卢大学的 CS 135……好吧，马上学习！吭哧吭哧学下来，我大概算是摸清了滑铁卢的套路。不得不说滑铁卢的 CS 135 真的有点意思，打个比方就是说，学校只教会你使用最基本的拼音和汉字以及最基础的语法，然后就让你写出一首押韵的回文诗。

这篇文章只是用几个非常基本的小例子来展示一下函数式编程的样子，主要是与过程式编程和面向对象编程区别开来，因此并不能完全地体现出函数式编程的特性。

话不多说，开始。

例子

1. len

len() 函数应该是在各大编程语言中很常见的一个内置函数了，它的基本作用是求一个列表（list）的长度（length），即列表中元素的个数。那么，怎么用函数式编程的方式来实现 len() 这么一种函数呢？

注意，函数式编程一般不会用循环，因此如果直接循环遍历每一个结点然后 cnt++ 这样是不合适的。

能用的只有两个基本特性：条件判断和递归。当然，基本的算术运算符肯定还是要用的。

这里用 Racket 语言当作例子。Racket 是 Scheme 的一个分支，而 Scheme 是由 Lisp 而来。

1
2
3
4
5
6
7
8
9
;; Returns the number of elements in list.
;; (listof Any) -> Num
(define (my-len l)
  (cond
    [(empty? l) 0]
    [else (+ 1 (my-len (rest l)))]))

;; Examples
(my-len '(1 2 3 4)) ; => 4

简单说一下

  • cond 表达式，它会依次计算参数列表中每个参数的第一个表达式，如果结果为真则计算该参数的第二个表达式，然后结束，如果都没有真，则计算 else 分支的表达式。整个 cond 也是一个表达式，因为在函数式编程里，任何子句都是纯粹的表达式。这个 cond 可以简单理解为 C 语言中的 switch。
  • empty? 表达式，它会计算参数是否为空，返回布尔值。
  • l（代表 list）是形参，其实参本质上是一个链表。
  • rest 表达式，它会返回除开链表头结点之后的剩余链表。

OK，再简单说一下这个函数是怎么算出列表长度的。

  • 递归两大要素：基例和链条。基例就是，当列表为空时，返回 0 给上一层。
  • 链条就是，每次递归到下一层时，最顶层表达式加 1。递归到下一层传进去的实参是 (rest l)，这样一直递归下去直到基例，当到达基例的时候，在最顶层看来就已经加了总元素个数那么多个 1 了，于是返回到最顶层的时候累加起来就得到了结果。

嘛，大概就是这样，就算出了一个列表的长度。

上面那个是最简单的版本，空间复杂度比较高（每次递归都要开辟新的栈），可以改进一下：

1
2
3
4
5
6
7
8
9
10
;; Tail Recursion version.
(define (my-len-tr l)
  (define (iter l len)
    (cond
      [(empty? l) len]
      [else (iter (rest l) (+ len 1))]))
  (iter l 0))

;; Examples
(my-len-tr '(1 2 3 4)) ; => 4

嗯……尾递归版本，可以复用栈帧，空间复杂度从 \(O(N)\) 降到了 \(O(1)\)。

用 Racket 提供的 trace 库可以很容易看普通递归与尾递归的区别：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>(my-len '(1 2 3 4))
> (my-len '(2 3 4))
> >(my-len '(3 4))
> > (my-len '(4))
> > >(my-len '())
< < <0
< < 1
< <2
< 3
<4
4
>(my-len-tr '(1 2 3 4))
>(iter '(1 2 3 4) 0)
>(iter '(2 3 4) 1)
>(iter '(3 4) 2)
>(iter '(4) 3)
>(iter '() 4)
<4
4

2. map

map() 是函数式编程里一个很常用的函数了，Python 里面也有。简单来说就是把一个函数当成参数作用到后面列表的每一个元素上。

1
2
3
4
5
6
7
8
9
;; Constructs a new list by applying a function to each item on list.
;; func (listof Any) -> (listof Any)
(define (my-map f l)
  (cond
    [(empty? l) empty]
    [else (cons (f (first l)) (my-map f (rest l)))]))

;; Examples
(my-map string-upcase '("ready" "go")) ; => '("READY" "GO")

尾递归版本：

1
2
3
4
5
6
7
8
9
10
;; Tail Recursion version.
(define (my-map-tr f l)
  (define (iter l r)
    (cond
      [(empty? l) (reverse r)]
      [else (iter (rest l) (cons (f (first l)) r))]))
  (iter l empty))

;; Examples
(my-map-tr string-upcase '("ready" "go")) ; => '("READY" "GO")

3. filter

filter() 函数是函数式编程的一个很常用的函数了，Python 里面也有。

1
2
3
4
5
6
7
8
9
10
11
;; Constructs a list from all those items on a list for which the predicate holds.
;; func (listof Any) -> (listof Any)
(define (my-filter p? l)
  (cond
    [(empty? l) empty]
    [(p? (first l)) (cons (first l) (my-filter p? (rest l)))]
    [else (my-filter p? (rest l))]))

;; Examples
(my-filter odd? '(0 1 2 3 4 5 6 7 8 9)) ; => '(1 3 5 7 9)
(my-filter even? '(0 1 2 3 4 5 6 7 8 9)) ; => '(0 2 4 6 8)

4. min/max

min()/max() 这两个函数也是非常常用的，顾名思义，取出一个列表中的最小值/最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
;; Determines the smallest number.
;; (listof Num) -> Num
(define (my-min l)
  (cond
    [(empty? (rest l)) (first l)]
    [(< (first l) (my-min (rest l))) (first l)]
    [else (my-min (rest l))]))

;; Examples
(my-min '(1 2 3 4)) ; => 1


;; Determines the largest number.
;; (listof Num) -> Num
(define (my-max l)
  (cond
    [(empty? (rest l)) (first l)]
    [(> (first l) (my-max (rest l))) (first l)]
    [else (my-max (rest l))]))

;; Examples
(my-max '(1 2 3 4)) ; => 4

5. sum

sum() 这个函数也是非常常用的，顾名思义，对列表求和，前提是该列表的元素是可加的。

1
2
3
4
5
6
7
8
9
;; Returns the summation of elements in list.
;; (listof Num) -> Num
(define (my-sum l)
  (cond
    [(empty? l) 0]
    [else (+ (first l) (my-sum (rest l)))]))

;; Examples
(my-sum '(1 2 3 4)) ; => 10

6. index

index() 这个函数的作用是取出该列表中指定索引（index）的值。本质上就是查找一个链表中指定位置结点的值。

1
2
3
4
5
6
7
8
9
;; Extracts the n-th element from list.
;; (listof Any) Num -> Any
(define (my-index l n)
  (cond
    [(zero? n) (first l)]
    [else (my-index (rest l) (- n 1))]))

;; Examples
(my-index '(1 2 3 4) 3) ; => 4

以上。