logo头像

Hacked By Swing

浅谈函数式编程(1)

浅谈函数式编程

前言

关于这个话题我其实很早以前就想聊一聊,但是鉴于自己水平有限,一直不敢瞎说,比较担心说错或是理解不够深刻,但是换个角度想,这反正只是我的理解,如果不发出来也不知道错了还是没错,所以还是决定写一下,如果有错漏也欢迎指出,理解不对的也欢迎探讨。(我可能会简化一些东西便于理解)

另外,本文在写的时候是认为大家对写程序有一定理解的,所以我会假设大家已经会一种或者多种语言,我会尽量使用较为普及的语言来解释。但是如果你完全没有编程基础,这不是一篇入门的教程,可能会存在阅读上的困难。

生活太简单了,加点难度。

让我们做个假设,假设有一天,你写代码的时候觉得写代码实在太简单了,于是决定给自己加点难度。

这个难度怎么加呢?代码还是要写的,逻辑还是得要的,但是你就是突然太讨厌变量了。于是你决定从此以后你用的“变量”再也不给第二次赋值(变量不再可变)。

举个例子:

1
2
a = 1 # 第一次赋值
a = 2 # 第二次赋值,在今天以后,你决定再也不写这种代码了

没有了赋值,你就不能再写循环了。为什么呢?让我们来看一种循环的实现方式:

1
2
3
4
i = 0
while i < 10:
print(i)
i += 1

如果用 C 来写,就更显然了

1
2
3
for (int i = 0; i < 10; ++i) {
printf("%d\n", i);
}

为什么呢?因为你不能再 i += 1 或者 i++++i)了。(还记得你刚刚提高的难度么?)

没有了循环,代码还怎么写呢?

其实也不难,虽然没有了循环,但是你还可以用递归呀,所以我们可以把原来的循环代码改成这样:

1
2
3
4
def print_10(i):
if i < 10:
print(i)
print_10(i + 1)

C 语言也是一样:

1
2
3
4
5
6
void print_10(int i) {
if (i < 10) {
printf("%d\n", i);
print_10(i + 1);
}
}

所以,用这样的方式,你依然可以写出原来能够写出的代码。那区别是哪儿呢?区别是你在使用“函数式编程了”。

函数式编程

到现在我们说到了函数式编程的其中两个原则:

  1. 没有变量,只有绑定(也就是只能有仅允许一次赋值或是叫做绑定的常量)
  2. 没有循环,只有递归

另外我们还需要加上一点:

  1. 函数可以作为参数传入

这一点由于在现行的大多数语言中已经支持了(例如 PythonJavascript等都已经支持了闭包,或者是匿名函数等)。

如果不去纠结细节,满足这几点,我们基本上已经在进行“函数式编程”了。

(事实上函数式编程涉及到 lambda 演算等理论,但是这里我们简化了一下,认为符合这几点就算函数式编程)

由于函数式编程的几个特点,编程时的思路也有些不同。由于函数可以作为参数传入,加上使用递归,在函数式编程中,我们往往倾向于编写大量“小的函数”,然后对函数进行组合来完成完整的程序。

Typeclass

好了,我们知道了函数式编程,知道了函数式编程倾向于用小函数组合出完整程序。下面有一个问题,在普通的编程中(叫做指令式编程),我们可以采用面向对象的方式来尽量复用代码,函数编程中我们还可以使用这种方式吗?

当然不行。在面向对象中,我们没有要求对象“不可变”,也就是对象的状态(属性)是可以变的,那就不符合函数式编程的原则了。

所以我们该如何去复用代码呢?当然,要是能够尽力保持函数式编程的哲学(使用小函数组合成大函数)就更好了。

于是就有了 typeclass

其实 typeclass 并不复杂,因为其实它基本上就是面向对象中的 interface ,接口。

接口规定了一个对象能够做的事情,我们如何应用接口来复用代码呢?其实不难,我们如果能把代码写在接口里,不就可以复用代码了吗?

比如:

1
2
3
4
5
6
7
8
9
10
interface GetArea {
method area(): Double
}

interface DoubleArea {
// 不同的 area 我们都可以将它 * 2 !
method double_area(): Double {
this.area() * 2
}
}

可以看到,无论具体的 area 是如何实现的,double_area 都可以利用 area 来完成他的功能,不同的 area 实现对应的 double_area 的结果也不一样。通过这样的方法,我们就可以将可以复用的代码实现在接口里。 (其实这也是另一种“面向对象”,Rust 语言就采用这样的面向对象,将 interface 命名为 trait)

