前言
在咱们曾经把握了那么多建管子的办法之后,咱们开始切题,看看咱们能用起码的概念做哪些自举产生的事。在这一章中咱们讲仅应用字符串 "e"
,函数,if-else
分支,=="e"
运算,这四个概念来实现一个自然数的概念(理论中还用到了 bool
值,不过 bool
自身也能够用 "e"
和f("e")
示意)。
皮亚诺公理
咱们首先回顾一下,数学如何定义即皮亚诺公理如何定义自然数,事实上,皮亚诺公理定义的是「有限可数集」的概念
- (1) $$e \in S$$
- (2) $$(\forall a \in S)(f(a) \in S)$$
- (3) $$(\forall b \in S)(\forall c \in S)(f(b) = f(c) \rightarrow b = c)$$
- (4) $$(\forall \in S)(f(a) \ne e)$$
- (5) $$(\forall A \subseteq S)(((e \in A) \land (\forall a \in A)(f(a) \in A)) \rightarrow (A = S))$$
- (1) 示意咱们须要一个初始值,来表述咱们能够从第一个货色开始数数,在这个符号集里叫 \(e\)。对应于自然数的「1」的概念。
- (2) 示意往下数一个数的操作,这个符号集里用 \(f\)表述,咱们个别也把这个操作叫 后继。对应自然数中「加一」/「往下数一」的概念
- (3) 确定恒等关系。
- (4) 确定 \(e\)不是任何数的后继,保障它是第一个被数的数。
- (5) 归纳法
实现
咱们仅仅须要上面两行代码就曾经实现了自然数的全副定义,咱们应用递归示意向下数数,用 "e"
表白了起始值「1」
one = "e" # 1
f = lambda x: lambda : x # 后继
当然,这么一个定义,是没有任何意义的,咱们还须要实现 判断相等 、 加法 、 乘法 这三个最简略的算法。首先判断全等的办法就是咱们将两个函数有限地求值上来,看到最初是不是同时失去 "e"
值,这也是对应了性质(3):
def equal(x, y) -> bool:
if x =="e" and y =="e":
return True
elif x =="e":
return False
elif y =="e":
return False
else:
return equal(x(), y())
not_equal = lambda x, y: not(equal(x, y))
留神我在下面的实现中应用了 x =="e"
这种后面带空格而前面不带空格的写法,其实是为了强调,=="e"
是一个一元运算,咱们仅应用到了它,而不须要其余概念。而认真探索这个算式,咱们发现其实它也隐式地用到定义 (4),只有一个不为"e"
咱们就能够确定它们是不相等的。
定义加法其实也是一个非常容易的操作,咱们只须要让一个参数计算后继,一个参数求值产生前继的概念:
def add(x, y):
if y =="e":
return f(x)
else:
return add(f(x), y())
最初是乘法的概念,这个咱们能够调用 add
来递归实现:
def multiply(x, y):
if y =="e":
return x
else:
return add(multiply(x, y()), x)
其实咱们也能够同理取得一个自然数求幂的函数,十分相似下面 multiply
的实现
def power(x, y):
if y =="e":
return x
else:
return multiply(power(x, y()), x)
这样咱们能够十分疾速地给 20 以内的数取名字了:
one = "e"
two = f(one)
three = f(two)
four = f(three)
five= f(four)
six = f(five)
seven = f(six)
eight = f(seven)
nine = f(eight)
ten = f(nine)
eleven = f(ten)
twelve = f(eleven)
thirteen = f(twelve)
fourteen = f(thirteen)
fifteen = f(fourteen)
sixteen = f(fifteen)
seventeen = f(sixteen)
eighteen = f(seventeen)
nineteen = f(eighteen)
OK,最初咱们能够通过 equal
验证咱们的算法对不对:
>>> assert equal(add(two, one), three)
>>> assert not_equal(power(two, three), seven)
>>> assert equal(power(two, three), eight)
>>> assert equal(multiply(three, five), fifteen)
结语
这一篇咱们偏题地实现了一个「自然数」的定义,目标是为了展示,函数式编程的魅力在于:
- 咱们能够用非常少的概念(在这个例子中是 4 个)就能够自举地实现十分多的事件。这个也是晚期 LISP 语言(一种常见的动静函数式语言)会那么在 AI 畛域或者一些对语言内核大小十分敏感的畛域的起因。
- 因为函数式编程中的函数和数学上的函数十分靠近,这使得在数学上应用的代数运算,都能够十分不便的实现(当然这一点咱们在前面也会一一例举进去)。