A bit of fun with the Y combinator

[Millies, Sebastian]

Hello there,

many people seem to enjoy coding the Y combinator in Java. There are examples
in Java 7 (e. g. [1] and [2]) which I decided to try and port to Java 8. The popular
application is to compute the factorial function.

I’ll show my first solution in a minute. The code really does work: There are no
variables, no names assigned to any function, only lambda expressions and parameters.
And yet, we can recursively compute the factorial of arbitrary integers.

Here’s the puzzle for you: I have not been able to “generify” the thing, i. e.
replace all references to “int” in the Y combinator with a suitable type parameter.
I would always get type incompatibilities. And remember: No named methods or
variables are allowed. (e. g. the Java 7 code in [2] violates that condition.)

Note that there are a few casts even in the working solution. Why are they necessary?
It would be nice to get rid of them.

Best Regards,
Sebastian

[1] http://www.righto.com/2009/03/y-combinator-in-arc-and-java.html
[2] https://gist.github.com/jonbodner/2571928

Code follows
------- 8< ----------

import java.util.function.Function;
import java.util.function.IntUnaryOperator;

public class Combinators {

    // First a few abbreviations

    /** Function on int returning int. */
    interface IntFunc extends IntUnaryOperator {
    }

     /**
     * Higher-order function returning an int function.
     * <br/>F: F -> (int -> int)
     * <br/>This is the type of the Y combinator subexpressions.
     */
    interface FuncToIntFunc extends Function<FuncToIntFunc, IntFunc> {
    }

    /**
     * Function from IntFuntToIntFunc to Func.
     * <br/>((int -> int) -> (int -> int)) -> (int -> int)
     */
    interface YCombinator extends Function<Function<IntFunc, IntFunc>, IntFunc> {
    }

    // Then the meat

    /**
     * Computes the factorial with the applicative-order Y combinator.
     * <br/>Y = λr.(λf.(f f)) λf.(r λx.((f f) x))
     */
    public static int factorial(int n) {
        return  ((YCombinator) r ->
                        ((FuncToIntFunc) (f -> f.apply(f))).apply(
                                f -> r.apply(x -> f.apply(f).applyAsInt(x)))
                        )
                        .apply(
                                // Recursive function generator
                                f -> x -> (x == 0) ? 1 : x * f.applyAsInt(x - 1)
                        )
                        .applyAsInt(
                                // Argument
                                n);
    }

    public static void main(String args[]) {
        int n = Integer.parseInt(args[0]);
        System.out.println(n + "! = " + factorial(n));
    }
}

Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com