Why can the Monad interface not be declared in Java?

user_3888450 0
Viewed 3325

Before you start reading: This question is not about understanding monads, but it is about identifying the limitations of the Java type system which prevents the declaration of a Monad interface.

In my effort to understand monads I read this SO-answer by Eric Lippert on a question which asks about a simple explanation of monads. There, he also lists the operations which can be executed on a monad:

  1. That there is a way to take a value of an unamplified type and turn it into a value of the amplified type.
  2. That there is a way to transform operations on the unamplified type into operations on the amplified type that obeys the rules of functional composition mentioned before
  3. That there is usually a way to get the unamplified type back out of the amplified type. (This last point isn't strictly necessary for a monad but it is frequently the case that such an operation exists.)

After reading more about monads, I identified the first operation as the return function and the second operation as the bind function. I was not able to find a commonly used name for the third operation, so I will just call it the unbox function.

To better understand monads, I went ahead and tried to declare a generic Monad interface in Java. For this, I first looked at the signatures of the three functions above. For the Monad M, it looks like this:

return :: T1 -> M<T1>
bind   :: M<T1> -> (T1 -> M<T2>) -> M<T2>
unbox  :: M<T1> -> T1

The return function is not executed on an instance of M, so it does not belong into the Monad interface. Instead, it will be implemented as a constructor or factory method.

Also for now, I omit the unbox function from the interface declaration, since it is not required. There will be different implementations of this function for the different implementations of the interface.

Thus, the Monad interface only contains the bind function.

Let's try to declare the interface:

public interface Monad {
    Monad bind();
}

There are two flaws:

  • The bind function should return the concrete implementation, however it does only return the interface type. This is a problem, since we have the unbox operations declared on the concrete subtypes. I will refer to this as problem 1.
  • The bind function should retrieve a function as a parameter. We will address this later.

Using the concrete type in the interface declaration

This addresses problem 1: If my understanding of monads is correct, then the bind function always returns a new monad of the same concrete type as the monad where it was called on. So, if I have an implementation of the Monad interface called M, then M.bind will return another M but not a Monad. I can implement this using generics:

public interface Monad<M extends Monad<M>> {
    M bind();
}

public class MonadImpl<M extends MonadImpl<M>> implements Monad<M> {
    @Override
    public M bind() { /* do stuff and return an instance of M */ }
}

At first, this seems to work, however there are at least two flaws with this:

  • This breaks down as soon as an implementing class does not provide itself but another implementation of the Monad interface as the type parameter M, because then the bind method will return the wrong type. For example the 

    public class FaultyMonad<M extends MonadImpl<M>> implements Monad<M> { ... }

    will return an instance of MonadImpl where it should return an instance of FaultyMonad. However, we can specify this restriction in the documentation and consider such an implementation as a programmer error.

  • The second flaw is more difficult to resolve. I will call it problem 2: When I try to instantiate the class MonadImpl I need to provide the type of M. Lets try this:

    new MonadImpl<MonadImpl<MonadImpl<MonadImpl<MonadImpl< ... >>>>>()

    To get a valid type declaration, this has to go on infinitely. Here is another attempt:

    public static <M extends MonadImpl<M>> MonadImpl<M> create() {
    return new MonadImpl<M>();
}

    While this seems to work, we just defered the problem to the called. Here is the only usage of that function that works for me:

    public void createAndUseMonad() {
    MonadImpl<?> monad = create();
    // use monad
}

    which essentially boils down to 

    MonadImpl<?> monad = new MonadImpl<>();

    but this is clearly not what we want.

Using a type in its own declaration with shifted type parameters

Now, let's add the function parameter to the bind function: As described above, the signature of the bind function looks like this: T1 -> M<T2>. In Java, this is the type Function<T1, M<T2>>. Here is the first attempt to declare the interface with the parameter:

public interface Monad<T1, M extends Monad<?, ?>> {
    M bind(Function<T1, M> function);
}

We have to add the type T1 as generic type parameter to the interface declaration, so we can use it in the function signature. The first ? is the T1 of the returned monad of type M. To replace it with T2, we have to add T2 itself as a generic type parameter:

public interface Monad<T1, M extends Monad<T2, ?, ?>,
                       T2> {
    M bind(Function<T1, M> function);
}

Now, we get another problem. We added a third type parameter to the Monad interface, so we had to add a new ? to the usage of it. We will ignore the new ? for now to investigate the now first ?. It is the M of the returned monad of type M. Let's try to remove this ? by renaming M to M1 and by introducing another M2:

public interface Monad<T1, M1 extends Monad<T2, M2, ?, ?>,
                       T2, M2 extends Monad< ?,  ?, ?, ?>> {
    M1 bind(Function<T1, M1> function);
}

Introducing another T3 results in:

public interface Monad<T1, M1 extends Monad<T2, M2, T3, ?, ?>,
                       T2, M2 extends Monad<T3,  ?,  ?, ?, ?>,
                       T3> {
    M1 bind(Function<T1, M1> function);
}

and introducing another M3 results in:

public interface Monad<T1, M1 extends Monad<T2, M2, T3, M3, ?, ?>,
                       T2, M2 extends Monad<T3, M3,  ?,  ?, ?, ?>,
                       T3, M3 extends Monad< ?,  ?,  ?,  ?, ?, ?>> {
    M1 bind(Function<T1, M1> function);
}

We see that this will go on forever if we try to resolve all ?. This is problem 3.

Summing it all up

We identified three problems:

  1. Using the concrete type in the declaration of the abstract type.
  2. Instantiating a type which receives itself as generic type parameter.
  3. Declaring a type which uses itself in its declaration with shifted type parameters.

The question is: What is the feature that is missing in the Java type system? Since there are languages which work with monads, these languages have to somehow declare the Monad type. How do these other languages declare the Monad type? I was not able to find information about this. I only find information about the declaration of concrete monads, like the Maybe monad.

Did I miss anything? Can I properly solve one of these problems with the Java type system? If I cannot solve problem 2 with the Java type system, is there a reason why Java does not warn me about the not instantiable type declaration?

As already stated, this question is not about understanding monads. If my understanding of monads is wrong, you might give a hint about it, but don't attempt to give an explanation. If my understanding of monads is wrong the described problems remain.

This question is also not about whether it is possible to declare the Monad interface in Java. This question already received an answer by Eric Lippert in his SO-answer linked above: It is not. This question is about what exactly is the limitation that prevents me from doing this. Eric Lippert refers to this as higher types, but I can't get my head around them.

Most OOP languages do not have a rich enough type system to represent the monad pattern itself directly; you need a type system that supports types that are higher types than generic types. So I wouldn't try to do that. Rather, I would implement generic types that represent each monad, and implement methods that represent the three operations you need: turning a value into an amplified value, turning an amplified value into a value, and transforming a function on unamplified values into a function on amplified values.

higher-order-types type-systems monads generics java
4 Answers

Good question indeed! :-)

