不使用后继函数定义 lambda 加法

Question

我熟悉在 SUCC 函数之上定义 ADD 函数，如下所示：

const ONE = f => a => f(a);   
const SUCC = n => f => a => f(n(f)(a));        // SUCC = λnfa.f(nfa)
const ADD = n1 => n2 => n1(SUCC)(n2);          // ADD  = λnk.n SUCC k 
console.log(ADD(ONE)(ONE)(x => x+1)(0));
// 2

但是，如果没有已定义的后继函数，我将如何定义 add？我尝试使用替换来获得以下内容，但我不确定为什么它不起作用。我在这里搞砸了什么？

const ONE = f => a => f(a);
const ADD = n1 => n2 => f => a => n1(f(n1(f)(a)))(n2);
console.log(ADD(ONE)(ONE)(x => x+1)(0));
// TypeError: f is not a function

Answer 1

const ADD = n1 => n2 => n1(n => f => a => f(n(f)(a)))(n2)
// ADD = λnk.n (λnfa.f (n f a)) k

这也可以是eta-reduced到

const ADD = n1 => n1(n => f => a => f(n(f)(a)))
// ADD = λn.n (λnfa.f (n f a))

进行替换时，只需将要替换的术语替换为其定义即可：

n1 => n2 => n1(SUCC)(n2)
SUCC的定义：n => f => a => f(n(f)(a))
用上面的定义替换SUCC：n1 => n2 => n1(n => f => a => f(n(f)(a)))(n2)

另一种定义 ADD 的方法是这样的：

const ADD = m => n => f => x => m(f)(n(f)(x))
// ADD = λmnfx.m f (n f x)

教堂数字 m 和 n 可以看作是采用函数 f 并产生另一个应用 f 特定次数的函数的函数。换句话说，n(f)可以看作是“重复fn次”。

因此，ADD(m)(n) 应该 return 一个重复函数 m + n 次的函数。

const ADD =
  m => // first number
  n => // second number
  f => // function to be repeated
  x => // value
  (
    m(f) // 2. then apply f m times
    (n(f)(x)) // 1. apply f n times
  )

ADD(ONE) 也等同于 SUCC（如您所料）：

ADD(ONE)
(m => n => f => x => m(f)(n(f)(x)))(ONE)（ADD的定义）
n => f => x => ONE(f)(n(f)(x)) (beta-reduction)
n => f => x => (f => a => f(a))(f)(n(f)(x))（ONE的定义）
n => f => x => (a => f(a))(n(f)(x)) (beta-reduction)
n => f => x => f(n(f)(x)) (beta-reduction)
SUCC（SUCC的定义）

有关详细信息，请参阅 ‘Church encoding’ on Wikipedia。

不使用后继函数定义 lambda 加法

Defining lambda addition without using the successor function

javascript

functional-programming

lambda-calculus