Y-combinator, simplified 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). Some problem follows from his mathematical writing: he generates the sequence ggg ... g Y g, in which each next step can only use the result of the previous calculation and the 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-applicable function.


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

Moreover, the function being recovered, in turn, must take the previous value and the list of arguments modified for this step.

To begin with, I will try to make 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, calculate factorial four.

Fully combining combinatorial substitutions, we get:

 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 we turn off:

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

 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 nine ninth year of the 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 incrementor 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 us to select data for the next iteration in the functor, which means that the recursion can be not only linear, but also tree-like.