recursion, self-referencing lambda, y-combinator

[zhong...@gmail.com]

Say we want to define a function recursively, e.g. factorial

    fac(n) = n*fac(n-1)  // n>0
    fac(0) = 1

This is a little hard to do with Java's lambda expression, since a lambda cannot reference itself. (`this` won't work in a lambda body).

The simple workaround is to use an anonymous class to define the function, and that's that. But let's say we'd really love to use lambda.

Naming the lambda (by pegging it to a variable) doesn't help much either

    Function<Integer,Integer> fac = n -> n==0? 1 : n*fac.apply(n-1);    // compile error - cannot access `fac` in lambda body

If `fac` is an instance variable, we can work around it by accessing `this.fac`

If `fac` is a static variable, we can work around it by accessing `ClassName.fac`

If `fac` is a local variable, I don't see how. We must use a mutable container instead, e.g.

        Function<Integer,Integer> fac[] = new Function[1];

        fac[0] = n -> n==0? 1 : n*fac[0].apply(n-1);

----

Now, the fun way. We can sort-of feed the lambda to itself as an extra parameter

        Function<Integer, Integer> fac = convert( (thiz, n) -> n==0? 1 : n*thiz.apply(n-1) );

`thiz` has the type of `Function<Integer,Integer>`, and `convert()` makes sure that `thiz` will be the same object returned from `convert()`, i.e. thiz==fac.

To be prettier, we can design it as `thiz -> n ->` instead of `(thiz,n)->`

        Function<Integer, Integer> fac = fix( thiz -> n -> n==0? 1 : n*thiz.apply(n-1) );

And `fix()` looks like

    static <T,R>
    Function<T,R> fix( Function< Function<T,R>, Function<T,R> > ff )
    {
        return new Function<T, R>()
        {
            public R apply(T t)
            {
                return ff.apply(this).apply(t);  // feed `this` to `ff` as `thiz`
            }
        };
    }

which has something to do with fix-point and y-combinator. It gives me headache so I'm not gonna dive in it. As far as I'm concerned, `fix()` is a practical utility that helps a lambda reference itself.


See also https://www.reddit.com/r/java/comments/2cqvvy where a guy implements `fix()` as

    static <T,R>
    Function<T,R> fix(Function< Function<T,R>, Function<T,R> > f)
    {
        return x -> f.apply(fix(f)).apply(x);
    }

which is more mind-fucking to me... it works correctly but it generates more objects, because `fix(f)` is called many times.


Zhong Yu
bayou.io