0

我的输入是两个列表，即 l = [x1, x2, x3,...,xn] 和 k = [y1, y2, y3,...,yn]

我想要 ay = [(x1,y1),(x2,y2),(x3,y3)...(xn,yn)] 输出。

如何将递归应用于我的代码？我可以为第一个项目做到这一点， f = \l k. (cons (pair (head l) (head k)) empty)但我不明白如何使用递归来创建其他项目。

函数“head”返回列表的第一项，函数“tail”返回没有第一项的列表。

4

1 回答 1

0

自然，这完全取决于您如何在 Lambda 演算中实现元组、列表等。但是假设标准功能cons列表，并且两个列表的长度相同，并且您已经定义了以下帮助程序，其中一些您已经引用了：

cons    -- construct a list from a node and another list
empty   -- the empty list
head    -- retrieve the first node value of a list
tail    -- retrieve all but the first node of a list
pair    -- pair values into a tuple
isEmpty -- return `true` if a list is `empty`, `false` otherwise
true    -- return the first argument
false   -- return the second argument

然后我们可以递归地压缩列表，如下所示：

ZIP = λlk. isEmpty l -- "if the list is empty…"
           empty     -- "return an empty result. Else…"
           (cons     -- "return a new list, containing…"
               (pair (head l) (head k))  -- "the zipped heads, and…"
               (ZIP  (tail l) (tail k))) -- "everything else zipped."

问题当然是原始的 lambda 演算没有递归。您不能在其自己的定义中引用函数名称。答案是使用定点组合器，例如著名的Y组合器。

ZIP = Y (λzlk. isEmpty l empty (cons (pair (head l) (head k)) (z (tail l) (tail k)))

的定义Y是：

Y = λf.(λx.f(x x))(λx.f(x x))

解开它的工作原理是一个令人印象深刻的心理体操，这不是这个问题的范围，但使用它非常简单。一般来说，如果你有一个想要的（但在原始 LC 中是非法的）递归定义，如下所示：

R = λ ??? . ??? R ???

你可以把它写成完全合法的、非递归的定义：

R = Y (λr ??? . ??? r ???)

换句话说，为您的函数添加一个新参数，它代表您的递归函数，并用于Y为您连接所有内容。Y能从零开始发明递归是非同寻常的，也是它如此出名的原因。

于 2018-09-25T03:14:18.217 回答