如果我们要再 “typeclass” 一点,我们就不让接口和 “对象” 绑定,也就是说,我们调用 area 或者 double_area 的方式不是 obj.area() 或是 obj.double_area(),那我们要如何调用呢?

我们以 double_area 为例,不用这种方式调用之后,它就变为了 double_area(obj),也就是应该传入一个参数,这个参数是我们希望计算出面积的对象(或是结构体等类似概念)。此时,double_areaarea 的调用也变为了 area(obj) ,那如何去知道这个 area 是具体哪个 area 呢?

按照 typeclass,这个问题的答案就是:“根据类型而定”。因为一个 typeclass 会指定一个类型,类似如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
//        类型
typeclass Circle GetArea {
function area(circle: Circle): Double {
// 实现
}
}

typeclass Circle DoubleArea {
function double_area(circle: Circle): Double {
// 由于这里的“circle”是 Circle类型,所以会使用 Circle 的 area 实现
circle.area() * 2
}
}

所以类型,是一个关键。

几种 typeclass:Semigroup

接下来我们就需要看看几个关键的 typeclass 或者说 interface(trait) 了。这些 typeclass 的存在才使得函数式编程可以通过组合小函数来完成更多的任务。在我看来,这些“typeclass”组成了函数式编程的“设计模式”。

从这几种 typeclass 的介绍中我们就可以感受到函数式编程的模式中,低粒度的代码复用。

第一种是 Semigroup。

由于函数式编程和数学有一些的相关性,不少名词都来源于数学,然而事实上不完全明白这些数学概念也不会特别影响使用。

Semigroup 在数学中的意思是半群,这里沿用了其在数学中的定义。

这个 typeclass 需要一个“加法”,或者叫做结合,或者类似的意思,反正就是一个操作(我们这里用 "combine" 表示)(伪代码):

1
2
3
typeclass Semigroup {
function combine(one: Semigroup, another: Semigroup): Semigroup;
}

很明显,这是一个二元运算,要求运算的两个是同一个类型(这里由于我不想引入泛型的表示方式,所以伪代码中看不出来),且这个类型需要满足一个特定要求:

1
combine(A, combine(B, C)) == combine(combine(A, B), C)

看起来眼熟?是的,这就是数学上的结合律!在数学上半群其实定义与之类似,所以我们采用了这个命名。

然后?然后就没了。这个“接口”(typeclass) 就只需要这样的要求。

体会到函数式的特点了吗?粒度很细,如果说的更专业一点,这个叫做“抽象程度更高”(因为符合这个要求的情况更多)。

那么有哪些东西符合这个要求呢?例如,python中,字符串的连接:

1
("a" + "b") + "c" == "a" + ("b" + "c") # True,将 a, b, c 任意替换也成立

列表的连接:

1
([1] + [2]) + [3] == [1] + ([2] + [3]) # True,将 1, 2, 3 任意替换也成立

那这个东西有什么用呢?这个问题其实比较难以回答,他的目的就是把你的数据结构和操作只要符合这个要求,就实现这个接口,然后我就可以很方便的组合出更高级的函数。

举个例子,比如我写一个函数,目的是把一个东西重复两次,我就可以用上这个“半群”。

1
2
3
function mult2(s: Semigroup): Semigroup {
combine(s, s)
}

那这个函数可以干嘛呢?这个函数,如果我给他一个字符串,他就会把字符串重复两次,如果是列表,就会把元素重复两次,如果是数字,就会乘 2 ,这种函数非常“抽象”,函数式编程的特点就是这样,你通过组合一大堆十分“抽象”的函数,得到一个你想要的,你提供给别人的函数可能也十分抽象,这就是一种细粒度的组合。

这样写出的程序十分灵活,复用程度也很高,因为他们很“抽象”,他们可以在很多时候被反复使用,这就达到了代码复用的目的。

Typeclass: Monoid

下一个是 Monoid,幺半群(也叫单位半群),同样来源于数学中的概念,名字十分高深,令人疑惑。

但是其实呢?它的要求也很简单。

首先它要求 Semigroup 要求的所有东西,也就是有一个满足结合律的二元运算。

接下来,它还额外需要一个函数,或者说,额外需要一个“元素”:

1
2
3
typeclass Monoid: Semigroup {
function empty(): Monoid;
}

听名字就知道,这个东西代表“空”,或者说是零,或者单位,更准确(单位半群的单位,幺半群的幺元)。

