How to implement Church Numerals using Java 1.8

Question

I'm trying to implement Church Numerals in Java 1.8. My first attempt was:

import java.util.function.UnaryOperator;

@FunctionalInterface
public interface ChurchNumeral {
  public static ChurchNumeral valueOf(int n) {
    if (n < 0) {
      throw new IllegalArgumentException("Argument n must be non-negative.");
    }
    if (n == 0) {
      return (f, arg) -> arg;
    }
    return (f, arg) -> f(valueOf(n-1).apply(f, arg));
  }

  <T> T apply(UnaryOperator<T> f, T arg);
}

This fails because the functional method has a type parameter. (Specifically, the lines with lambda expressions give the error: "Illegal lambda expression: Method apply of type ChurchNumeral is generic".)

Based on answers to related questions on the use of generics with functional interfaces, I tried parameterizing the class:

import java.util.function.UnaryOperator;

@FunctionalInterface
public interface ChurchNumeral<T> {                // This line changed.
  public static ChurchNumeral<?> valueOf(int n) {  // This line changed.
    if (n < 0) {
      throw new IllegalArgumentException("Argument n must be non-negative.");
    }
    if (n == 0) {
      return (f, arg) -> arg;
    }
    return (f, arg) -> f(valueOf(n-1).apply(f, arg));
  }

  T apply(UnaryOperator<T> f, T arg);              // This line changed.
}

The first lambda expression now compiles, but the second one fails with this error:

The method apply(UnaryOperator, capture#1-of ?) in the type ChurchNumeral is not applicable for the arguments (UnaryOperator, Object)

Additionally, I don't want to have different versions of ChurchNumeral.ZERO for every possible function/argument type.

Any suggestions?

Answer 1

Is there a way to do it so I don't need to create a ChurchNumeral for every possible type? I'd like to be able to apply ZERO (for example) to any UnaryOperator and argument of type T

I am assuming you mean you want to do something like this:

ChurchNumeral five = ChurchNumeral.valueOf(5);
five.apply(s -> s + s, "s");
five.apply(Math::sqrt, Double.MAX_VALUE);

which means that the method signature in your first example:

<T> T apply(UnaryOperator<T> f, T arg);

is the one that is needed.

However, you can't use a lambda expression for a functional interface, if the method in the functional interface has type parameters.

A workaround is to create a subinterface which is compatible with lambdas and delegate the calls to apply to its method, as shown below.

public static void main(String[]a){
    ChurchNumeral five = ChurchNumeral.valueOf(5);
    System.out.println(five.apply(s -> s + s, "s"));
    System.out.println(five.apply(Math::sqrt, Double.MAX_VALUE));
}
@FunctionalInterface
private interface ChurchNumeralT<T> extends ChurchNumeral {
    @SuppressWarnings({ "rawtypes", "unchecked" })
    @Override
    default<U> U apply(UnaryOperator<U> f, U arg){
        return (U)((ChurchNumeralT)this).tapply(f, arg);
    }
    T tapply(UnaryOperator<T> f, T arg);
}
public interface ChurchNumeral {

    <T> T apply(UnaryOperator<T> f, T arg);

    static ChurchNumeral valueOf(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Argument n must be non-negative.");
        }
        if (n == 0) {
            return (ChurchNumeralT<?>)(f, arg) -> arg;
        }
        return (ChurchNumeralT<?>)(f, arg) -> f.apply(valueOf(n - 1).apply(f, arg));
    }
}