Java Generics Inferred Types

Question

Ok, so I am implementing the state monad in java. However, I can't seem to get the generics to work right. I have the code below, and am trying to avoid the cases indicated.

public interface Monad<M, A> 
{
    <B, R extends Monad<M, B>> R bind(Function<? super A, R> p_function);
}

public class State<S, A> implements Monad<State<S, ?>, A>
{
    private Function<S, Pair<S, A>> m_function;

    public State(Function<S, Pair<S, A>> p_function)
    {
        m_function = p_function;
    }

    public final Pair<S, A> run(S p_state)
    {
        return m_function.apply(p_state);
    }

    @Override
    public <B, R extends Monad<State<S, ?>, B>> R bind(
            final Function<? super A, R> p_function) 
    {
        // I want to avoid the cast to R here
        return (R) new State<S, B>((S state) -> {
            Pair<S, A> run = run(state);
            // And this cast, but they seem related
            State<S, B> applied = (State<S, B>) p_function.apply(run.second());
            return applied.run(run.first());
        });
    }
}

Note: I am aware that if I cange the signature of bind to
<B> Monad<M, B> bind(Function<? super A, ? extends Monad<M, B>> p_function);
The cast can be avoided. However, this causes a compile error in the following method

public static <A, B, C, M, MB extends Monad<M, B>, MC extends Monad<M, C>> 
Function<A, MC> compose(
        Function<? super A, MB> p_first, Function<? super B, MC> p_second)
{
    // have to use an anonymous class here, because using a closure causes a
    // runtime error with the beta version of JDK 8
    return new Function<A, MC>() {

        @Override
        public MC apply(A arg) {
            MB monadOfB = p_first.apply(arg);
            return monadOfB.<C> bind(p_second); // <-- type error here
        }
    };
}

Now, I also tried changing the signature of compose in a similar manner. i.e. rather than MB extends Monad<M, B> I used Monad<M, B> where MB was used and similarly for MC. This makes the compose method compile. However, then the return type could not be correctly inferred by the callers of compose i.e.

Function<String, State<Integer, String>> left = ...; 
Function<String, State<Integer, String>> right = ...; 
Function<String, State<Integer, String>> composed = Monad.compose(left, right);

Doesn't work without specifying the types on the method call, whereas before it did.

How do I make all these generics play nicely together?

Answer 1

For your example to work, you need your classes to be defined similarly to:

class State<S, B> extends Monad<State<S, ?>, B> {}
class Monad<T, U> {}

R is a subclass of Monad<State<S, ?>, B>, and sb is a subclass of Monad<State<S, ?>, B> too, but there is no reason that it also is a R.

It is like writing:

Number n = 123.5d;
Integer i = n; //does not compile: cast required
Integer j = (Integer) n; //throws an exception

---

EDIT

I'm not familiar with what you are trying to achieve, and this simplication might not achieve your aim, but it would compile (I have removed the lambdas as I don't have a jdk8 compiler installed at the moment):

public class Test1 {

    public static <A, B, C, M> Function<A, Monad<M, C>> compose(final Function<? super A, Monad<M, B>> p_first, 
                                                                final Function<? super B, Monad<M, C>> p_second) {
        // have to use an anonymous class here, because using a closure causes a runtime error
        // with the beta version of JDK 8
        return new Function<A, Monad<M, C>>() {
            @Override
            public Monad<M, C> apply(A arg) {
                Monad<M, B> monadOfB = p_first.apply(arg);
                return monadOfB.bind(p_second); // <-- type error here
            }
        };
    }
}

interface Monad<M, A> {

    <B> Monad<M, B> bind(Function<? super A, Monad<M, B>> p_function);
}

class State<S, A> implements Monad<State<S, ?>, A> {

    private Function<S, Pair<S, A>> m_function;

    public State(Function<S, Pair<S, A>> p_function) {
        m_function = p_function;
    }

    public final Pair<S, A> run(S p_state) {
        return m_function.apply(p_state);
    }

    @Override
    public <B> Monad<State<S, ?>, B> bind(final Function<? super A, Monad<State<S, ?>, B>> p_function) {
        // I want to avoid the cast to R here
        return new State<S, B>(new Function<S, Pair<S, B>>() {
            public Pair<S, B> apply(S state) {
                Pair<S, A> run = run(state);
                // And this cast, but they seem related
                State<S, B> applied = (State<S, B>) p_function.apply(run.second());
                return applied.run(run.first());
            }
        });
    }
}

Answer 2

(I'm +1'ing jacobm's answer, I just wanted to elaborate a bit on the underlying problem.)

The problem is that in Java, there is no particular relationship between GenericClass<S> and GenericClass<T>: I mean, both are subtypes of GenericType<?>, but there's no way that GenericInterface<T> can refer to the type you'd get by taking getClass() and substituting T for S.

In Haskell, the definition of the Monad typeclass looks like this:

class Monad m where
    (>>=)  :: m a -> (a -> m b) -> m b
    return :: a -> m a

Note that it defines m by using both m a and m b, meaning "the same parameterized type m, with (potentially) different type-arguments a and b". In Java you can't create a supertype of m (that is, an interface for m) that expresses this sort of thing, because while the supertype can refer to itself with arbitrary type-parameters (because it can refer to itself by name, just like how it could use any other generic type), and can refer to an arbitrary subtype with any single type-argument (namely its own), it has no way to refer to an arbitrary subtype with an arbitrary type-parameter. It doesn't sit "outside" the type system in the way that a Haskell typeclass definition does.

This means that there's no real way to define a generic Monad interface whose implementations are generic monadic types.