和之前的半群一样,这个函数(或者元素,因为这个函数直接返回一个元素/对象)除了满足接口的要求,还需要额外满足一个定律:

1
combine(empty(), A) == combine(A, empty()) == A

想到什么了?对比一下我们学的数学:

1
2
0 + A = A + 0 = A
1 * A = A * 1 = A

同样的,在实际程序中也有这样的例子。例如 Python 中的字符串:

1
"" + A == A + "" == A

还有列表:

1
[] + A == A + [] == A

所以,空字符串和空列表就是这里的 empty 应该返回的内容,然后字符串连接和空字符串、列表加法和空列表就形成了两个 Monoid (因为他们符合了这个要求)。

Typeclass: Functor

接下来我们来看一个非常具有特色的 typeclass , functor , 函子。这个的来源同样是数学,只不过就更高级一些了,来源于范畴论,所以我们不需要去深究他的来源了。

我们来看看他的要求,他的要求也足够抽象,也就是足够简单。在之前我们都没有用到“泛型”,现在我们必须要用泛型了,所以首先介绍一下什么是泛型。其实有 C++ 经验的同学应该是知道的,泛型,或者叫做类型参数,就是用一个“形式参数”代表一个类型。

举个例子:

1
function combine<T>(a: T, b: T): T;

这是之前我们提到的 Semigroup 的 combine 函数的正确写法(伪代码),其中 <T> 的意思是我们暂时不知道 T 是什么具体类型,于是用一个形式参数代替,等到使用这个函数的时候,根据传入的参数,来决定 T 是什么类型。假设我调用这个函数如下:

1
combine(1, 2) // 1: Int

那么 T 就是 Int。

另外一个记法是 <T: A>,这里 A 是某一个 typeclass,比如 Semigroup,那就写作 <T: Semigroup>,代表现在还不知道的类型 T 是什么类型,但是我们要求使用的时候(调用的时候),这个类型必须要满足 Semigroup 的要求,也就是这个类型 T 得有 combine 函数。

好了,我们现在来写写之前两个 typeclass 的正确写法:

1
2
3
4
5
6
7
8
9
// 这里我们把类型参数移到了 typeclass 这,意思是整个 typeclass 内都是这一个类型参数
typeclass Semigroup<T> {
function combine(a: T, b: T): T;
}

// 主要是在这里,我们需要 Semigroup 和 Monoid 中的 T 应该是同一个 T
typeclass Monoid<T>: Semigroup<T> {
function empty(): T;
}

有了泛型,还不太够,为了表示 Functor,我们还需要一个东西,叫做“类型构造子”。

其实类型构造子我们早就见过,只不过我们需要给他们起一个名字。我们见过什么类型构造子呢?例如,python 中的列表……

他们是什么呢?他们将类型“包”了一层,比如我们要表达列表的类型,应该怎么表达呢?嗯,可以是“int 类型的列表”,“字符串类型的列表”……

发现什么了吗?他们的“里边”包含了类型,我们这里用 A of B 来表示类型构造子,例如 List of Int

现在我们就可以来表达 Functor 了,我这里使用 -> 来表示函数,箭头前为参数,后为返回值:

1
2
3
typeclass Functor<F> {
function map<A, B>(a: A, f: A -> B): F of B;
}

这个 typeclass 就比较有意思了,也有一些复杂,我们来仔细分析一下。

首先,整个函子需要一个 F 类型,根据他的用法(F of B),看来他是一个类型构造子,然后两个类型,分别是 A 和 B,接收一个类型 A 的变量,然后一个函数,传入类型 A 得到一个 B 类型返回值,最终返回一个 F of B。

嗯,好乱,看不懂。那我们来看一个“生活中的实例”吧:(python)

1
map(lambda x: x + 1, [1, 2, 3]) # == [2, 3, 4]

哦?python 中也是 map ?是的,其实 python 的 map 就是这个 map !

我们来看看,根据我们写的 typeclass ,类型 A 和 B 都是 Int,F 就是 List,函数就是这个匿名函数,最终得到一个 Int 列表 (List of Int)。

所以 Functor 在干什么呢?Functor 将类型构造子“包含”的那个类型“映射”成了另一个类型。

再举个例子:

1
map(str, [1, 2, 3]) # == ["1", "2", "3"]

这里,就将 List 类型构造子内的 Int 映射成了 Str。

