任何人都可以帮助理解函数调用中的递归 lambda 表达式和 double () () 语法吗？
Anyone could help understanding recursive lambda expressions and double () () syntax in a function call?
我不明白 foo() 函数是如何与这 2 个 lambda 一起工作的，这 3 个函数一起执行阶乘计算。
5/10/2020 更新：
我修改了代码以更好地理解这些 lambda 如何使用全局变量和每个函数内的计数器来工作。
"""7. What math operation does the following perform?"""
foo_counter = 0
bar_counter = 0
baz_counter = 0
def foo(f):
global foo_counter
foo_counter += 1
print("foo = %d" % foo_counter)
return (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))
def bar(f):
global bar_counter
bar_counter += 1
print("bar = %d" % bar_counter)
return lambda n: (1 if n < 2 else n * f(n - 1))
def baz(n):
global baz_counter
baz_counter += 1
print("baz = %d" % baz_counter)
return foo(bar)(n)
print(baz(7))
输出：
baz = 1
foo = 1
bar = 1
bar = 2
bar = 3
bar = 4
bar = 5
bar = 6
bar = 7
5040
Process finished with exit code 0
所以基本上，baz() 使用奇怪的双 () () 符号 foo(bar)(n) 调用 bar()，然后正如@Igor Mikushkin 所说，foo() 正在传递值到 bar() 使用 2 个 lambda 并定义函数 f(lambda *args: x(x)(*args))) 在其中最终调用 bar() 这是执行阶乘的函数。
但即便如此我也不明白背后的逻辑，希望有人能帮助我们理解。
我发现这样做：
print(foo(bar)(7))
也会return5040
那么，双括号在语法上的作用是这样的吗？
function_1(function_2)(argument))
我不知道这是调用函数的有效方法
让我们从语法开始。此调用 foo(bar) return 是一个函数。然后用参数 7: foo(bar)(7) 调用它。您可以将 print(foo(bar)(7)) 重写为
f = foo(bar)
print(f(7))
这个概念叫做高阶函数。在尝试理解您发布的谜题之前，您可能需要深入研究它。在 Python 中函数是 first-class 对象。它们被视为价值。您可以使用函数作为参数来调用函数。您也可以 return 一个函数中的一个函数。
代码本身就是一个谜。我不得不说这是艰难的。这当然不是学习高阶函数的最佳方式，因为它采用了这个概念并将其提升到月球。我建议你稍后再 return ，当你对这个概念有深刻的理解时。因此，与其解释，我建议举一个更简单的例子。
from typing import Callable
def g(x: int) -> int:
return x*x
def f() -> Callable[[int], int]:
return g
#1
print(f()(2))
#2
print((f())(2))
#3
h = f()
print(h(2))
为了您更好地理解，我介绍了类型注释。那么这里发生了什么？函数 f return 是一个函数 g，它得到一个 int，return 是一个 int。您调用 f 并获得此函数 g。然后你用参数 2 调用 returned 函数。这里#1、#2 和#3 是绝对等价的。我在 #2 中添加了括号以强调执行顺序。如果还不够理解我推荐你google first-class函数和高阶函数。
关于谜题。函数 bar 得到一个函数作为参数，return 得到一个函数。很明显，参数和 returned 函数应该是等价的。它来自阶乘递归定义。所以 foo 是一种非常奇特的方法，可以用这个函数的结果调用某个函数。在这里 的组合器方面对此进行了很好的解释。阅读此答案后，很明显该示例适用于了解组合逻辑并能够在代码中找到组合模式的人。尽管可以通过分解代码和应用类型注释来理解代码，但这不是正确的方向。所以我删除了我以前的建议。特别是你必须处理在 Python 类型系统中不能完全表示的无限函数类型，例如 lambda x: x(x) 的类型。所以总结一下理解它你需要知道
- 高阶函数和闭包
- 组合逻辑
也就是Y-combinator使用U-combinator实现的
U 和 Y 组合子都启用仅使用 lambda 的递归。这些示例作为学习工具非常好，可以让您了解 lambda 和闭包的惊人功能 属性。但是，以更熟悉的形式查看表达式是有意义的 -
def foo(f):
# ...
(lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))) #wtf?
实际上与-
相同1
def foo(f):
# ...
return f(lambda *x: foo(f)(*x)) # try it and see ...
或者因为bar return是单参数lambda，我们可以再简化一点-
def foo(f):
# ...
return f(lambda x: foo(f)(x))
与eta reduction，即与-
相同
def foo(f):
# ...
return f(foo(f))
对 Y 组合器来说是 alpha equivalent -
def Y(f):
# ...
return f(Y(f)) # a wild Y appears!
但是，由于 eta 缩减形式会导致 applicative-order 语言（如 Python）中 Y 的立即递归，因此肯定会发生堆栈溢出。保留 eta 扩展允许我们安全地使用 Y -
def Y(f):
return f(lambda x: Y(f)(x)) # eta expanded Y(f)
def fact (recur):
def loop (n):
if n < 1:
return 1
else:
return n * recur(n - 1) # <-- uses recur to recur
return loop
def fib (recur):
def loop (n):
if n < 2:
return n
else:
return recur(n - 1) + recur(n - 2) # <-- uses recur to recur
return loop
print(Y(fact)(7)) # 5040
print(Y(fib)(10)) # 55
请注意 fact 和 fib 如何从不称呼自己 名字 。相反，递归机制作为参数传递给函数 recur。而不是直接 return 结果，我们 return 一个函数 loop，它可以在调用 recur 时重复出现。
Python 虽然支持递归，所以这只是围绕这个更惯用的程序的大型 lambda 歌曲和舞蹈 -
<del>默认事实（重复）：</del>
<del>def 循环 (n):</del>
默认事实（n）：
如果 n < 1：
return 1
别的：
<del>return n * 重复出现(n - 1)</del>
return n * fact(n - 1) # <-- 按名称重复出现；调用事实
<del>return循环</del>
<del>def fib（重复出现）：</del>
<del>def 循环 (n):</del>
def fib (n):
如果 n < 2：
returnn
别的：
<del>return 重复(n - 1) + 重复(n - 2)</del>
return fib(n - 1) + fib(n - 2) # <-- 按名称重复；呼叫小谎
<del>return循环</del>
<del>打印(Y(事实)(7))</del>
打印（事实（7））#5040
<del>打印(Y(fib)(10))</del>
打印(fib(10)) # 55
不止一个函数参数？
上面我们看到fact和fib是单参数函数。这种模式可以与接受更多参数的函数一起使用吗？
在我们看到 Y 用于更复杂的场景之前，让我们先看看 curried function 在 Python 中使用 def -
def func (x): # func accepts x and returns inner1
def inner1 (y): # inner1 accepts y and returns inner2
def inner2 (z): # inner2 accepts z and returns x + y + z
return x + y + z
return inner2
return inner1
func(3)(3)(3) # 9
现在使用 lambda 同样的功能。注意 \ 用于 Python -
中的换行符
func = lambda x: lambda y: lambda z: \
x + y + z
func(3)(3)(3) # 9
好吧，现在我们知道这两种形式是相同的，让我们让 Y 起作用 -
Y = lambda f: \
f(lambda x: Y(f)(x))
range = lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]
reduce = lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])
add = lambda a, b: \
a + b
sum = \
Y(reduce)(add)(0)
nums = Y(range)(3)(9)
print(nums) # [ 3, 4, 5, 6, 7, 8, 9 ]
print(sum(nums)) # 42
但是等等...
那么，如果 Y 组合器是为了启用递归，为什么它有递归定义？
Y = lambda f: \ # Y = ...
f(lambda x: Y(f)(x)) # recur with Y ??
这是展示 Y 工作原理的简单方法，但是将实际递归卸载到 Python 有点像是一个廉价的技巧。准备完全离开 rails...
U-combinator登场-
U = lambda f: \
f(f) # <-- no named recursion
Y = \
U(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) # <-- no named recursion
fact = lambda r: lambda n: \
1 if n < 1 else n * r(n - 1)
print(Y(fact)(7))
# 5040
即 U。通过将函数作为参数传递给自身，函数可以使用其 参数 而不是其 名称 !
重复出现
现在因为我们所有的函数都是纯函数且 无名，我们可以显示跳过中间赋值并显示内联 lambdas -
# print(Y(fact)(7))
print( \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda n: \
1 if n < 1 else n * r(n - 1)) \
(7) \
)
# 5040
在sum(range)示例中也可以这样做-
# sum = Y(reduce)(add)(0)
sum = \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])) \
(lambda a, b: \
a + b) \
(0)
# nums = Y(range)(3)(9)
nums = \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]) \
(3) \
(9)
print(sum(nums))
# 42
并且作为一个单一的纯表达式 -
# (sum)((range(3)(9)))
print( \
((lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])) \
(lambda a, b: \
a + b) \
(0)) \
((lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]) \
(3) \
(9)) \
)
# 42
我建议您查看 this Q&A 以获得进一步的解释
1技术上...
完全不一样。原文中-
def foo(f):
global foo_counter
foo_counter += 1 # side effect 1
print("foo = %d" % foo_counter) # side effect 2
return (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))) # repeats f
通过直接使用 U 组合器 (lambda x: x(x))，f 的直接递归成为可能 而无需 重复副作用 1 和 2。
当我们在不使用 U 组合器的情况下重写 foo 时，我们会重复出现 foo（而不仅仅是 f），因此重复副作用 1 和 2 -
def foo(f):
global foo_counter
foo_counter += 1 # side effect 1
print("foo = %d" % foo_counter) # side effect 2
return f(lambda *x: foo(f)(*x)) # repeats all of foo
这是一个微小的差异，但值得一提，因为它显示了副作用的破坏性。
我不明白 foo() 函数是如何与这 2 个 lambda 一起工作的，这 3 个函数一起执行阶乘计算。
5/10/2020 更新： 我修改了代码以更好地理解这些 lambda 如何使用全局变量和每个函数内的计数器来工作。
"""7. What math operation does the following perform?"""
foo_counter = 0
bar_counter = 0
baz_counter = 0
def foo(f):
global foo_counter
foo_counter += 1
print("foo = %d" % foo_counter)
return (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))
def bar(f):
global bar_counter
bar_counter += 1
print("bar = %d" % bar_counter)
return lambda n: (1 if n < 2 else n * f(n - 1))
def baz(n):
global baz_counter
baz_counter += 1
print("baz = %d" % baz_counter)
return foo(bar)(n)
print(baz(7))
输出：
baz = 1
foo = 1
bar = 1
bar = 2
bar = 3
bar = 4
bar = 5
bar = 6
bar = 7
5040
Process finished with exit code 0
所以基本上，baz() 使用奇怪的双 () () 符号 foo(bar)(n) 调用 bar()，然后正如@Igor Mikushkin 所说，foo() 正在传递值到 bar() 使用 2 个 lambda 并定义函数 f(lambda *args: x(x)(*args))) 在其中最终调用 bar() 这是执行阶乘的函数。
但即便如此我也不明白背后的逻辑，希望有人能帮助我们理解。
我发现这样做：
print(foo(bar)(7))
也会return5040
那么，双括号在语法上的作用是这样的吗？
function_1(function_2)(argument))
我不知道这是调用函数的有效方法
让我们从语法开始。此调用 foo(bar) return 是一个函数。然后用参数 7: foo(bar)(7) 调用它。您可以将 print(foo(bar)(7)) 重写为
f = foo(bar)
print(f(7))
这个概念叫做高阶函数。在尝试理解您发布的谜题之前，您可能需要深入研究它。在 Python 中函数是 first-class 对象。它们被视为价值。您可以使用函数作为参数来调用函数。您也可以 return 一个函数中的一个函数。
代码本身就是一个谜。我不得不说这是艰难的。这当然不是学习高阶函数的最佳方式，因为它采用了这个概念并将其提升到月球。我建议你稍后再 return ，当你对这个概念有深刻的理解时。因此，与其解释，我建议举一个更简单的例子。
from typing import Callable
def g(x: int) -> int:
return x*x
def f() -> Callable[[int], int]:
return g
#1
print(f()(2))
#2
print((f())(2))
#3
h = f()
print(h(2))
为了您更好地理解，我介绍了类型注释。那么这里发生了什么？函数 f return 是一个函数 g，它得到一个 int，return 是一个 int。您调用 f 并获得此函数 g。然后你用参数 2 调用 returned 函数。这里#1、#2 和#3 是绝对等价的。我在 #2 中添加了括号以强调执行顺序。如果还不够理解我推荐你google first-class函数和高阶函数。
关于谜题。函数 bar 得到一个函数作为参数，return 得到一个函数。很明显，参数和 returned 函数应该是等价的。它来自阶乘递归定义。所以 foo 是一种非常奇特的方法，可以用这个函数的结果调用某个函数。在这里 lambda x: x(x) 的类型。所以总结一下理解它你需要知道
- 高阶函数和闭包
- 组合逻辑
也就是Y-combinator使用U-combinator实现的
U 和 Y 组合子都启用仅使用 lambda 的递归。这些示例作为学习工具非常好，可以让您了解 lambda 和闭包的惊人功能 属性。但是，以更熟悉的形式查看表达式是有意义的 -
def foo(f):
# ...
(lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))) #wtf?
实际上与-
相同1def foo(f):
# ...
return f(lambda *x: foo(f)(*x)) # try it and see ...
或者因为bar return是单参数lambda，我们可以再简化一点-
def foo(f):
# ...
return f(lambda x: foo(f)(x))
与eta reduction，即与-
相同def foo(f):
# ...
return f(foo(f))
对 Y 组合器来说是 alpha equivalent -
def Y(f):
# ...
return f(Y(f)) # a wild Y appears!
但是，由于 eta 缩减形式会导致 applicative-order 语言（如 Python）中 Y 的立即递归，因此肯定会发生堆栈溢出。保留 eta 扩展允许我们安全地使用 Y -
def Y(f):
return f(lambda x: Y(f)(x)) # eta expanded Y(f)
def fact (recur):
def loop (n):
if n < 1:
return 1
else:
return n * recur(n - 1) # <-- uses recur to recur
return loop
def fib (recur):
def loop (n):
if n < 2:
return n
else:
return recur(n - 1) + recur(n - 2) # <-- uses recur to recur
return loop
print(Y(fact)(7)) # 5040
print(Y(fib)(10)) # 55
请注意 fact 和 fib 如何从不称呼自己 名字 。相反，递归机制作为参数传递给函数 recur。而不是直接 return 结果，我们 return 一个函数 loop，它可以在调用 recur 时重复出现。
Python 虽然支持递归，所以这只是围绕这个更惯用的程序的大型 lambda 歌曲和舞蹈 -
<del>默认事实（重复）：</del>
<del>def 循环 (n):</del>
默认事实（n）：
如果 n < 1：
return 1
别的：
<del>return n * 重复出现(n - 1)</del>
return n * fact(n - 1) # <-- 按名称重复出现；调用事实
<del>return循环</del>
<del>def fib（重复出现）：</del>
<del>def 循环 (n):</del>
def fib (n):
如果 n < 2：
returnn
别的：
<del>return 重复(n - 1) + 重复(n - 2)</del>
return fib(n - 1) + fib(n - 2) # <-- 按名称重复；呼叫小谎
<del>return循环</del>
<del>打印(Y(事实)(7))</del>
打印（事实（7））#5040
<del>打印(Y(fib)(10))</del>
打印(fib(10)) # 55
不止一个函数参数？
上面我们看到fact和fib是单参数函数。这种模式可以与接受更多参数的函数一起使用吗？
在我们看到 Y 用于更复杂的场景之前，让我们先看看 curried function 在 Python 中使用 def -
def func (x): # func accepts x and returns inner1
def inner1 (y): # inner1 accepts y and returns inner2
def inner2 (z): # inner2 accepts z and returns x + y + z
return x + y + z
return inner2
return inner1
func(3)(3)(3) # 9
现在使用 lambda 同样的功能。注意 \ 用于 Python -
func = lambda x: lambda y: lambda z: \
x + y + z
func(3)(3)(3) # 9
好吧，现在我们知道这两种形式是相同的，让我们让 Y 起作用 -
Y = lambda f: \
f(lambda x: Y(f)(x))
range = lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]
reduce = lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])
add = lambda a, b: \
a + b
sum = \
Y(reduce)(add)(0)
nums = Y(range)(3)(9)
print(nums) # [ 3, 4, 5, 6, 7, 8, 9 ]
print(sum(nums)) # 42
但是等等...
那么，如果 Y 组合器是为了启用递归，为什么它有递归定义？
Y = lambda f: \ # Y = ...
f(lambda x: Y(f)(x)) # recur with Y ??
这是展示 Y 工作原理的简单方法，但是将实际递归卸载到 Python 有点像是一个廉价的技巧。准备完全离开 rails...
U-combinator登场-
U = lambda f: \
f(f) # <-- no named recursion
Y = \
U(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) # <-- no named recursion
fact = lambda r: lambda n: \
1 if n < 1 else n * r(n - 1)
print(Y(fact)(7))
# 5040
即 U。通过将函数作为参数传递给自身，函数可以使用其 参数 而不是其 名称 !
现在因为我们所有的函数都是纯函数且 无名，我们可以显示跳过中间赋值并显示内联 lambdas -
# print(Y(fact)(7))
print( \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda n: \
1 if n < 1 else n * r(n - 1)) \
(7) \
)
# 5040
在sum(range)示例中也可以这样做-
# sum = Y(reduce)(add)(0)
sum = \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])) \
(lambda a, b: \
a + b) \
(0)
# nums = Y(range)(3)(9)
nums = \
(lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]) \
(3) \
(9)
print(sum(nums))
# 42
并且作为一个单一的纯表达式 -
# (sum)((range(3)(9)))
print( \
((lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda f: lambda init: lambda xs: \
init if not xs else r(f)(f(init, xs[0]))(xs[1:])) \
(lambda a, b: \
a + b) \
(0)) \
((lambda f: \
f(f)) \
(lambda r: lambda f: \
f(lambda x: r(r)(f)(x))) \
(lambda r: lambda start: lambda end: \
[] if start > end else [ start, *r(start + 1)(end) ]) \
(3) \
(9)) \
)
# 42
我建议您查看 this Q&A 以获得进一步的解释
1技术上...
完全不一样。原文中-
def foo(f):
global foo_counter
foo_counter += 1 # side effect 1
print("foo = %d" % foo_counter) # side effect 2
return (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args))) # repeats f
通过直接使用 U 组合器 (lambda x: x(x))，f 的直接递归成为可能 而无需 重复副作用 1 和 2。
当我们在不使用 U 组合器的情况下重写 foo 时，我们会重复出现 foo（而不仅仅是 f），因此重复副作用 1 和 2 -
def foo(f):
global foo_counter
foo_counter += 1 # side effect 1
print("foo = %d" % foo_counter) # side effect 2
return f(lambda *x: foo(f)(*x)) # repeats all of foo
这是一个微小的差异，但值得一提，因为它显示了副作用的破坏性。