Y combinator, simplifying the interface

So, we all remember what a Y-combinator is (who does not remember, this is a fixed-point combinator or Y g = g Y g). A mathematical problem follows from his mathematical notation: it generates a sequence ggg ... g Y g in which each next step can use only the result of the previous calculation and a piece of context captured from the combinator — which makes it necessary for each function to write its own combinator.

The idea is to write a Y-combinator that will not depend on a self-applying function.



Theoretically, it should receive the following data as an input: a function for recursion, a function for modifying the argument list, and the initial state of this list.

Moreover, the recursed function, in turn, must take the previous value and the list of arguments changed for this step.

To get started, I’ll try to make an implementation on Haskell:

Y functor argtracker args = functor (Y functor argtracker (agtracker args)) args;

Well, now you can try to calculate the factorial:

fac N = 
    Y 
        (\ prev -> \ i -> if i = 0 then 1 else prev * i)
        (\ i -> i - 1)
        N;

Now, let's calculate the factorial of four.

Completing combinatorial substitutions, we obtain:

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)))))

Now collapse:

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) 
                (eleven))))
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

It seems to work :)

- Updated on the third of June two thousand and ninth year of our era of the fifteenth collider:

Recently I came to the conclusion that the developed interface introduces certain restrictions: in the case when the data for the next iteration is determined by the result of the current one, the latter will have to be calculated twice, in the increment and in the functor.

Therefore, such a version of the Y-combinator was developed:

Y functor data =
    functor
        (\ newdata -> Y functor newdata)
        data;

Lisp:

(defun Y (functor data)
    (funcall functor 
        (lambda (new-data) 
            (Y functor new-data))))

This allows the functor to select data for the next iteration, which means that recursion can be not only linear, but also tree-like.