Is general case of monad expressible in java 6?

Question

Is general case of monad expressible in Java 6? Note the words "general case" — it may be possible that general case of monad is not expressible, although many particular cases of monad (i.e. many specific monads) are expressible.

The problem here is (lack of) Higher-kinded generics in Java ; however, I saw that sample Haskell code was really ported to Java using the approach like https://stackoverflow.com/a/877036/1123502 (that is, public class Fix<F extends Fix<F>>).

Of course, non-type-safe implementations (like using Object and downcasts) are not interesting.

Update: there are 2 common monad definitions: join-fmap and bind-return. Although they are (mathematically) equivalent, they may be not equivalent in the sense that one definition is expressible in Java, whereas other is not (however, it seems to me, that non-equivalence is unlikely). So my question concern both definitions.

The bottom line: did anyone overcome all obstacles and wrote "general case" monad in Java 6? Or, alternatively, please point out a paper, or a thorough blog post, or thoroughly explain why it is not possible.

@trashgod Note though that in that implementation the return type of bind is Monad<M,T> - not M<T>, which wouldn't be possible in Java. Consequently if you have a List class that inherits from Monad, there is no guarantee that calling bind on such a list will produce another list, so it wouldn't be legal to write something like MonadicList<T> strings = myMonadicList.bind(...) without a cast. ... — sepp2k
... So the abstract class given in that article isn't an entirely correct implementation of the monad concept (though it's probably as close to correct as you can get in Java). — sepp2k
Also the article says "The unit function, η, comes for free in Java: it's called new.". That would be true if it weren't the fact that it's illegal in Java to write new M where M is a type parameter. So this makes it impossible to create instances of an arbitrary monadic type in a generic method (without reflection tricks like passing Class objects around). — sepp2k
@sepp2k: Your constructive critique of the article cited would be a useful answer. — trashgod

Landei Landei · Accepted Answer · 2012-11-25T17:38:33

Not without dirty casting tricks. As you already noted Java doesn't support type level polymorphism (a.k.a. "higher kinded types" in Scala land).

Here is one way: Say you want to implement a functor. You would like to write Functor<F<A>>, where F is e.g. a List or Maybe, but that doesn't work. But you can have a "base class" Base<X,Y> for higher-kinded stuff. X must be a "witness" for your real class like List. Y is the usual generic parameter. Now your functor becomes Functor<Base<F,A>>, but all classes that want to be used with this, need to implement Base<X,Y>:

class List<A> implements Base<List.Witness,A> {
   public class Witness{}
   ...
}

public interface Functor<F> {
    public <A, B> Base<F, B> map(F1<A, B> fn, Base<F, A> nestedA);
}

public class ListFunctor implements Functor<List.Witness> {
    public <A, B> Base<List.Witness, B> map(F1<A, B> fn, Base<List.Witness, A> nestedA) {
       ...
    }  
}

Of course the price to pay is that you get back a Base<List.Witness,B>, not a List<B>. This might be fine if you stay in that higher-kinded domain, and of course you can have conversion functions for convenience, but it's still not very nice.

For an implementation see my not-so-serious project highJ. Note that I'm working on a completely rewritten and slightly more convenient version closer to the example above.

For serious code, consider writing such stuff in Scala instead (or use Scalaz).

Is general case of monad expressible in java 6?

1 Answers