Why can the Monad interface not be declared in Java?
If you look at what the AspectJ project is doing, it is similar to applying monads to Java. The way they do it is to post-process the byte code of the classes to add the additional functionality-- and the reason they have to do that is because there is no way within the language without the AspectJ extensions to do what they need to do; the language is not expressive enough.
A concrete example: say you start with class A. You have a monad M such that M(A) is a class that works just like A, but all method entrances and exits get traced to log4j. AspectJ can do this, but there is no facility within the Java language itself that would let you.
This paper describes how Aspect-Oriented Programming as in AspectJ might be formalized as monads
In particular, there is no way within the Java language to specify a type programmatically (short of byte-code manipulation a la AspectJ). All types are pre-defined when the program starts.
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.
What is the feature that is missing in the Java type system? How do these other languages declare the Monad type?
Good question!
Eric Lippert refers to this as higher types, but I can't get my head around them.
You are not alone. But they are actually not as crazy as they sound.
Let's answer both of your questions by looking at how Haskell declares the monad "type" -- you'll see why the quotes in a minute. I have simplified it somewhat; the standard monad pattern also has a couple other operations in Haskell:
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
Boy, that looks both incredibly simple and completely opaque at the same time, doesn't it?
Here, let me simplify that a bit more. Haskell lets you declare your own infix operator for bind, but we'll just call it bind:
class Monad m where
bind :: m a -> (a -> m b) -> m b
return :: a -> m a
All right, now at least we can see that there are the two monad operations in there. What does the rest of this mean?
The first thing to get your head around, as you note, is "higher kinded types". (As Brian points out, I somewhat simplified this jargon in my original answer. Also quite amusing that your question attracted the attention of Brian!)
In Java, a "class" is a kind of "type", and a class may be generic. So in Java we've got int and IFrob and List<IBar> and they're all types.
From this point on throw away any intuition you have about Giraffe being a class that is a subclass of Animal, and so on; we won't need that. Think about a world with no inheritance; it will not come into this discussion again.
What are classes in Java? Well, the easiest way to think of a class is that it is a name for a set of values that have something in common, such that any one of those values can be used when an instance of the class is required. You have a class Point, lets say, and if you have a variable of type Point, you can assign any instance of Point to it. The Point class is in some sense just a way to describe the set of all Point instances. Classes are a thing that is higher than instances.
In Haskell there are also generic and non-generic types. A class in Haskell is not a kind of type. In Java, a class describes a set of values; any time you need an instance of the class, you can use a value of that type. In Haskell a class describes a set of types. That is the key feature that the Java type system is missing. In Haskell a class is higher than a type, which is higher than an instance. Java only has two levels of hierarchy; Haskell has three. In Haskell you can express the idea "any time I need a type that has certain operations, I can use a member of this class".
(ASIDE: I want to point out here that I am making a bit of an oversimplification . Consider in Java for example List<int> and List<String>. These are two "types", but Java considers them to be one "class", so in a sense Java also has classes which are "higher" than types. But then again, you could say the same in Haskell, that list x and list y are types, and that list is a thing that is higher than a type; it's a thing that can produce a type. So it would in fact be more accurate to say that Java has three levels, and Haskell has four. The point remains though: Haskell has a concept of describing the operations available on a type that is simply more powerful than Java has. We'll look at this in more detail below.)
So how is this different than interfaces? This sounds like interfaces in Java -- you need a type that has certain operations, you define an interface that describes those operations. We'll see what is missing from Java interfaces.
Now we can start making sense of this Haskell:
class Monad m where
So, what is Monad? It's a class. What is a class? It's a set of types that have something in common, such that whenever you need a type that has certain operations, you can use a Monad type.
Suppose we have a type that is a member of this class; call it m. What are the operations that must be on this type in order for that type to be a member of the class Monad?
bind :: m a -> (a -> m b) -> m b
return :: a -> m a
The name of the operation comes to the left of the ::, and the signature comes to the right. So to be a Monad, a type m must have two operations: bind and return. What are the signatures of those operations? Let's look at return first.
a -> m a
m a is Haskell for what in Java would be M<A>. That is, this means m is a generic type, a is a type, m a is m parametrized with a.
x -> y in Haskell is the syntax for "a function which takes type x and returns type y". It's Function<X, Y>.
Put it together, and we have return is a function that takes an argument of type a and returns a value of type m a. Or in Java
static <A> M<A> Return(A a);
bind is a little bit harder. I think the OP well understands this signature, but for readers who are unfamiliar with the terse Haskell syntax, let me expand on this a bit.
In Haskell, functions only take one argument. If you want a function of two arguments, you make a function that takes one argument and returns another function of one argument. So if you have
a -> b -> c
Then what have you got? A function that takes an a and returns a b -> c. So suppose you wanted to make a function that took two numbers and returned their sum. You would make a function that takes the first number, and returns a function that takes a second number and adds it to the first number.
In Java you'd say
static <A, B, C> Function<B, C> F(A a)
So if you wanted a C and you had and A and a B, you could say
F(a)(b)
Make sense?
All right, so
bind :: m a -> (a -> m b) -> m b
is effectively a function that takes two things: an m a, and a a -> m b and it returns an m b. Or, in Java, it is directly:
static <A, B> Function<Function<A, M<B>>, M<B>> Bind(M<A>)
Or, more idiomatically in Java:
static <A, B> M<B> Bind(M<A>, Function<A, M<B>>)
So now you see why Java cannot represent the monad type directly. It does not have the ability to say "I have a class of types that have this pattern in common".
Now, you can make all the monadic types you want in Java. The thing you can't do is make an interface that represents the idea "this type is a monad type". What you would need to do is something like:
typeinterface Monad<M>
{
static <A> M<A> Return(A a);
static <A, B> M<B> Bind(M<A> m, Function<A, M<B>> f);
}
See how the type interface talks about the generic type itself? A monadic type is any type M that is generic with one type parameter and has these two static methods. But you can't do that in the Java or C# type systems. Bind of course could be an instance method that takes an M<A> as this. But there is no way to make Return anything but static. Java gives you no ability to (1) parameterize an interface by an unconstructed generic type, and (2) no ability to specify that static members are part of the interface contract.
Since there are languages which work with monads, these languages have to somehow declare the Monad type.
Well you'd think so but actually not. First off, of course any language with a sufficient type system can define monadic types; you can define all the monadic types you want in C# or Java, you just can't say what they all have in common in the type system. You can't make a generic class that can only be parameterized by monadic types, for instance.
Second, you can embed the monad pattern in the language in other ways. C# has no way to say "this type matches the monad pattern", but C# has query comprehensions (LINQ) built into the language. Query comprehensions work on any monadic type! It's just that the bind operation has to be called SelectMany, which is a little weird. But if you look at the signature of SelectMany, you'll see that it is just bind:
static IEnumerable<R> SelectMany<S, R>(
IEnumerable<S> source,
Func<S, IEnumerable<R>> selector)
That's the implementation of SelectMany for the sequence monad, IEnumerable<T>, but in C# if you write
from x in a from y in b select z
then a's type can be of any monadic type, not just IEnumerable<T>. What is required is that a is M<A>, that b is M<B>, and that there is a suitable SelectMany that follows the monad pattern. So that's another way of embedding a "monad recognizer" in the language, without representing it directly in the type system.
(The previous paragraph is actually a lie of oversimplification; the binding pattern used by this query is slightly different than the standard monadic bind for performance reasons. Conceptually this recognizes the monad pattern; in actuality the details differ slightly. Read about them here http://ericlippert.com/2013/04/02/monads-part-twelve/ if you're interested.)
A few more small points:
I was not able to find a commonly used name for the third operation, so I will just call it the unbox function.
Good choice; it is usually called the "extract" operation. A monad need not have an extract operation exposed, but of course somehow bind needs to be able to get the A out of the M<A> in order to call the Function<A, M<B>> on it, so logically some sort of extraction operation usually exists.
A comonad -- a backwards monad, in a sense -- requires an extract operation to be exposed; extract is essentially return backwards. A comonad as well requires an extend operation that is sort of bind turned backwards. It has the signature static M<B> Extend(M<A> m, Func<M<A>, B> f)