As @EricLippert pointed out, the type of polymorphism that is known as "type classes" in Haskell is beyond the grasp of Java's type system. However, at least since the introduction of the Frege programming language it has been shown that a Haskell-like type system can indeed be implemented on top of the JVM.

If you want to use higher-kinded types in the Java language itself you have to resort to libraries like highJ or Cyclops. Both libraries do provide a monad type class in the Haskell sense (see here and here, respectively, for the sources of the monad type class). In both cases, be prepared for some major syntactic inconveniences; this code will not look pretty at all and carries a lot of overhead to shoehorn this functionality into Java's type system. Both libraries use a "type witness" to capture the core type separately from the data type, as John McClean explains in his excellent introduction. However, in neither implementation you will find anything as simple and straightforward as Maybe extends Monad or List extends Monad.

The secondary problem of specifying constructors or static methods with Java interfaces can be easily overcome by introducing a factory (or "companion") interface that declares the static method as a non-static one. Personally, I always try to avoid anything static and use injected singletons instead.

Long story short, yes, it is possible to represent HKTs in Java but at this point it is very inconvenient and not very user friendly.

user_19328900

Yes, we cannot override static method in class, and we cannot write constructor in interface.

  • use abstract class to simulate Monad type class in Haskell
import java.util.function.Function;

