Python: 使用 cons、car 和 cdr 的函数式编程

Question

有个问题是这样的：

cons(a, b) constructs a pair, and car(pair) and cdr(pair) returns the first and last element of that pair. For example, car(cons(3, 4)) returns 3, and cdr(cons(3, 4)) returns 4.

现在，我已经看到了解决方案，但我想知道是否有人可以解释如何真正思考以达到解决方案？

cdr(cons(3, 4))：这两个函数的求值顺序是什么？我通常认为 cons(3, 4) 首先被评估，但在这种情况下这没有意义，因为 cons(3, 4) return 是一个函数，其中参数 3 和 4 被“集成”，所以有无法挑出论点。
在我看来car(f)return是一个函数，那么cons(3, 4)return3怎么可能呢？编辑：打字错误，应该是car(cons(3, 4))而不是cons(3, 4)
我显然是想解决这个问题，因为我想学习 Python，但是你会建议我跳过这些问题吗？我很想在这里阅读：Why program functionally in Python?

解决方案：

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

def car(f):
    def pair(a,b):
        return a
    return f(pair)

def cdr(f):
    def pair(a, b):
        return b
    return f(pair)

print(car(cons(3,4)))
Output: 3
print(cdr(cons(3,4)))
Output: 4

Answer 1

您粘贴的代码应该像这样使用：

首先，您定义您的配对：

f = cons(3, 4)

之后，您定义一个对数对起作用的函数：

add = lambda x, y: x + y

现在，您可以像这样使用您的“对”：

f(add)

输出：

因此，它所做的是：它将 Your pair 转换为一个函数，该函数可以以定义的 pair 作为参数在 pair 上“执行”函数。 car 和 cds 实际上可以“转换”你的 pair-function 和 return 一个元素。

编辑：

如果您不熟悉 lambda 表达式，请参阅 this tutorial。

现在，您也可以选择

def add(x, y):
    return x + y

并以同样的方式使用它。 :)

Answer 2

在 a(b()) 中，b 将总是首先计算。我不知道 Python 中有一个例外。 a 需要是一个宏才能使反向为真。

注意 cdr 和 car 的参数名称是什么：f，如“函数”。每个函数都接受一个函数作为参数。不过，这是可行的，因为正如您所指出的，cons return 是一个函数。

在car(cons(3,4))中，cons return是一个函数（本地称为pair）。然后将该函数提供给 car，car 在这里使用它：f(pair)。在这种情况下，f 是传入的函数。这里复杂的部分是 f 是一个函数，它接受 另一个 函数，并调用它两个参数。这两个参数是最初提供给 cons 的数据：3 和 4.

cons(3, 4) 不是 return 3，car(cons(3,4)) 是。 cons(3, 4) return 是一个作用于提供给它的数据的函数。在这种情况下，car 的 pair 函数最终会丢弃第二个传递的参数 (4)，取而代之的是 return 第一个 (3) .

是的，暂时远离这样的代码。传递函数非常有用，但这段代码更像是一个实验性的玩具。它是显示样式的理论代码（源自基于术语的 Scheme 之类的 lisp）。有许多更简单的方法可以达到相同的最终结果。

练习 Higher Order Functions 的简单示例（如 map 和 reduce），熟练使用它们，然后重新访问此代码。它仍然很难理解（因为这段代码本身并不容易理解），但它会更有意义。

Answer 3

你给出的问题也可以这样解决

def cons(a, b):
    return (a,b)

def car(pair):
    return pair[0]

def cdr(pair):
    return pair[1]

您将如何使用它：

lst = cons(1,cons(2,3))

# Get the first element of lst
print(car(lst))

# Get the second element of lst
print(car(cdr(lst)))

# Get the last element of lst
print(cdr(cdr(lst)))

输出：

1
2
3

我展示这个只是为了让您看到解决该问题的方法不止一种，而您发现的方法在 python 中很少有人采用。任何想在 python 中解决这个问题的人都会在 99% 的时间里按照我在这里展示的方式来做。

现在开始解决您的问题。

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

def car(f):
    def pair(a,b):
        return a
    return f(pair)

def cdr(f):
    def pair(a, b):
        return b
    return f(pair)

首先让我们使用一些haskell函数符号来讨论这些函数，以便您可以看到这些函数的完整类型：

`cons::(a, b) -> (((a, b) -> c) -> c)`

cons 是一个接受两个参数 a 和 b 的函数，然后它 return 是一个接受另一个函数的函数 f，当给定参数 (a,b), returns c, 其中 c 可以是 a 或 b, 或别的东西。 f 然后 returns c 的值。

真是一口啊！

另一种理解方式是由cons编辑的函数f (((a, b) -> c) -> c) return用于转发a和b 到任何想要作用于 cons 的运算符（或映射函数）。此运算符 returns c。 f 然后简单的 returns 不管这个映射函数 returns，它恰好是 c.

现在不用担心 c 是什么。想想它是将函数应用于 cons.

的结果

`car::(((a, b) -> a) -> a) -> a`

car 定义了从 (a,b) 到 c 的可能映射，并且 return 是使用此映射调用 f 的值。

car 采用一个函数 f，它需要从输入 (a,b) 到某个输出 c 的映射。在这种情况下，car 将映射定义为 (a, b) -> a，这意味着传递给 car 的任何函数 f 都将 return 作为 [=40= 的第一个参数]，也就是 a。这就是 car 将要 return。

`cdr::(((a, b) -> b) -> b) -> b`

类似于car，但是映射是由cdr returns b而不是a定义的映射。

请注意 cdr 和 car 的输入与 cons 编辑的函数 (f) return 有多么相似？这就是为什么我只是将他们的输入称为 f

现在回答你的一些问题：

cdr(cons(3, 4)): in what order are these two functions evaluated? I would normally think that cons(3, 4) are evaluated first, but that does not make sense in this case, because cons(3, 4) returns a function where arguments 3 and 4 are "integrated", so there is no way of singling out the arguments.

根据我上面给出的解释，从 cons 编辑的函数 return 与 cdr 期望的函数类型完全相同。现在 cdr 所要做的就是为 f 和 return 提供映射函数，无论 f returns.

It seems to me that car(f) returns a function, so how can cons(3, 4) return 3? EDIT: typo, should be car(cons(3, 4)) instead of cons(3, 4)

car(f) 不一定是 return 函数。请参阅上面的类型签名。它只是 returns 任何 f returns 如果它恰好是一个函数，那么它就是 return 一个函数。

一般来说，car return 是 cons 的第一个元素。在这种情况下，由于 cons(3,4) return 是一个函数 (f) 并且此函数被传递给 car，因此 car 将为该函数提供另一个函数选择它的第一个参数，在本例中为 3。 3 现在是 car(cons(3,4).

的结果

我希望事情已经解决了。

Python: 使用 cons、car 和 cdr 的函数式编程

Python: functional programming with cons, car & cdr

python

functional-programming

cons

cdr

输出：

`cons::(a, b) -> (((a, b) -> c) -> c)`

`car::(((a, b) -> a) -> a) -> a`

`cdr::(((a, b) -> b) -> b) -> b`