Поводом для написания этой статьи стало желание разобраться с тем, как работает Y-комбинатор.
Чтобы мозги не ржавели и работали как часы, я стараюсь пробовать новые и необычные вещи.
Интереса ради, я скомпилировал Lua 5.x под DOS, с этим никаких проблем не было, но при проверке Lua на её стандартных тестах, я обнаружил код вычисления факториала, работу которого я не понял.
Но ясно осознал, что это нечто относится к функциональному программированию.
В итоге нашёл статью в Википедии, статью про практическое использование в Ruby и статью про Y-комбинатор на Python'е, при разборе которой я, наконец-то хоть что-то понял.
Y-комбинатор позволяет превратить обычную (в том числе и анонимную) функцию в рекурсивную. Основная его ценность — теоретическая, для обоснования теорий формальных вычислений, но некоторые находят для него практическое применение (такое ощущение появилось после чтения комментариев к вышеупомянутым статьям).
Из Википедии следует, что Y-комбинатор — это частный случай функций высшего порядка, которые принимают на вход функцию f и возвращают функцию g, такую, что f(g)=g. Может это и так, но пользы для понимания это определение мне не дало[1][2].
Попробуем разобраться на классическом примере факториала как это всё работает. Использоваться будет Python, потому что с ним я больше знаком.
В процессе разбора будет использоваться вспомогательная функцию dumb, от которой мы впоследствии избавимся.
Попробуем преобразовать следующую лямбда-функцию в рекурсивную, которая вычисляет факториал.
Мы уже сделали шаг вперёд, так как 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-комбинатор.
Вот одна из его форм, в которой чётко видна такая структура вызовов:
И, соответственно, факториал можно определить так:
В рамках определения из Википедии, можно сказать и так, что мы получили ссылку на внутреннюю лямбда-функцию (это которая lambda n: ...) и вызвали test с этой ссылкой.
Ещё одну известную рекурсивную функцию можно записать так:
Другая форма Y-комбинатора, в которой структура вызовов эффективно скрыта:
Практической ценности в такой реализации факториала, конечно нет, это даже медленнее обычного рекурсивного вызова. Можно пожертвовать памятью и ускорить вычисления за счёт кэширования. Для этого нам необходимо слегка модифицировать Y-комбинатор:
И функция вычисления чисел Фиббоначчи будет выглядеть так:
Вычисление 200-го числа Фиббоначчи происходит практически мгновенно, в отличии от простого рекурсивного варианта.
И напоследок, немного экзотики: быстрая сортировка (quick_sort)
_________
Текст подготовлен в ХабраРедакторе
[1]Есть мысль, что это как-то связано с тем, что у некоторого класса функций f(f(f(f(f(f(f(f(f(f(…f(x))))))))))) будет сходиться к значению y, такому что f(y)=y.
[2]В Википедии в обсуждении написали, что 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-комбинатор не обязан решать алгоритмически неразрешимые задачи, а просто обеспечивать своё поведение на некотором классе функций.
