使用lambda演算代表负和复数

Question

Lambda演算上的大多数教程提供了示例，其中正整数和布尔值可以由函数表示。 -1和我呢？

Answer 1

如JMAD所述，首先编码自然数和对。

代表整数$ k $作为一对自然数字$（a，b）$，这样$ k = a -b $。然后，您可以将整数上的通常操作定义为（使用$ lambda $ -calculus的Haskell符号）：

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

从某种意义上说，复杂数字被编码为一对真实的意义上，复数的情况相似。但是一个更复杂的问题是如何编码真实。在这里，您必须做更多的工作：

1. 编码一个有理数$ q $作为一对$（k，a）$，其中$ k $是整数，$ a $是自然的，$ q = k /（1 + a）$。
2. 用函数$ f $编码一个实际数字$ x $，以便对于 mathbb {n} $，$ fk $编码的每个天然$ k in mathbb中的每个天然$ k 编码$ | x -q | <2^{ - k} $。换句话说，一个真实的编码为以$ k mapsto 2^{ - k} $的速率融合到它的一系列理由。

编码Reals是很多工作，您不想在$ lambda $ -calculus中实际进行。但是请参阅 etc/haskell 子目录的 马歇尔 为了简单地实现纯Haskell中的真实。原则上可以将其转换为纯$ lambda $ -calculus。

Answer 2

Lambda-Calculus可以编码大多数数据结构和基本类型。例如，你可以 编码一对 使用相同的lambda微积分中的现有术语 教堂编码 您通常认为编码非负整数和布尔值：

$$ mbox {pair} =λxyz.zxy$$ $ $ $ mbox {fst} =λp.p（λxy.x）$$ $ $ $ $ mbox {snd} =λp.p.p（λxy.y）$$

然后，$（a，b）$是$ p =（ mbox {pair} ab）$，如果要拿回来$ a $ a $ a $ a $ b $，您可以做$（ mbox {fst} p）$和$（ mbox {snd} p）$。

这意味着您可以轻松地用一对：左侧的符号以及右侧的绝对值来表示正整数：符号。该标志是指定数字是否为正的布尔值。权利是使用教堂编码的自然数字。

$$（标志，n）$$

现在您有了相对整数。乘法易于定义，您只需要应用 $ mbox {xor} $函数 在标志和 自然数乘以 关于绝对值：

$ mbox {mult}_ℤ=λab。 mbox {pair} ~~（ mbox {xor}（ mbox {fst} a）（ mbox {fst} b））~~（ mbox { mbox {mult} （ mbox {snd} a）（ mbox {snd} b））$$

要定义添加，您必须比较两个自然数并在符号不同时使用减法，因此这不是λ任期，但是如果您真的想，则可以对其进行调整：

$ mbox {add}_ℤ=λab。 left { begin {array} {ll}（ mbox {true}， mbox {add}_ℕ（ mbox {snd} a） b））＆ mbox {if}a≥0∧b≥0（ mbox {false}， mbox {add}_ℕ（ mbox {snd} a）（ mbox {snd} b）） mbox {if} a <0∧b<0 （ mbox {true}， mbox {sub}_ℕ（ mbox {snd} a）（ mbox {snd} b）b）＆ mbox {if} a ≥0∧b<0∧| a |≥| b | （ mbox {false}， mbox {sub}_ℕ（ mbox {snd} b）（ mbox {snd} a））） | B | （ mbox {true}， mbox {sub}_ℕ（ mbox {snd} b）（ mbox {snd} a））） | B | （ mbox {false}， mbox {sub}_ℕ（ mbox {snd} a）（ mbox {snd} b））） | B | end {array} right。$$

但是然后减去真的很容易定义：

$ mbox {minus}_ℤ=λa。 λab。 mbox {add}_ℤ（a）（ mbox {minus}_ℤB）$$

一旦您拥有正面和负面整数，您就可以定义 复杂的整数 非常容易：这只是一对两个整数$（a，b）$，代表$ a+a+b mbox {i} $。然后添加是点的，乘法是 照常, ，但我不会写，这应该很容易：

$ mbox {add} _ { mbox { mbox {i}]} =λz_1z_2。 （ mbox {add}_ℤ（ mbox {snd} z_1）（ mbox {snd} z_2））$$