Это Y-комбинатор , реализованный с использованием U-комбинатора.
Комбинаторы U и Y позволяют рекурсию с использованием только лямбда-выражений. Эти примеры хороши как инструмент обучения и могут научить вас удивительным возможностям лямбда-выражений и свойству замыкания. Однако имеет смысл увидеть выражение в более знакомой форме -
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 возвращает однопараметрическую лямбду, мы можем еще немного упростить -
def foo(f):
# ...
return f(lambda x: foo(f)(x))
С сокращением эта , то же самое, что -
def foo(f):
# ...
return f(foo(f))
Что является альфа-эквивалентом Y-комбинатору -
def Y(f):
# ...
return f(Y(f)) # a wild Y appears!
Однако, поскольку эта-сокращенная форма вызывает немедленную рекурсию Y в аппликативном порядке язык (например, Python), переполнение стека гарантировано. Если оставить eta-extension на месте, мы можем безопасно использовать 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. И вместо того, чтобы возвращать результат напрямую, мы возвращаем функцию loop, которая может повторяться при вызове recur.
Python поддерживает рекурсию, так что это всего лишь большая лямбда-песня и танцевать вокруг этой более идиоматической c программы -
<del>def fact (recur):</del>
<del>def loop (n):</del>
def fact (n):
if n < 1:
return 1
else:
<del>return n * recur(n - 1)</del>
return n * fact(n - 1) # <-- recur by name; call fact
<del>return loop</del>
<del>def fib (recur):</del>
<del>def loop (n):</del>
def fib (n):
if n < 2:
return n
else:
<del>return recur(n - 1) + recur(n - 2)</del>
return fib(n - 1) + fib(n - 2) # <-- recur by name; call fib
<del>return loop</del>
<del>print(Y(fact)(7))</del>
print(fact(7)) # 5040
<del>print(Y(fib)(10))</del>
print(fib(10)) # 55
более одного аргумента функции?
Выше мы видим fact и fib как однопараметрические функции. Может ли этот шаблон работать с функциями, которые принимают больше аргументов?
Прежде чем мы увидим, что Y используется в более сложном сценарии ios, давайте сначала посмотрим на каррированную функцию в 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 вроде как дешевый трюк. Приготовьтесь полностью go сойти с рельсов ...
U-комбинатор выходит на сцену -
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. Передавая функцию себе в качестве аргумента, функция может повторяться, используя свой параметр вместо своего имени !
Теперь, потому что все наши функции чистые и безымянный , мы можем показать пропускать промежуточные назначения и показать встроенные лямбды -
# 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
Я рекомендую вам проверить этот 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.
Когда мы переписываем foo без U-комбинатора, мы повторяем 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
Это разница незначительна, но ее стоит упомянуть, поскольку она показывает разрушительное качество побочных эффектов.