Итак, все мы помним, что такое Y-комбинатор (кто не помнит, это комбинатор неподвижной точки или Y g = g Y g). Из математической его записи следует некоторая проблема: он генерирует последовательность g g g… g Y g, в которой каждый следующий шаг может использовать лишь результат предыдущего вычисления да захваченный из комбинатора кусок контекста — что приводит к необходимости для каждой функции писать свой собственный комбинатор.
Идея заключается в том, чтобы написать Y-комбинатор, который не будет зависеть от самоприменяемой функции.
Теоретически, он должен получить на вход следующие данные: функцию для рекурсии, функцию для модификации списка аргументов и начальное состояние этого списка.
Причем, рекурируемая функция в свою очередь, должна принимать предыдущее значение и список аргументов, измененных для этого шага.
Для начала, попробую составить реализацию на Хаскелле:
Ну, теперь можно попытаться вычислить факториал:
Теперь, рассчитаем факториал четырех.
Полностью проведя комбинаторные подстановки, получим:
Теперь сворачиваем:
Вроде работает :)
— Обновлено третьего июня две тысячи девятого года нашей эры пятнадцатого коллайдера:
Недавно я пришел к мысли, что разработанный интерфейс вводит определенные ограничения: в случае когда данные для следующей итерации определяются результатом текущей, последнюю придется вычислять два раза, в инкременторе и в функторе.
Поэтому была разработана таковая вот версия Ы-комбинатора:
Лисп:
Что позволяет в функторе выбирать данные для следущей итерации, а значит реккурсия может быть не только линейной, но и древовидной.
Идея заключается в том, чтобы написать Y-комбинатор, который не будет зависеть от самоприменяемой функции.
Теоретически, он должен получить на вход следующие данные: функцию для рекурсии, функцию для модификации списка аргументов и начальное состояние этого списка.
Причем, рекурируемая функция в свою очередь, должна принимать предыдущее значение и список аргументов, измененных для этого шага.
Для начала, попробую составить реализацию на Хаскелле:
Y functor argtracker args = functor (Y functor argtracker (agtracker args)) args;
Ну, теперь можно попытаться вычислить факториал:
fac N = Y (\prev -> \i -> if i = 0 then 1 else prev * i) (\i -> i - 1) N;
Теперь, рассчитаем факториал четырех.
Полностью проведя комбинаторные подстановки, получим:
fac 4 = (\prev -> 4 -> if 4 = 0 then 1 else prev * i) ((\prev -> 3 -> if 3 = 0 then 1 else prev * i) ((\prev -> 2 -> if 2 = 0 then 1 else prev * i) ((\prev -> 1 -> if 1 = 0 then 1 else prev * i) ((\prev -> 0 -> if 0 = 0 then 1 else prev * i)))))
Теперь сворачиваем:
fac 4 = (\prev -> 4 -> if 4 = 0 then 1 else prev * 4) ((\prev -> 3 -> if 3 = 0 then 1 else prev * 3) ((\prev -> 2 -> if 2 = 0 then 1 else prev * 2) ((\prev -> 1 -> if 1 = 0 then 1 else prev * 1) (1))))) fac 4 = (\prev -> 4 -> if 4 = 0 then 1 else prev * 4) ((\prev -> 3 -> if 3 = 0 then 1 else prev * 3) ((\prev -> 2 -> if 2 = 0 then 1 else prev * 2) (1 * 1)))) fac 4 = (\prev -> 4 -> if 4 = 0 then 1 else prev * 4) ((\prev -> 3 -> if 3 = 0 then 1 else prev * 3) (2 * (1 * 1))) fac 4 = (\prev -> 4 -> if 4 = 0 then 1 else prev * i) 3 * (2 * (1 * 1)) fac 4 = 4 * 3 * 2 * 1 * 1
Вроде работает :)
— Обновлено третьего июня две тысячи девятого года нашей эры пятнадцатого коллайдера:
Недавно я пришел к мысли, что разработанный интерфейс вводит определенные ограничения: в случае когда данные для следующей итерации определяются результатом текущей, последнюю придется вычислять два раза, в инкременторе и в функторе.
Поэтому была разработана таковая вот версия Ы-комбинатора:
Y functor data = functor (\newdata -> Y functor newdata) data;
Лисп:
(defun Y (functor data) (funcall functor (lambda (new-data) (Y functor new-data))))
Что позволяет в функторе выбирать данные для следущей итерации, а значит реккурсия может быть не только линейной, но и древовидной.