Maybe in Java
In Haskell, there is an algebraic data type called Maybe to represent evaluation of a partial function. That is, if you have a function, say f(x), and f(x) is defined for some x, but not all x, you return either:
- A type Maybe that has a value available - called Just a where a is the value - representing defined function evaluation.
- A type Maybe that has no value available - called Nothing - representing undefined function evaluation.
In fact, if we were to look at the source for the Maybe algebraic data type in GHC, we’d see this:
data Maybe a = Just a | Nothing
Not much to it, eh!? This Haskell snippet can be read as “Declare type Maybe with one polymorphic unbound variable ‘a’ that can be constructed as either Just ‘a’ or Nothing”.
Consider a real Java example, List<T>.get(int index), which returns a type T where T is a type parameter (it once returned type Object prior to 1.5). For some Lists and some ints, this function is undefined. For example, for the list [1,2,3] and the int 7, List.get is undefined. In fact, this will throw an IndexOutOfBoundsException if attempted:
java.util.Arrays.asList(new Integer[]{1, 2, 3}).get(7);
Throwing an exception is one of our possible options for evaluation of a partial function in Java. Here are all our options available in Java:
- Return
null - Throw a compile-time checked exception
- Throw an unchecked exception
- Emulate continuation passing style (CPS)
I have distinguished checked and unchecked exceptions for a specific reason that I’ll leave for another day and I won’t go into great detail about any of these options in specific, since I am currently in the middle of documenting all this in more detail along with some basic type theory. However I will note that each of these options for evaluation of a partial function have some kind of nasty consequence. For example, the value null is assignable to any reference type and so can inadvertently be passed along to a method (I am sure you have seen this before):
T t = f(x); // is t null? // the compiler doesn't force us to check! // how does the method behave now? method(t);
And how long has that checked/unchecked exception debate been going? Yes there is a reason it has been going for so long - in fact, it is riding on a flawed premise so it will continue on forever until its participants realise this flaw - but we’ll leave that for another day and smile and nod in the meantime. 
With a Maybe data type, we might instead write our function/method as:
Maybe<T> List<T>.get(int index)
…where undefined behaviour is denoted by returning Nothing and defined behaviour is denoted with Just T. We should also be assured that only one of these two things will occur. No more returning null, no more throwing exceptions!! How wonderful would that be!? Well, if you’ve ever dabbled in Haskell or type theory, you’ll know immediately how great that would be - but what about Java?
An initial and naive attempt to emulate Maybe fails immediately:
interface Maybe<T> {
T get();
}
We see that we have isolated our apparent anomaly that we are trying to resolve. We must still either return null or throw an exception from the Maybe.get method, but no other method ever need do so - as long as we (hopefully) remember to check for null for any given Maybe. While a slight improvement, this of course, does not solve our problem. We are still returning null or throwing exceptions and importantly, suffering the adverse consequences of doing so (we want the compiler to fail, not have to remember to do stuff!). Instead, we need to use types to represent Just and Nothing. Let’s try another attempt.
interface Maybe<T> {
}
interface Just<T> extends Maybe<T> {
T get();
}
interface Nothing<T> extends Maybe<T> {
}
Done!! Or not. There is a specific guarantee that our Haskell data type makes that our Java attempt doesn’t. Specifically, if a Maybe is not Just, then it is definitely Nothing and vice versa in Haskell - this is important if we are to continue. We can see that this constraint does not hold for our Java Maybe because it can have any number of sub-types - of course - since it is an interface. We know how to constrain a type to have zero sub-types; by using a class with the final keyword. We know how to free a type to have infinite sub-types; without the final keyword or an interface. But what about constraining a type to 2 and only 2 sub-types?
This can be achieved by exploiting a little known Java language feature - a type cannot be sub-typed if it has only private constructors unless those sub-types are nested in the super-type. It seems we can indeed have a Maybe algebraic data type in Java by having 2 and only 2 sub-types!
public abstract class Maybe{ private Maybe() { } public static abstract class Nothing extends Maybe { private Nothing() { } } public static abstract class Just extends Maybe { private Just() { } public abstract T just(); } }
Looking good so far. We now know for sure that every instance of Maybe is either Just or Nothing and if it is Just, we have a value available through the get method - exactly what we ordered. As it stands though, we cannot create instances - let’s expose these through public methods.
public abstract class Maybe<T> {
private Maybe() {
}
public static abstract class Nothing<T> extends Maybe<T> {
private Nothing() {
}
}
public static abstract class Just<T> extends Maybe<T> {
private Just() {
}
public abstract T just();
}
public static <T> Maybe<T> _just(final T t) {
return new Just<T>() {
public T just() {
return t;
}
};
}
public static <T> Maybe<T> _nothing() {
return new Nothing<T>() {
};
}
}
And so there we have it - an algebraic data type in Java for evaluation of a partial function. How does our List method look now? How about this:
Maybe<T> List<T>.get(int index)
Clients of this method will now check if the return type is either Just or Nothing and in the case of Just, perform a downcast and retrieve the value. No more returning null. No more throwing exceptions. Not ever!
I’ll let your imagination run wild with possibilities from here
As I have mentioned, I plan to go into greater detail about this problem by documenting it in detail so keep an eye out on the Workingmouse Research page.
Until then, I’ll keep you wondering will a small piece of interesting code:
import java.util.List;
import java.util.LinkedList;
import java.util.Map;
import java.util.Hashtable;
class ListMap {
public static void main(String[] args) {
Map<Integer, String> map =
new Hashtable<Integer, String>();
map.put(0, "x");
map.put(1, "y");
map.put(2, "z");
List<String> list =
new LinkedList<String>();
list.add(0, "x");
list.add(1, "y");
list.add(2, "z");
// xyz
System.out.println(map.get(0) + map.get(1) + map.get(2));
// xyz
System.out.println(list.get(0) + list.get(1) + list.get(2));
// returns null
System.out.println(map.get(7));
// throws IndexOutOfBoundsException
System.out.println(list.get(7));
}
}
November 14th, 2006 at 10:25 pm
Hi Tony,
By trying to emulate Haskell precisely, you’ve gone backwards a step from what I showed you some time ago, I fear.
In Java, we don’t need to care about which class really implements an interface, we only care about the behaviour, except in security-conscious code.
Your downcasting solution certainly works, but it isn’t optimal.
Instead, a Maybe needs a method - accept, that takes a function and a value The function is run if the Maybe is a ‘just’, and the return value returned to the caller of accept. If the Maybe is nothing, then the value is returned instead. I’ll use [] for generics because there’s no preview button and I don’t want them swallowed as HTML.
public interface Maybe[T]
{
[R] R accept(Function[T,R] ifExists,R reserve);
}
I found that a utility method to convert a ‘nullable’ into a Maybe is handy, and one back again (that throws an exception if the Maybe is a ‘just’ - it doesn’t return null!), especially while migrating from ‘code that sucks’ to
‘code that doesn’t’.
My code for this is all in functionalpeas - http://code.google.com/p/functionalpeas/ - directly to the maybe package: http://functionalpeas.googlecode.com/svn/trunk/src/fpeas/maybe/
Cheers.
November 14th, 2006 at 11:19 pm
So now instead of simply checking for null I have to test the type with instanceof, then cast it if it is a Just, and finally get the actual result?
Before:
> if (x != null) {
> doSomethingWith(x);
> }
After:
> if (x instanceof Just) {
> T value = ((Just x).get();
> doSometingWith(value);
> }
Without Haskell’s integrated pattern matching, I don’t see how this is an improvement… Did I miss something?
November 15th, 2006 at 7:22 am
Hi dibblego, just a nitpick here.
Maybe doesn’t represent partial function evaluation — it represents the evaluation of a partial function.
Partial evaluation is a compiler optimization where parts of an expression which are static can be evaluated at compile time, for example 2 * 3 * x can become 6 * x.
A partial function is a function from a set X to a set Y where applying the function to an element of X can either yield an element of Y, or a disjoint ‘bottom’ value.
November 15th, 2006 at 8:45 am
Thanks Slava, I will update accordingly.
Arch, to answer your question in a justified manner, I think I would need to write a follow-up post, but you’re certainly not the first person to ask and while it is a very good point, I think there are some subtle differences.
November 15th, 2006 at 11:08 am
Arch,
The improvement is that you can’t forget to check for null — if you just call
doSomethingWith(x) you’ll get a compile time error.
Here’s another way of doing it:
public class Maybe { private T value; public Maybe(T value) { this.value = value; } public void maybe(Functor0 nothing, Functor1 just) { if (value == null) { nothing.call(); } else { just.call(value); } } } abstract class Functor0 { public abstract void call(); } abstract class Functor1 { public abstract void call(T value); } class DefaultSpaceManager { public Maybe getPersonalSpace(User user) { String spaceKey = user.getPersonalSpaceKey(); return new Maybe(spaceDao.getSpace(spaceKey)); } private void addPersonalAndCurrentSpace(final List spaces) { // Add the personal space of the current user to the space list. Maybe personalSpace = spaceManager.getPersonalSpace(getRemoteUser()); ... personalSpace.maybe( new Functor0() { public void call() { } }, new Functor1() { public void call(Space value) { // value is guaranteed not to be null if (!spaces.contains(value)) spaces.add(value); } }); ... } ... }November 16th, 2006 at 8:29 am
Hi Ricky,
I think your solution is not optimal and in fact, I did cover it when I said, “Emulate continuation passing style (CPS)”. The drawbacks of this approach are something that I intend to cover in a more detailed document, nevertheless, the given Maybe implementation is not complete.
I only intended to point out that it is possible (though a poor man’s implementation) to emulate an algebraic data type with Java. I intend to cover this topic much more thoroughly by first introducing intersection types [1] and working from there.
November 16th, 2006 at 9:10 pm
I don’t think mine is quite a CPS, as the functions run aren’t intended to have side-effects, although of course they can.
That’s why the generic parameter R is declared on the method, so that you can call ‘accept’ and have it return anything.
You can use it like a CPS if you make R a Runnable, which I did for a short while, but, to be honest, I kept forgetting to tag ‘.run()’ to the end.
maybe.accept(functionThatReturnsARunnable,anotherRunnable).run();
A non-CPS use of the ‘functional’ Maybe:
For example, my automated tests operate on a JFrame. I wrapped JFrame so that I can instantiate my version in ‘headless’ mode, but sometimes you need to get at the original JFrame, e.g., to pass a ‘this’ pointer to a layout manager. So I have:
Maybe[javax.swing.JFrame] getRealFrame(); in my JFrame interface.
Suppose I want to find out whether the real frame is visible, and assume it’s not if it doesn’t exist. In reality I can call ‘isVisible()’ on my own JFrame interface, but let’s suppose I didn’t implement that..
Function[JFrame,Boolean] isVisible=new Function[JFrame,Boolean]()
{
public Boolean run(JFrame frame)
{
return frame.isVisible();
}
};
frame.getRealFrame().accept(isVisible,false);
Of course, Java’s syntax doesn’t make the above function definition pretty.
It’d be nicer if we could use delegates:
frame.getRealFrame().accept(JFrame.isVisible,false);
or closures:
frame.getRealFrame().accept({t.isVisible()},false);
Of course, simply ‘frame.isVisible()’ is preferable there, instead of that whole line, as each implementation of my JFrame wrapper interface knows for definite (no Maybes about it) whether it has a real frame or not.
By the way, nice lambdas. I’ll try not to mistake them for a wishbone.
November 16th, 2006 at 9:16 pm
One more thing, what’re your thoughts on Gilad Bracha’s Pluggable Types?
http://bracha.org/pluggable-types.pdf
December 18th, 2006 at 2:09 pm
[…] As I have shown previously, the problem of partial function in Java is not easily solved. The solution of the Maybe algebraic data type, while definitely superior to existing options, is cumbersome to implement and requires some functions defined over the type (isJust, isNothing, etc.) in order to be complete. As some point out, there is a preference for continuation passing to prevent the need for a cast (even though this case would be hidden). This prompted me to provide a more complete solution - which is still only a subset of a complete solution. […]
January 1st, 2007 at 11:03 am
[…] Looking good so far. But don’t be fooled - there is a huge problem. Namely, that the interface cannot be implemented correctly. Keeping with tradition, let’s attempt to write the Maybe monad: […]
January 3rd, 2007 at 7:25 am
Your problem is you are trying to fit a square peg in a round hole. Java is not a functional language, and attempts to fit it in your narrow veiw of what is proper will never work.
January 26th, 2007 at 10:17 am
But Bill, you have assumed I even have a problem - I simply don’t. I don’t use Java anymore. In fact, I used to work on the IBM implementation and I thankfully made the correct decision in leaving that behind.
I am not trying to fit anything anywhere; merely, provide a layperson perspective of an existing problem to the laypeople - the Java programmers.
I have absolutely no ambition of using Java as a functional language. OK, this is a bit of a lie, since I use Scala quite a lot these days - whose very existence refutes your claim that it cannot be done. You might also wish to refer to my post titled Fix It Sun!, which outlines the single biggest bottleneck in software development progress - the inability to tail call on the Sun JVM (the IBM JVM works fine, so long as it is not an indirect tail call).
In the meantime, I will use Haskell/Scala et. al. and watch the Java programmers struggle with solving even the most basic of problems - that of partial function. I will make efforts to provide insight for those seek it of course, hence this post.
August 4th, 2007 at 2:23 pm
[…] If we consider a Java or C# class that can somehow enforce 2 and only 2 subclasses, then we could emulate closed algebraic data types in these languages. Indeed, it is possible to do so, however, you have to get really quirky with the language at hand. I have written about this before, but instead of using this trick, I am going to invent a new keyword for these languages called klass. […]