所以 Functor 的用处就是一种“映射”,例如在列表上,把列表“里”的东西映射成了另一种(例如都加一,或者变成字符串)。

我们在 python 中可以体会到这个 map 函数带来的好处,在列表上,相当于很自然的帮你做了一个循环(于是有好多“一行完成好多任务”的例子)。不仅如此,我们还可以进一步,思考一个实用的函数式编程模式。

函数式中的Option

如何表达一个程序的返回值可有可无呢?很多编程语言都有自己的选择,例如在 Python 中用特殊值 None 来表示没有,Java 中用 null,C 语言用 NULL (其实是指针类型的 0)。

在 Functor 的讲解中,我们懂得了一个东西,叫做类型构造子,就像 List 。现在,我们扩展一下 Python 中用来表示“可有可无”的东西,用上我们的类型构造子,然后这个类型构造子命名为 Option。Option 包括两个值,一个 None,我们已经很熟悉了,另一个是一个特殊值,用来把一个值“包起来”,叫做 Some ,表示这个返回值存在。

1
2
3
Option<A>:
Some(A)
None

要是觉得 Some 不好理解,可以类比一下 [] 这个操作符。 Some 的一种用法:Some(3),将一个 Int 值包起来,如果 Option 换成 List,就好比 [3]

现在,让我们把我们之前所学的部分结合起来。

首先,这个 Option 类型构造子满足 Monoid 的要求,只要里边包含的 A 满足就可以,因为:

1
2
3
Some(A) + Some(B) == Some(A + B) // 这里就需要 A + B 满足 Semigroup 要求
Some(A) + None == Some(A)
None + Some(A) == Some(A)

看到 Monoid 和 Semigroup 的用法了吗?empty 就是 None!我可以将加法变成内部的加法,这样我就从类型构造子“包含”的类型中,构造出了新的函数,然后这种构造几乎是不需要写额外代码的!(即使写也非常显然)

还不算完,如果再用上我们学到的 Functor:

1
2
map(Some(A), f) == Some(f(A))
map(None, f) == None

这也是显然的!

那这有什么用?还记得一开始我们怎么提到 Option 的吗?是的,他可以用来表示“可有可无”,这意味着什么?

举个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def positive_only():
a = int(input())
if a <= 0:
return None
else:
return a

def add_two_inputs():
a = positive_only()
b = positive_only()

if a == None:
return None
elif b == None:
return None
else:
return a + b

这个的功能很简单,但是由于 positive_only() 一旦小于等于 0 则返回 None,导致在 add_two_inputs() 中需要写一个 if 来判断 None 的情况,如果有 Option 呢?

1
2
3
4
5
6
7
8
9
def positive_only():
a = int(input())
if a <= 0:
return None
else:
return Some(a)

def add_two_inputs():
return positive_only() + positive_only() # 因为 Option 满足 Semigroup

if 完全不再需要了!当然,这是由于加法的特殊性,那我们换一个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 没有 Some
def some_func():
a = positive_only()
b = positive_only()
if a == None:
return None
elif a <= 5:
if b == None:
return None
else:
return 6

# 有 Some
def some_func():
a = positive_only()
b = positive_only()
# 这里 map 的顺序 python 和我的伪代码有所不同,使用 python 的惯例
def func(x):
return map(lambda x: 6, b)
return map(func, a)

在 func 中,将返回常量 6 的函数 map 到 b 上,如果 b 是 None,那这个函数返回 None,否则返回常量 6, 之后这个函数 map 到 a 上,如果 a 是 None,那么不需要管 func 返回什么,都返回 None,否则返回 func 的返回值。所以这两个函数的效果是一样的(如果使用匿名函数,可以更简洁,但是相对难以阅读)。

于是有人问了,为什么要这么写?这么写明明思考起来更复杂啊?事实上这样的思考并不复杂,根据我们之前的规则,每一个 map 实际上都是将操作放到了里边包含的东西上,如果里边没有东西(None),那不管这个函数,我们直接返回 None,这么想其实写这样的代码就不复杂了。

这样写的一个最大好处:没有了边界判断!没有了“特设性假定”(误),没有特殊情况,于是我们的代码可以避免由于缺少特殊情况判断(忘记判断 None)而导致的问题。

第一部分结语

这一部分我主要描述了函数式编程的基本概念,介绍了几个抽象方式,还有类型构造子、Functor 和 Option,其中类型构造子相对比较复杂,但是一旦理解就很简单了。

(本来打算一口气写完,但是似乎内容较多,一些内容我们下一步再写)