The “Option” Pattern

7
Apr
2008

As I’ve gotten to know Scala better, I’ve begun to appreciate its simple power in ways which have caught me by surprise. When I picked up the language, I was expecting to be wowed by things like type inference and a more concise syntax. I wasn’t expecting to fall in love with Option.

The Option Monad

In case you don’t know, Option is a class in the Scala core libraries. It is what object-oriented developers would call “a simple container”. It simply wraps around an instance of some type as specified in its type parameter. A simple application would be in a naive integer division function:

def div(a:Int)(b:Int):Option[Int] = if (b <= 0) None
  else if (a < b) Some(0)
  else Some(1 + div(a - b)(b).get)

Pretty straightforward stuff. This method repeatedly subtracts the dividend by the divisor until it is strictly less than the divisor. Of course, the fact that I wrote this as a pure function using currying, recursion and complex expressions obfuscates the meaning somewhat, but you get the drift. What’s really interesting here is the use of Option to encapsulate the result. Here’s how we could use this method to perform some useful(?) calculations:

div(25)(5)     // => Some(5)
div(150)(2)    // => Some(75)
div(13)(4)     // => Some(3)

Nothing earth-shattering in the mathematical realm, but it provides a useful illustration. Each return value is wrapped in an instance of class Some, which is a subclass of Option. This doesn’t seem very useful until we consider what happens when we try to divide values which break the algorithm:

div(13)(0)     // => None
div(25)(-5)    // => None

Instead of getting an integer result wrapped in an enclosing class, we get an instance of a totally different class which doesn’t appear to encapsulate any value at all. None is still a subclass of Option, but unlike Some it does not represent any specific value. In fact, it would be more accurate to say that it represents the absence of a value. This makes a lot of sense seeing as there really is no sane value for the first computation, and the second is simply incomputable with the given algorithm.

Retrieving a value from an instance of Option can be done in one of two ways. The first technique is demonstrated in the div method itself (calling the no-args get method). This is nice because it’s terse, but it’s not really the preferred way of doing things. After all, what happens if the value in question is actually an instance of None? (the answer is: Scala throws an exception) This really doesn’t seem all that compelling as a means of encapsulating return values. That is why pattern matching is more frequently employed:

div(13)(0) match {
  case Some(x) => println(x)
  case None => println("Problems")
}
// => prints "Problems"
 
div(25)(5) match {
  case Some(x) => println(x)
  case None => println("Problems")
}
// => prints "5"

Pattern matching allows us to deconstruct Option values in a type-safe manner without the risk of trying to access a value which really isn’t there. Granted, the pattern matching syntax is a bit more verbose than just calling a get polymorphically, but it’s more about the principle of the thing. It’s easy to see how this could be quite elegant in a non-trivial example.

Compared to `null`

This is very similar to a common pattern in C++ and Java. Often times a method needs to return either a value or nothing, depending on various conditions. More importantly, some internal state may be uninitialized, so a common “default” value for this state would be null. Consider the following lazy initialization:

public class Example {
    private String value;
 
    public String getValue() {
        if (value == null) {
             value = queryDatabase();
        }
 
        return value;
    }
}
 
// ...
Example ex = new Example();
System.out.println(ex.getValue());

Well, that’s all well and good, but there’s two problems with this code. Number one, there’s always the potential for stray null pointer exceptions. This is certainly less of a concern in Java than it was back in the days of C and C++, but they still can be annoying. However, let’s just assume that we’re all good programmers and we always check potentially-null values prior to use, there’s still the problem of primitive types. Let’s change our example just a bit to see where this causes issues:

public class Example {
    private int value;
 
    public int getValue() {
        if (value == ???) {    // er...?
             value = queryDatabase();
        }
 
        return value;
    }
}
 
// ...
Example ex = new Example();
System.out.println(ex.getValue());

If you’re following along at home, your compiler will probably complain at this point saying that what you just wrote was not valid Java. If your compiler didn’t complain, then you have some more serious issues that need to be addressed.

Primitive values cannot be valued as null because they are true primitives (an int is actually a bona-fide integer value sitting in a register somewhere at the hardware level). This too is a holdover from the days of C and C++, but it’s something we have to deal with. One of the consequences of this is that there is no reasonable “non-value” for primitive types. Many people have tried clever little tricks to get around this, but most of them lead to horrible and strange results:

public class Example {
    private Integer value = null;
 
    public int getValue() {
        // forgot to init...
 
        return value;
    }
}

This code will fail at runtime with a NullPointerException oddly originating from the return statement in getValue(). I can’t tell you how many times I’ve spent hours sifting through code I thought was perfectly safe before finally isolating a stray null value which the compiler happily attempted to autobox.

It’s worth briefly mentioning that a common “non-value” for integers is something negative, but this breaks down when you can have legitimate values which fall into that range. In short, there’s really no silver bullet within the Java language, so we have to turn elsewhere for inspiration.

Option in Java

I was actually working on an algorithm recently which required just such a solution. In this case, the primitive value was a boolean, so there wasn’t even a conventional non-value to jump to. I hemmed and hawed for a while before eventually deciding to implement a simple Option monad within Java. The rest of the API is remarkably functional for something written in Java (immutable state everywhere), so I figured that a few monadic types would feel right at home. Here’s what I came up with:

public interface Option<T> {
    public T get();
}
 
public final class Some<T> implements Option<T> {
    private final T value;
 
    public Some(T value) {
        this.value = value;
    }
 
    public T get() {
        return value;
    }
}
 
public final class None<T> implements Option<T> {
 
    public None() {}
 
    public T get() {
        throw new UnsupportedOperationException("Cannot resolve value on None");
    }
}

The usage for this code looks like this:

public class Example {
    private Option<Boolean> value = new None<Boolean>();
 
    public boolean getValue() {
        if (value instanceof None) {
            value = queryDatabase();
        }
 
        return value.get();
    }
}

Once again, Java has demonstrated how needlessly verbose and annoying its syntax can be. In case you were wondering, the generics are necessary on None primarily because Java has such a poor type system. Effectively, null is an untyped value which may be assigned to any class type. Java has no concept of a Nothing type which is a subtype of anything. Thus, there’s no way to provide a default parameterization for None and the developer must specify.

Now this is certainly not the cleanest API we could have written and it’s definitely not a very good demonstration of how monads can be applied to Java, but it gets the job done. If you’re interested, there’s a lot of good information out there on how do do something like this better. The point was not to create a pure monad though, the point was to create something that solved the problem at hand.

Conclusion

Once you start thinking about structuring your code to use Option in languages which have built-in support for it, you’ll find yourself dreaming about such patterns in other, less fortunate languages. It’s really sort of bizarre how much this little device can open your mind to new possibilities. Take my code, and give it a try in your project. Better yet, implement something on your own which solves the problem more elegantly! The stodgy old Java “best practices” could use a little fresh air.

P.S. Yes, I know that the original implementation of this was actually the Maybe monad in Haskell. I picked Option instead mainly because a) I like the name better, and b) it’s Scala, so it’s far more approachable than Haskell.

Comments

Funny, I’ve just been working on the same thing (mainly to wrap my functionally-undereducated Java-monkey head around monads). I’m curious, though, how useful you’re finding it in Java without case classes and pattern matching. At first glance, checking instanceof None doesn't seem much better than a null check -- though I suppose returning Some makes it more obvious that something other than a regular value might come back.

In terms of idiot-proofing -- as long as we don't have pattern matching -- it might be interesting if get() took as an argument a snippet of code to execute in the None case, so you could pass in getDatabase() to the Option and let it do the work of sorting Some from None. Ugly without something like the BGGA closure syntax, though -- you'd have to either define an interface or abuse something like Callable.

