U-комбинатор на Питоне

предыдущая серия

То, что мы рассмотрели ранее, либо подходит узкому кругу разработчиков языков, либо интересно исключительно с теоретической позиции. На практике же лямбда-исчисления наиболее интересны, пожалуй, своими комбинаторами.

Начнём с U-комбинатора.

U-комбинатор — это функция, которая применяет свой аргумент к самой себе:

U = lambda f: f(f)

На первый взгляд, тут возникает зацикленная рекурсия, и если применять U-комбинатор в лоб, мы действительно получим stack overflow (так как, в частности, Питон полноценно не поддерживает хвостовую оптимизацию).
В функциональных языках, где вычисления могут быть отложены, такой код будет просто «non-terminate».

Практической пользы от этого пока тоже никакой, но напрашивается что-то, связанное с рекурсией. Вспомним классическое определение факториала:

fact = lambda n: 1 if n <= 0 else n*fact(n-1)

Можно попробовать избавиться от явной рекурсии так:

fact = ((lambda n: 1 if n <= 0 else n*fact(n-1))
(lambda n: 1 if n <= 0 else n*fact(n-1)))

Проблема возникнет с неоднозначностью трактовки видимости параметра n, поэтому в Питоне сработает такой трюк:

fact = ((lambda f: lambda n: 1 if n <= 0 else n*fact(n-1))
(lambda f: lambda n: 1 if n <= 0 else n*fact(n-1)))

Однако мы по-прежнему записываем рекурсивный вызов fact, и U-комбинатор и поможет от него избавиться: U(f) к счастью создаст новую ссылку на fact!

fact = ((lambda f: lambda n: 1 if n <= 0 else n*(U(f))(n-1))
(lambda f: lambda n: 1 if n <= 0 else n*(U(f))(n-1)))

Собственно, сам этот код и есть U-комбинатор!

fact = U(lambda f: lambda n: 1 if n <= 0 else n*(U(f))(n-1))

fact(5) # 120

По сути, мы описали рекурсию исключительно в терминах анонимных лямбда-функций с помощью U-комбинатора.

Далее займёмся Y-комбинатором.

Поделиться статьей ...Share on Facebook0Share on Google+0Tweet about this on TwitterShare on LinkedIn0Share on VKPrint this page

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *