How to write a generic iteration of a function using Java 8?

Question

Please consider the following two functions:

public static <X, Y, U, V extends X> Function<U, Y> composite(
    Function<X, Y> first, Function<U, V> second)
{
    Objects.requireNonNull(first);
    Objects.requireNonNull(second);
    return (U arg) -> first.apply(second.apply(arg));
}

public static <X, Y extends X> Function<X, ?> iterate(Function<X, Y> function, int n)
{
    if (n < 0)
        return null;
    if (n == 0)
        return (X arg) -> arg;  
    Objects.requireNonNull(function);

    Function<X, Y> iteration = function;
    for (; n > 1; --n)
        iteration = composite(function, iteration);
    return iteration;
}

While composite(first, second) computes the composition of first and second, iterate(function, n) computes the nth iterate of function.

While the restriction Y extends X suffices for any n > 0, we've got some problem with n == 0. Mathematically, iterate should yield the identity function. However, therefore we would need X extends Y, i.e. X == Y, as well.

Please consider the following example

Function<Double, Double> nthSquareRoot = iterate(Math::sqrt, n);

This yields the error message:

Type mismatch: cannot convert from Function<Double,capture#2-of ?> to Function<Double,Double>

What's the best option here? If n == 1, we could check if X is acceptable as Y. I would like to hear other options and some ideas how this check can be performed (as far as I know, there is no simple solution to check two generic parameters for equality).

Answer 1

Try:

public static<X> UnaryOperator<X> iterate(UnaryOperator<X> f, int n) { ... }

If Y <: X, then a function from X to Y is also a function from X to X, and you should be able to do what you want.