Поводом для написания этой статьи стало желание разобраться с тем, как работает Y-комбинатор.

Чтобы мозги не ржавели и работали как часы, я стараюсь пробовать новые и необычные вещи.
Интереса ради, я скомпилировал Lua 5.x под DOS, с этим никаких проблем не было, но при проверке Lua на её стандартных тестах, я обнаружил код вычисления факториала, работу которого я не понял.
Но ясно осознал, что это нечто относится к функциональному программированию.



В итоге нашёл статью в Википедии, статью про практическое использование в Ruby и статью про Y-комбинатор на Python'е, при разборе которой я, наконец-то хоть что-то понял.

Y-комбинатор позволяет превратить обычную (в том числе и анонимную) функцию в рекурсивную. Основная его ценность — теоретическая, для обоснования теорий формальных вычислений, но некоторые находят для него практическое применение (такое ощущение появилось после чтения комментариев к вышеупомянутым статьям).

Из Википедии следует, что Y-комбинатор — это частный случай функций высшего порядка, которые принимают на вход функцию f и возвращают функцию g, такую, что f(g)=g. Может это и так, но пользы для понимания это определение мне не дало^[1][2].

Попробуем разобраться на классическом примере факториала как это всё работает. Использоваться будет Python, потому что с ним я больше знаком.

В процессе разбора будет использоваться вспомогательная функцию dumb, от которой мы впоследствии избавимся.

def dumb():
    pass
 

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

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

Мы уже сделали шаг вперёд, так как test(dumb)(0)==1.

Попробуем вызвать test(dumb)(1). Мы получим исключение, так как интерпретатор не сможет вызвать dumb с аргументом 0. Мы можем поступить хитро и сделать вызов test(test(dumb))(1). Пойдя этой дорогой, мы может даже дойти до такого вызова test(test(test(test(test(test(test(dumb)))))))(6), который успешно считает факториал до 6.

А можно ли сделать такой вызов: test(test(...))(x), где… — бесконечное количество вызовов нашей функции test?
Можно, и в этом нам поможет Y-комбинатор.
Вот одна из его форм, в которой чётко видна такая структура вызовов:

def Y(f):
    return f(lambda x: Y(f)(x))
 

И, соответственно, факториал можно определить так:

factorial=Y(test)

В рамках определения из Википедии, можно сказать и так, что мы получили ссылку на внутреннюю лямбда-функцию (это которая lambda n: ...) и вызвали test с этой ссылкой.

Ещё одну известную рекурсивную функцию можно записать так:

fibbonacci=Y(lambda f:lambda n: 1 if n==0 or n==1 else f(n-2)+f(n-1))
 

Другая форма Y-комбинатора, в которой структура вызовов эффективно скрыта:

def Y(f):
    def g(k):
        return f(lambda a: (k(k))(a))
    return g(g)
 

Практической ценности в такой реализации факториала, конечно нет, это даже медленнее обычного рекурсивного вызова. Можно пожертвовать памятью и ускорить вычисления за счёт кэширования. Для этого нам необходимо слегка модифицировать Y-комбинатор:

def Ycache(f,data):
    def _fn(x):
        if x in data:
            return data[x]
        else:
            temp=(f(lambda x: Ycache(f,data)(x))
                 )(x)
            data[x]=temp
            return temp
    return _fn
 

И функция вычисления чисел Фиббоначчи будет выглядеть так:

fibbonacci=Ycache(test,{})
 

Вычисление 200-го числа Фиббоначчи происходит практически мгновенно, в отличии от простого рекурсивного варианта.

И напоследок, немного экзотики: быстрая сортировка (quick_sort)

qsort = lambda h: lambda lst: (lst if len(lst)<=1 else ( 
                             h([item for item in lst if item<lst[0]]) + \
                               [lst[0]]*lst.count(lst[0]) + \
                             h([item for item in lst if item>lst[0]])))
 
print( Y(qsort)([1,13,2,12,3,11,4,10,5,9,6,8,7]))

_________
Текст подготовлен в ХабраРедакторе
^[1]Есть мысль, что это как-то связано с тем, что у некоторого класса функций f(f(f(f(f(f(f(f(f(f(…f(x))))))))))) будет сходиться к значению y, такому что f(y)=y.
^[2]В Википедии в обсуждении написали, что Y-комбинатор не обязан решать алгоритмически неразрешимые задачи, а просто обеспечивать своё поведение на некотором классе функций.