public abstract class Monad<T> {
    public static <T> Monad<T> Unit(T a){
        throw new UnsupportedOperationException("Call Unit in abstract class: Monad");
    }
    public <R> Monad<R> OUnit(R a){
        throw new UnsupportedOperationException("Call OUnit in abstract class: Monad");
    }
    public <B> Monad<B> bind(Function<T, Monad<B>> func){
        throw new UnsupportedOperationException("Call bind in abstract class: Monad");
    }
    public <B> Monad<B> combine(Monad<B> b){
        return this.bind(unused -> b);
    }
}
public class Maybe<T> extends Monad<T> {
    public boolean has;
    public T val;
    public Maybe(T value) {
        this.has = true;
        this.val = value;
    }
    public Maybe(){
        has = false;
    }
    public static <T> Maybe<T> Unit(T a) {
        return new Maybe<T>(a);
    }
    public static <T> Maybe<T> Unit() {
        return new Maybe<T>();
    }
    @Override
    public <R> Maybe<R> OUnit(R a) {
        return new Maybe<R>(a);
    }
    public <T> Maybe<T> OUnit() {
        return new Maybe<T>();
    }
    @Override
    public <B> Monad<B> bind(Function<T, Monad<B>> func){
        if (this.has){
            return func.apply(this.val);
        }
        return new Maybe<B>();
    }
    @Override
    public String toString(){
        if (this.has){
            return "Maybe " + val.toString();
        }
        return "Nothing";
    }
}
public class Main {
/*
example :: (Monad m, Show (m n), Num n) => m n -> m n -> IO ()
example a b = do
  print $ a >> b
  print $ b >> a
  print $ a >>= (\x -> return $ x+x)
  print $ b >>= (\x -> return $ x+x)

main = do
  example (Just 10) (Just 5)
  example (Right 10) (Left 5)
*/
    public static void example(Monad<Integer> a, Monad<Integer> b){
        System.out.println(a.bind(x -> b));
        System.out.println(b.bind(x -> b));

        System.out.println(a.bind(x -> a.OUnit(x*2)));
        System.out.println(b.bind(x -> b.OUnit(x*2)));

        System.out.println(a.combine(a));
        System.out.println(a.combine(b));
        System.out.println(b.combine(a));
        System.out.println(b.combine(b));
    }
    // Monad can also used in any Objects
    public static void example2(Monad<Object> a, Monad<Object> b){
        System.out.println(a.bind(x -> b));
        System.out.println(b.bind(x -> b));

        System.out.println(a.combine(a));
        System.out.println(a.combine(b));
        System.out.println(b.combine(a));
        System.out.println(b.combine(b));
    }
    public static void main(String[] args){
        System.out.println("Example 1:");
        example(Maybe.<Integer>Unit(10), Maybe.<Integer>Unit());
        System.out.println("\n\nExample 2:");
        example(Maybe.<Integer>Unit(1), Maybe.<Integer>Unit(3));
        System.out.println("\n\nExample 3:");
        example2(Maybe.<Object>Unit(10), Maybe.<Object>Unit());
    }
}
  • use interface to simulate Monad type class in Haskell
import java.util.function.Function;

public interface Monad<T> {
    public static <T> Monad<T> Unit(T a){
        throw new UnsupportedOperationException("call Unit in Monad interface");
    }
    public <R> Monad<R> OUnit(R a);
    public <B> Monad<B> bind(Function<T, Monad<B>> func);
    default public <B> Monad<B> combine(Monad<B> b){
        return bind(x-> b);
    };
}
// in class Maybe, replace extends with implements
// in class Main, unchanged

and the output is the same

user_158860080
Related