David Moles Monday, April 7, 2008 at 1:08 am
Do I understand correctly from your explenation that the only real advantage of this Option pattern is a work arround for the problem that primitive types can not have the ‘null’ value? You compare with java, but ofcourse in scala the Int type also can not be ‘null’, because it is a scala value type rather then a reference type.

If Int’s behaved truly like any other reference type, you could also use pattern matching without the Option class:

div(13)(0) match {
case null=>println(“problem”)
case x => println(x)
}

(this actually works if you rewrite the div funtion to return Integer rather then Int)

Are there any other real advantages that are not merely a work arround for primitive types?

Jan Van Besien Monday, April 7, 2008 at 2:44 am
you don’t use Some as a monad, you just use it as a simple container ( I think it was used this way in *ML long before the discovery of monads). Even though div calls itself, it uses ugly get() which defeats whole purpose of using Some because it throws exception in case of None. if all you need is getting value out of container then patternmatching is better way then try-get-catch, and if you want to use it as a monad then it’s purpose is to implement simple exceptions and combine simple computations with bind/flatMap not with underlying built-in exception engine.

try to rewrite div with scala’s for notation for flatMap and don’t use get, then you will understand monads. have fun!

Paczesiowa Monday, April 7, 2008 at 5:51 am
I very much doubt that Haskell was the first language in which the Maybe
(aka Option) type was expressed. A number of languages got variant types
and pattern matching before Haskell was born and the Maybe (aka Option)
type is such a basic example of a variant type that it would surprise me
if it was first introduced in Haskell’s standard prelude.

Also, this article really doesn’t discuss the Maybe monad. What this
article is discussing is just the Option (aka Maybe) type. The Maybe
monad, based on the Maybe type, is about gluing together computations that
may or may not yield a value. To talk about the Maybe monad, you should
introduce the return and bind (>>=) operations of the Maybe monad and
discuss how you use those to glue together computations.

But it is certainly nice that more and more programmers are interested in
FP techniques.

Vesa Karvonen Monday, April 7, 2008 at 5:58 am
You forgot the return keyword in the last Java snippet.
When you get used to Scala, Java hurts!

German B. Monday, April 7, 2008 at 6:42 am
@German

lol So I did! Correcting the article.

@Paczesiowa

Actually, get() is perfectly fine in div() because it’s provable that when I call it the value will not be None. The reason to use this over pattern matching is a more concise syntax. The reason not to use bind and flatMap is for clarity in the explanation.

@Vesa

I started the article planning on discussing more monadic techniques, but I just didn’t feel up to it. The truth of it is that I really have a weak grasp on monads myself, so I’m barely qualified to even speak the word.

Daniel Spiewak Monday, April 7, 2008 at 10:19 am
Hi Daniel,
The Option Monad comes about from the fact that the algebra (not pattern) has a bind (Scala calls it flatMap) and it is unital (a => m a), which for Option is simply the Some constructor.

The Haskell Maybe Monad was not the original implementation. In fact, Java has a monad built right in – the throws keyword (this is the disjoint union monad aka (Either a)). The Monad concept originates from a branch of mathematics called Category Theory. Note that all Monads are Functors, which implies the existence of forall a. forall b. f a -> (a -> b) -> f b. This is the map function on scala.Option.

Also, Option is a *closed* algebra in that the number of constructors is fininite (2; None and Some). This is very important in deconstruction of the algebra (i.e. pattern matching). In your Java example, your type is open, since I could potentially subtype your Option and any deconstruction using None and Some become non-exhaustive. There is a way of emulating a closed algebra in Java using a little-known language trick. I encourage you to ponder if before looking at the answer: blog.tmorris.net/maybe-in-java

Here is a more “production ready” version of Option/Maybe using Java:

projects.workingmouse.com/public/functionaljava/tags/1.1/src/main/fj/data/Option.java

Of course, I recommend at least upgrading to Scala instead of using Java, but we still have that legacy and some people insist on using Java for whatever irrational reasons.

Keep up the good work!

Tony Morris Monday, April 7, 2008 at 6:13 pm
@Tony

Your comment shows why it is a really bad idea for me to write posts about subjects I understand poorly. Your implementation is definitely better. It’s a shame that it had to be written in a language like Java encumbered with statements. Functional syntax is remarkably verbose when not everything has a value.

Anyway, definitely a prompt to me to spend some more time researching this stuff. So once you understand monads, do the mysteries of the universe just unfold before your eyes? (no pun intended)

Daniel Spiewak Monday, April 7, 2008 at 6:36 pm
G’day Daniel
It’s OK to make mistakes mate – it’s what you do about it that counts. Admission to the fact and learning probably makes it all effective in the long run.

The concept of a monad is just a model of computation. I think a typical response might be “oh, is that all it is?”, since it is indeed trivial. What follows from the abstraction however (which Scala can represent (see below), but with some hand-holding; Java cannot represent because the type system is lacking), is what it is all about.

I think that given what you have demonstrated to understand, then figuring out the monad abstraction is just one more step.

Consider the type signature of the functions for a monad (there are also laws, which are important), which Scala calls flatMap and then some other name depending on the type. Check out the Option.flatMap signature:

forall A. forall B. Option[A] => (A => Option[B]) => Option[B]

…where the first argument is ‘this’, since flatMap is declared on the class.

Now look at flatMap for List:

forall A. forall B. List[A] => (A => List[B]) => List[B]

This is precisely the same, except for the ‘type constructors’ Option and List. The monad abstraction makes these type variables. So bind has a signature:

forall A. forall B. forall M[_], M[A] => (A => M[B]) => M[B]

There is also the unit; which must have a signature:

forall A. forall M[_]. A => M[A]

which for Option is just the Some constructor (i.e. x => Some(x)) and for list is cons to Nil (i.e. x => x :: Nil). There are some laws which must hold about the flatMap/bind and unit functions, but you needn’t concern yourself to much with just yet (though, they are important to making up the monad!).

The question of “what functions can we write now across flatMap and unit such that any type declaring itself a Monad implicitly inherits these functions?” is an interesting one.

All this aside, I think understanding the Functor type is a much better middle step between say, a specific Monad (Option, as you know about) and the Monad abstraction. Functor abstracts what Scala calls the map function. For Option:

forall A. forall B. Option[A] => (A => B) => Option[B]

and for List:

forall A. forall B. List[A] => (A => B) => List[B]

Again, only the type constructor is the difference. Here is Functor.map:

forall A. forall B. forall F[_]. F[A] => (A => B) => F[B]

Are there any interesting functions that can be written across Functor? you bet – what about:

forall A. forall B. forall C. forall F[_]. F[A] => F[B] => (A => B => C) => F[C]

Indeed, this function already exists in scala.List (map2), but not Option! If we were to write one for Option, this would result in repetition (pretty much a copy/paste from the List.map2). The idea is that the abstraction prevents this repetition.

There are also laws across a Functor and they are much easier to understand than the Monad laws, making it a suitable candidate for learning first. There are two, called identity and composition and I’ll let you look them up.

There are also other computation models besides monads; applicative functors and arrows for example, both abstract a monad. That is given a monad, you can get an applicative functor and an arrow.

I won’t elaborate on these, but in summary, to answer your question about “Having your eyes opened”, it’s more about figuring out common concepts for abstraction to prevent endless repetition (leave that to the Java guys).

Hope this help

Scala Monad:
projects.workingmouse.com/public/scalaz/tags/2.4/src/main/scalaz/control/Monad.scala

Tony Morris Monday, April 7, 2008 at 6:55 pm
Thanks for the explanation, Tony. Definately food for thought. One more step on the path to enlightenment!

Daniel Spiewak Monday, April 7, 2008 at 9:53 pm
No problem mate, and if you have any questions, please feel free to ask in the Scala IRC channel:

irc://freenode.net/#scala

Tony Morris Monday, April 7, 2008 at 10:10 pm
I’ve got an ongoing-but-sleeping-at-the-moment series of articles on monads in Scala at james-iry.blogspot.com/. The goal is to introduce monads as containers and gradually move the reader towards seeing them as a way to weave an effect through a series of computations. What makes monads powerful is that the code for those computations can be written in such a way as to ignore the effect. In the case of the Maybe/Option monad the effect is optionality. But this viewpoint takes some work to get to. Good luck on your journey.

James Iry Tuesday, April 8, 2008 at 12:16 pm
I’m familiar with your series on monads and I must say that it has helped me tremendously. Obviously I still don’t understand monads very well, but your series helped boost me from “no understanding” to “superficially minimal understanding”.

Daniel Spiewak Tuesday, April 8, 2008 at 12:22 pm
Instead of returning a special instance of the container, the Java/c++ could have returned a null reference, which you’d check for just as the Scala checks for None.

A smug lisp weenie might point out that Scala needs the container because its type system is too weak to handle int or nil return values.

Note that this sort of code is somewhat fragile. There are usually lots of reasons why a function might want to return something odd and encoding them all as None (or nil) will often get you into trouble.

A smug lisp weenie can handle this case by returning a “not good” object that describes the problem. I don’t know if scala allows more interesting things than None. The java/c++ folks have bad choices here. Either they complicate the container or they go polymorphic.

Andy Freeman Wednesday, April 9, 2008 at 8:07 am
I’m very sorry to hear that. You’re my target audience: smart, motivated, and somewhat familiar with Scala. If you have any thoughts on where the articles start getting nebulous, would you mind sending me an email? I’m always looking to improve my writing.

James Iry Wednesday, April 9, 2008 at 8:11 am
I’ll have to read through the series again. To be honest, I suspect that things get nebulous more due to my own density than the quality of the writing (which is excellent).

Daniel Spiewak Wednesday, April 9, 2008 at 10:01 am
Daniel,

I look forward to hearing from you. You’re definitely not the only one to get lost on the road.

Andy,

I think you’ve been lead astray. First, Scala has null with exactly the same semantics as Java’s null, which is to say it’s a valid value for all reference types and the runtime guarantees an NPE when dereferenced. It’s just that Scala coders avoid null like the plague except when interfacing with Java libraries. Second, I know Daniel’s article says that Scala has special support for Option but it’s not really true. The Option type is pretty ordinary code that you could write for yourself. Scala does have special support for all monads (actually all classes that implement a certain interface, but in practice most will be monads). The only special support Scala has for Option lies deep in the way patten matching extractors indicate successful matches or not. So unless you write extractors by hand you can ignore that one special treatment for Option.

Third, you’ve confused lisp style runtime tags for a type system. It’s not uncommon because people use phrases like “dynamically typed” and “runtime type” but in a very precise sense, what they are talking about are not types but tags. Lisps have many powerful aspects (macros, eval, etc) but “type system” isn’t one of them – unless you count Liskell and Qi as lisps.

Fourth, the answer available in lisps (return whatever you want and let the caller figure out what to do with it based on a tag) is available in any tagged (aka “dynamically typed” language). You can do it in Python, Perl, Ruby, etc, etc. It is, in fact, available in Scala (and Java and C#) as well. That’s because Java/Scala/C#/etc have a tagging systems that parallel (more or less) their static typing system and they all have a top type or something close to a top type.

James Iry Wednesday, April 9, 2008 at 11:37 am
“Either they complicate the container”, that’s exactly what haskell people do! we use Either type which is parameterized over return valu and exception type (like string).

Paczesiowa Wednesday, April 9, 2008 at 11:44 am
In your Java implementation, I don’t see why None has to have a type parameter. Can’t you just write: public class None implements Option?