跳到主内容

面向眼科医生的λ演算入门教程(6)

一生二

有了Church numeral以后非负整数就都可以定义了。有了数据,还要有数据结构才行。

吐槽一下我的大学课程设置,计算机必修课叫《算法与数据结构》,学了一学期的Fortran 77,只讲了Fortran的语法,我敢说除了计算机课跷课的和上课睡觉的,我们班同学里肯定没人知道动态规划(算法)或者堆栈(数据结构)。

最基本的数据结构就是一对数据了,从数据对又可以衍生出二叉树、链表,在此基础上又可以衍生出各种各样的数据结构。如果有了一对数据,就要能够提取其第一个元和第二个元。因此需要有三个操作,pair用来构造,first, second用来读取。

pair=λx.λy.λz.(z x y)
first=λp.p (λx.λy.x)
second=λp.p (λx.λy.y)

试试看:

pair a b
=(λx.λy.λz.(z x y)) a b
=λz.(z a b)
first (pair a b)
=λp.p (λx.λy.x) λz.(z a b)
=λz.(z a b) (λx.λy.x)
=(λx.λy.x) a b
=a

里面λp.p和λz.z好像是个小技巧,可以用来把后面的东西提前面来用。

仔细看看这数据结构的定义,感觉就像循环定义一样无中生有嘛,pair就是一对expression,first就是一对expression的前一个,second就是一对expression的后一个。

有了二,就可以有三有多了。比如三元的表:

list3=pair a (pair b (pair c nil)

nil表示一个表结尾标记,比如在C语言中用\0作为字符串的结尾。

如果要取表中的第三个位置,那就first( second (second list) )

有pair以后,其实就可以定义整数之外的数了, 有理数可以写成一对整数(分子, 分母),比如0.8=4/5,用(4,5)这样的结构就可以表示了。 复数可以写成(实部, 虚部)的pair 有理复数,可以加入一些标记,比如用c作为复数标记,用r作为有理数标记,那么一个有理复数可以使用这样的结构:(c,(实部, 虚部)),继续展开是(c, ( (r,(分子,分母), (r,(分子,分母) ) ) 甚至用一个表来模拟8位字节

只要数的定义有相应的运算法则可以操作就可以了。 有了二,就有了数据结构。