10

我必须为 > 、 < 和 != 创建一些 Lambda 函数

我不知道怎么做,有人可以帮我吗?PS:我们刚开始学习 Lambda 演算,所以请不要假设任何先前的知识。

谢谢你的期待!

编辑- 我的意思是Lambda 演算中的算术

编辑 2 - 更准确:寻找 Church-encoding (lambda calculus) 来定义 < , > , !=


编者注:我认为这是 OP 试图问的:

我正在尝试使用 Church 编码在无类型 lambda 演算中实现以下操作:

  1. 大于(GT>)。
  2. 小于(LT<)。
  3. 不等于 (NE!=)。

我已经知道如何实现以下内容:

  1. 布尔真(TRUEλx.λy.x)。
  2. 布尔假(FALSEλx.λy.y)。
  3. 逻辑和(ANDλp.λq.p q p)。
  4. 逻辑或(ORλp.λq.p p q)。
  5. 逻辑非(NOTλp.λa.λb.p b a)。

您将如何在无类型 lambda 演算中编写GTLT和函数?NE

4

3 回答 3

5

使用Greg Michaelson 的“通过 Lambda 演算介绍函数式编程”

从...开始

第 4.8.3 节。比较

有多种方法可以定义数字之间的相等性。一种方法是注意两个相等数字之间的差异为零。但是,如果我们从一个较小的数字中减去一个数字,我们也会得到零,因此我们需要找到它们之间的绝对差;无论比较顺序如何,差异。要找到两个数字之间的绝对差,请将第一个和第二个之间的差加上第二个和第一个之间的差:

def abs_diff xy = add (sub xy) (sub yx)

如果它们都相同,那么绝对差异将为零,因为从另一个中获取的结果将为零。如果第一个大于第二个,则绝对差将是第一个减去第二个,因为第二个减去第一个将为零。同样,如果第二个大于第一个,则差值将是第二个减去第一个,因为第一个减去第二个将为零。

因此,我们可以定义:

def 等于 xy = iszero (abs_diff xy)

我们还可以使用减法来定义算术不等式。例如,如果从第一个数中减去第二个数会得到非零结果,则一个数大于另一个数:

def 更大 xy = not (iszero (sub xy))

在后面的练习部分的解决方案中定义了较少。

def 小于 xy = 更大的 yx

现在使用链接中的书只需找到所有从属函数,您将拥有 =、>、<。虽然这本书没有定义 != 它应该是显而易见的。

编辑

根据 WillNess 的评论

4.8.2. 减法

要找到两个数字之间的差异,请在减少两个数字后找到数字之间的差异。数字和零之间的区别是数字:

rec sub xy =
if iszero y
then x
else sub (pred x) (pred y)

请注意"Now using the book in the link just find all of the subordinate functions".

我不打算搜索所有从属功能并在此处列出它们,因为它们会爆炸成在这里重新创建许多功能。我已经阅读并通读了本书的部分内容,它足够全面,我并不缺乏信息。

于 2013-12-11T22:12:44.980 回答
3

您还需要实现自然数。这就是您要编写比较运算符的目的,不是吗。

我想我记得自然数的实现。数字n表示为一个函数,该函数采用函数f和值x,并在x上应用f n次。

zero = λf . λx . x
succ = λn . λf . λx . n f (f x)
于 2013-12-11T20:12:17.307 回答
2

关于教堂编码的维基百科文章有一个关于谓词的部分,涵盖EQLEQ

于 2013-12-13T00:16:48.640 回答