Мы знаем, что λ-исчисление лишено поддержки рекурсии. Также мы знаем, что использование λ-функций часто помогает сделать запись программы красивее и лаконичнее. В любом случае, возникают ситуации, когда достижению этой благородной цели мешает невозможность сделать рекурсивный вызов λ-функции.

Здесь нам поможет Y-комбинатор.

Итак, я не в состоянии дать определение, выводы и основы комбинаторной логики, потому что Саклесс ни разу не об этом. Несмотря на это, следует вкратце рассказать об этом комбинаторе.

Комбинатор Y помимо его названия с латинской (или какой там?) буквой “Y” называют «парадоксальным», благодаря его связи с самоотносимостью. Это свойство самоотносимости позволяет нам реализовать рекурсию над лямбда-исчислением. Мило, не правда ли?

Итак, реализовать это можно как-то так:

def Y
  lambda { |f| f.call(f) }.call(
    lambda do |g|
      yield(lambda { |*n| g.call(g).call(*n) })
    end)
end

Раньше для реализации функции рекурсивного подсчёта факториала целого числа приходилось писать отдельный метод. Как правило, в таких случаях декларация отдельного метода выглядит не так изящно, как запись λ-функции:

fact = Y { |this|
  lambda do |n|
    (n > 1) ? n * this.call(n - 1) : 1
  end
}

p fact.call(5) # => 120

Вуаля! Результат одинаков, но давайте посмотрим, как дела с производительностью? Для этого закатаем простой бенчмарк: объявим метод вычисления факториала, объявим метод создания Y-комбинатора, объявим λ-функцию вычисления факториала, а потом погоняем всё это дело на разных n.

Результат несколько огорчает. При использовании λ-функций мы гораздо раньше напарываемся на ограничение уровня стека, чем при использовании методов. Это довольно печально, хотя на этом проблемы не заканчиваются.

Уже на маленьких n временные затраты (real) на вызовы λ-функции превышают тупой вызов метода. С увеличением n разрыв идёт уже не на один, а на два порядка, то есть вариант с Y-комбинатором медленнее в сто раз! Как решить эту проблему?

На хабре в аналогичной статье человек предлагает решать эту проблему на Python при помощи промежуточного кэширования. Думаю, это поможет, но в таком случае становится несколько страшно смотреть на реализацию этого дела.

Y-комбинатор позволяет избавить себя от лишнего объявления метода при использовании функции, требующей рекурсии.

В случае обработки деревьев, списков или чего-то в этом роде, этот приём позволяет сделать код красивым, чистым и шелковистым. К сожалению, придётся несколько пожертвовать производительностью, но в любом случае это лучше, чем превращать код в лапшу. И это хорошо.