复合数据只要拥有满足一定条件的构造函数、选择函数和约束规则,甚至不需要是由基本数据复合,church 计数是一个以 lambda 表达式为唯一元素,构建数值、数值运算等编程要素的系统,在church 计数中 0 和 加1 运算分别被定义为

1
2
3
4
5
6
7
8
9
10
11
12
func zero<T>(f:(T->T)) -> T->T {
return {x in
return x}
}
func add_1<T>(n:(T->T) -> T->T) -> (T->T) -> T->T {
return {f in
return {x in
return f(n(f)(x))
}
}
}

0 是一个以函数为参数返回一个函数的过程,加1 运算是作用于类似 0 这样的过程之上返回一个新过程的函数,将 0 带入 加1 运算得到 1 的定义,带入 1 得到 2 的定义

1
2
3
4
5
6
7
8
9
10
func one<T>(f:(T->T)) -> T->T {
return {x in
return f(x)}
}
func two<T>(f:(T->T)) -> T->T {
return {x in
return f(f(x))
}
}

形式上讲 church 计数的正整数可以看做应用参数函数的过程,0 是应用 0 次直接返回原值,1 是返回应用 1 次得到的返回值,以此类推。加法的定义是先应用第一个加数次,再应用第二个加数次,乘法是应用次数之积次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func plus<T>(operand1 operand1: (T->T) -> T->T, operand2: (T->T) -> T->T) -> (T->T) -> T->T {
return {f in
return {x in
return operand2(f)(operand1(f)(x))
}
}
}
func mult<T>(operand1 operand1: (T->T) -> T->T, operand2: (T->T) -> T->T) -> (T->T) -> T->T {
return {f in
return {x in
return operand2(operand1(f))(x)
}
}
}

减法的定义先考虑简单的情况,任意给定一个过程进行减 1,从概念上讲应该是应用给定过程的减 1 次,实现方法:

我没想出来