Y-комбинатор, упрощение интерфейса

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

Идея заключается в том, чтобы написать 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))))

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