Monads are Elephants Part 4

Until you experience an adult elephant first hand you won't really understand just how big they can be. If monads are elephants then so far in this series of articles I've only presented baby elephants like List and Option. But now it's time to see a full grown adult pachyderm. As a bonus, this one will even do a bit of circus magic.

Functional Programming and IO

In functional programming there's a concept called referential transparency. Referential transparency means you can call a particular function anywhere and any time and the same arguments will always give the same results. As you might imagine, a referentially transparent function is easier to use and debug than one that isn't.

There's one area where referential transparency would seem impossible to achieve: IO. Several calls to the same readLine console function may result in any number of different strings depending on things like what the user ate for breakfast. Sending a network packet may end in successful delivery or it might not.

But we can't get rid of IO just to accomplish referential transparency. A program without IO is just a complicated way to make your CPU hot.

You might guess that monads provide a solution for referentially transparent IO given the topic of this series but I'm going to work my way up from some simple principles. I'll solve the problem for reading and writing strings on the console but the same solution can be extended to arbitrary kinds of IO like file and network.

Of course, you may not think that referentially transparent IO is terribly important in Scala. I'm not here to preach the one true way of purely functional referential transparency. I'm here to talk about monads and it just so happens that the IO monad is very illustrative of how several monads work.

The World In a Cup

Reading a string from the console wasn't referentially transparent because readLine depends on the state of the user and "user" isn't one of its parameters. A file reading function would depend on the state of the file system. A function that reads a web page would depend on the state of the target web server, the Internet, and the local network. Equivalent output functions have similar dependencies.

All this could be summed up by creating a class called WorldState and making it both a parameter and a result for all IO functions. Unfortunately, the world is a big place. My first attempt to write a WorldState resulted in a compiler crash as it ran out of memory. So instead I'll try for something a bit smaller than modeling the whole universe. That's where a bit of circus magic comes in.

The slight-of-hand I'll use is to model only a few aspects of the world and just pretend WorldState knows about the rest of the world. Here are some aspects that would be useful

1. The state of the world changes between IO functions.
2. The world's state is what it is. You can't just create new ones whenever you want (val coolWorldState = new WorldState(){def jamesIsBillionaire = true}).
3. The world is in exactly one state at any moment in time.

Property 3 is a bit tricky so let's deal with properties 1 and 2 first.

Here's a rough sketch for property 1

//file RTConsole.scala
object RTConsole_v1 {
  def getString(state: WorldState) = 
    (state.nextState, Console.readLine)
  def putString(state: WorldState, s: String) = 
    (state.nextState, Console.print(s) )
}

getString and putString use functions defined in scala.Console as raw primitive functions. They take a world state and return a tuple consisting of a new world state and the result of the primitive IO.

Here's how I'll implement property 2

//file RTIO.scala
sealed trait WorldState{def nextState:WorldState}

abstract class IOApplication_v1 {
  private class WorldStateImpl(id:BigInt) 
      extends WorldState {
    def nextState = new WorldStateImpl(id + 1)
  }
  final def main(args:Array[String]):Unit = {
    iomain(args, new WorldStateImpl(0))
  }
  def iomain(
      args:Array[String], 
      startState:WorldState):(WorldState, _)
}

WorldState is a sealed trait; it can only be extended within the same file. IOApplication defines the only implementation privately so nobody else can instantiate it. IOApplication also defines a main function that can't be overridden and calls a function named iomain that must be implemented in a subclass. All of this is plumbing that is meant to be hidden from programmers that use the IO library.

Here's what hello world looks like given all this

// file HelloWorld.scala
class HelloWorld_v1 extends IOApplication_v1 {
  import RTConsole_v1._
  def iomain(
        args:Array[String], 
        startState:WorldState) = 
    putString(startState, "Hello world")
}

That Darn Property 3

The 3rd property said that the world can only be in one state at any given moment in time. I haven't solved that one yet and here's why it's a problem

class Evil_v1 extends IOApplication_v1 {
  import RTConsole_v1._
  def iomain(
      args:Array[String], 
      startState:WorldState) = {
    val (stateA, a) = getString(startState)
    val (stateB, b) = getString(startState)
    assert(a == b)
    (startState, b)
  }
}

Here I've called getString twice with the same inputs. If the code was referentially transparent then the result, a and b, should be the same but of course they won't be unless the user types the same thing twice. The problem is that "startState" is visible at the same time as the other world states stateA and stateB.

Inside Out

As a first step towards a solution, I'm going to turn everything inside out. Instead of iomain being a function from WorldState to WorldState, iomain will return such a function and the main driver will execute it. Here's the code

//file RTConsole.scala
object RTConsole_v2 {
  def getString = {state:WorldState => 
    (state.nextState, Console.readLine)}
  def putString(s: String) = {state: WorldState => 
    (state.nextState, Console.print(s))}
}

getString and putString no longer get or put a string - instead they each return a new function that's "waiting" to be executed once a WorldState is provided.

//file RTIO.scala
sealed trait WorldState{def nextState:WorldState}

abstract class IOApplication_v2 {
  private class WorldStateImpl(id:BigInt) 
      extends WorldState {
    def nextState = new WorldStateImpl(id + 1)
  }
  final def main(args:Array[String]):Unit = {
    val ioAction = iomain(args)
    ioAction(new WorldStateImpl(0));
  }
  def iomain(args:Array[String]):
    WorldState => (WorldState, _)
}

IOApplication's main driver calls iomain to get the function it will execute, then executes that function with an initial WorldState. HelloWorld doesn't change too much except it no longer takes a WorldState.

//file HelloWorld.scala
class HelloWorld_v2 extends IOApplication_v2 {
  import RTConsole_v2._
  def iomain(args:Array[String]) = 
    putString("Hello world")
}

At first glance we seem to have solved our problem because WorldState is nowhere to be found in HelloWorld. But it turns out it's just been buried a bit.

Oh That Darn Property 3

class Evil_v2 extends IOApplication_v2 {
  import RTConsole_v2._
  def iomain(args:Array[String]) = {        
    {startState:WorldState =>
      val (statea, a) = getString(startState)
      val (stateb, b) = getString(startState)
      assert(a == b)
      (startState, b)
    }
  }
}

Evil creates exactly the kind of function that iomain is supposed to return but once again things are broken. As long as the programmer can create arbitrary IO functions he or she can see through the WorldState trick.

Property 3 Squashed For Good

All we need to do is prevent the programmer from creating arbitrary functions with the right signature. Um...we need to do what now?

Okay, as we saw with WorldState it's easy to prevent programmers from creating subclasses. So let's turn our function signature into a trait.

sealed trait IOAction[+A] extends 
  Function1[WorldState, (WorldState, A)] 

private class SimpleAction[+A](
   expression: => A) extends IOAction[A]...

Unlike WorldState we do need to create IOAction instances. For example, getString and putString are in a separate file but they would need to create new IOActions. We just need them to do so safely. It's a bit of a dilemma until we realize that getString and putString have two separate pieces: the piece that does the primitive IO and the piece that turns the input world state into the next world state. A bit of a factory method might help keep things clean, too.

//file RTIO.scala
sealed trait IOAction_v3[+A] extends 
  Function1[WorldState, (WorldState, A)] 

object IOAction_v3 {
  def apply[A](expression: => A):IOAction_v3[A] = 
    new SimpleAction(expression)

  private class SimpleAction [+A](
      expression: => A) extends IOAction_v3[A] {
    def apply(state:WorldState) = 
      (state.nextState, expression)
  }
}

sealed trait WorldState{def nextState:WorldState}

abstract class IOApplication_v3 {
  private class WorldStateImpl(id:BigInt) 
      extends WorldState {
    def nextState = new WorldStateImpl(id + 1)
  }
  final def main(args:Array[String]):Unit = {
    val ioAction = iomain(args)
    ioAction(new WorldStateImpl(0));
  }
  def iomain(args:Array[String]):IOAction_v3[_]
}

The IOAction object is just a nice factory to create SimpleActions. SimpleAction's constructor takes a lazy expression as an argument, hence the "=> A" annotation. That expression won't be evaluated until SimpleAction's apply method is called. To call SimpleAction's apply method, a WorldState must be passed in. What comes out is a tuple with the new WorldState and the result of the expression.

Here's what our IO methods look like now

//file RTConsole.scala
object RTConsole_v3 {
  def getString = IOAction_v3(Console.readLine)
  def putString(s: String) = 
    IOAction_v3(Console.print(s))
}

And finally our HelloWorld class doesn't change a bit

class HelloWorld_v3 extends IOApplication_v3 {
  import RTConsole_v3._
  def iomain(args:Array[String]) = 
    putString("Hello world")
}

A little thought shows that there's no way to create an Evil IOApplication now. A programmer simply has no access to a WorldState. It has become totally sealed away. The main driver will only pass a WorldState to an IOAction's apply method, and we can't create arbitrary IOAction subclasses with custom definitions of apply.

Unfortunately, we've got a combining problem. We can't combine multiple IOActions so we can't do something as simple as "What's your name", Bob, "Hello Bob."

Hmmmm, IOAction is a container for an expression and monads are containers. IOAction needs to be combined and monads are combinable. Maybe, just maybe...

Ladies and Gentleman I Present the Mighty IO Monad

The IOAction.apply factory method takes an expression of type A and returns an IOAction[A]. It sure looks like "unit." It's not, but it's close enough for now. And if we knew what flatMap was for this monad then the monad laws would tell us how to create map using it and unit. But what's flatMap going to be? The signature needs to look like def flatMap[B](f: A=>IOAction[B]):IOAction[B]. But what does it do?

What we want it to do is chain an action to a function that returns an action and when activated causes the two actions to occur in order. In other words, getString.flatMap{y => putString(y)} should result in a new IOAction monad that, when activated, first activates the getString action then does the action that putString returns. Let's give it a whirl.

//file RTIO.scala
sealed abstract class IOAction_v4[+A] extends 
    Function1[WorldState, (WorldState, A)] {
  def map[B](f:A => B):IOAction_v4[B] = 
    flatMap {x => IOAction_v4(f(x))}  
  def flatMap[B](f:A => IOAction_v4[B]):IOAction_v4[B]= 
    new ChainedAction(this, f)
  
  private class ChainedAction[+A, B](
      action1: IOAction_v4[B], 
      f: B => IOAction_v4[A]) extends IOAction_v4[A] {
    def apply(state1:WorldState) = {
      val (state2, intermediateResult) = 
        action1(state1);
      val action2 = f(intermediateResult)
      action2(state2)
    }
  }  
}

object IOAction_v4 {
  def apply[A](expression: => A):IOAction_v4[A] = 
    new SimpleAction(expression)

  private class SimpleAction[+A](expression: => A) 
      extends IOAction_v4[A] {
    def apply(state:WorldState) = 
      (state.nextState, expression)
  }    
}

// the rest remains the same
sealed trait WorldState{def nextState:WorldState}

abstract class IOApplication_v4 {
  private class WorldStateImpl(id:BigInt) ...

The IOAction factory and SimpleAction remain the same. The IOAction class gets the monad methods. Per the monad laws, map is just defined in terms of flatMap and what we're using as unit for now. flatMap defers all the hard work to a new IOAction implementation called ChainedAction.

The trick in ChainedAction is its apply method. First it calls action1 with the first world state. This results in a second world state and an intermediate result. The function it was chained to needs that result and in return the function generates another action: action2. action2 is called with the second world state and the tuple that come out is the end result. Remember that none of this will happen until the main driver passes in an initial WorldState object.

A Test Drive

At some point you may have wondered why getString and putString weren't renamed to something like createGetStringAction/createPutStringAction since that's in fact what they do. For an answer, look at what happens when we stick 'em in our old friend "for".

object HelloWorld_v4 extends IOApplication_v4 {
  import RTConsole_v4._
  def iomain(args:Array[String]) = {
    for{
        _ <- putString(
            "This is an example of the IO monad.");
        _ <- putString("What's your name?");
        name <- getString;
        _ <- putString("Hello " + name)
    } yield ()
  }
}

It's as if "for" and getString/putString work together to create a mini language just for creating a complex IOActions.

Take a Deep Breath

Now's a good moment to sum up what we've got. IOApplication is pure plumbing. Users subclass it and create a method called iomain which is called by main. What comes back is an IOAction - which could in fact be a single action or several actions chained together. This IOAction is just "waiting" for a WorldState object before it can do its work. The ChainedAction class is responsible for ensuring that the WorldState is changed and threaded through each chained action in turn.

getString and putString don't actually get or put Strings as their names might indicate. Instead, they create IOActions. But, since IOAction is a monad we can stick it into a "for" statement and the result looks as if getString/putString really do what they say the do.

It's a good start; we've almost got a perfectly good monad in IOAction. We've got two problems. The first is that, because unit changes the world state we're breaking the monad laws slightly (e.g. m flatMap unit === m). That's kinda trivial in this case because it's invisible. But we might as well fix it.

The second problem is that, in general, IO can fail and we haven't captured that just yet.

IO Errors

In monadic terms, failure is represented by a zero. So all we need to do is map the native concept of failure (exceptions) to our monad. At this point I'm going to take a different tack from what I've been doing so far: I'll write one final version of the library with comments inline as I go.

The IOAction object remains a convenient module to hold several factories and private implementations (which could be anonymous classes, but it's easier to explain with names). SimpleAction remains the same and IOAction's apply method is a factory for them.

//file RTIO.scala
object IOAction {
  private class SimpleAction[+A](expression: => A) 
      extends IOAction[A] {
    def apply(state:WorldState) = 
      (state.nextState, expression)
  }

  def apply[A](expression: => A):IOAction[A] = 
    new SimpleAction(expression)

UnitAction is a class for unit actions - actions that return the specified value but don't change the world state. unit is a factory method for it. It's kind of odd to make a distinction from SimpleAction, but we might as well get in good monad habits now for monads where it does matter.

  private class UnitAction[+A](value: A) 
      extends IOAction[A] {
    def apply(state:WorldState) = 
      (state, value)
  }
  
  def unit[A](value:A):IOAction[A] = 
    new UnitAction(value)

FailureAction is a class for our zeros. It's an IOAction that always throws an exception. UserException is one such possible exception. The fail and ioError methods are factory methods for creating zeroes. Fail takes a string and results in an action that will raise a UserException whereas ioError takes an arbitrary exception and results in an action that will throw that exception.

  private class FailureAction(e:Exception) 
      extends IOAction[Nothing] {
    def apply(state:WorldState) = throw e
  }
  
  private class UserException(msg:String) 
    extends Exception(msg)

  def fail(msg:String) = 
    ioError(new UserException(msg))    
  def ioError[A](e:Exception):IOAction[A] = 
    new FailureAction(e)
}

IOAction's flatMap, and ChainedAction remain the same. Map changes to actually call the unit method so that it complies with the monad laws. I've also added two bits of convenience: >> and <<. Where flatMap sequences this action with a function that returns an action, >> and << sequence this action with another action. It's just a question of which result you get back. >>, which can be pronounced "then", creates an action that returns the second result, so 'putString "What's your name" >> getString' creates an action that will display a prompt then return the user's response. Conversely, <<, which can be called "before" creates an action that will return the result from the first action.

sealed abstract class IOAction[+A] 
    extends Function1[WorldState, (WorldState, A)] {
  def map[B](f:A => B):IOAction[B] = 
    flatMap {x => IOAction.unit(f(x))}  
  def flatMap[B](f:A => IOAction[B]):IOAction[B]=
    new ChainedAction(this, f)

  private class ChainedAction[+A, B](
      action1: IOAction[B], 
      f: B => IOAction[A]) extends IOAction[A] {
    def apply(state1:WorldState) = {
      val (state2, intermediateResult) = 
        action1(state1);
      val action2 = f(intermediateResult)
      action2(state2)
    }
  }  

  def >>[B](next: => IOAction[B]):IOAction[B] =
    for {
      _ <- this;
      second <- next
    } yield second
    
  def <<[B](next: => IOAction[B]):IOAction[A] =
    for {
      first <- this;
      _ <- next
    } yield first

Because we've got a zero now, it's possible to add a filter method by just following the monad laws. But here I've created two forms of filter method. One takes a user specified message to indicate why the filter didn't match whereas the other complies with Scala's required interface and uses a generic error message.

  def filter(
      p: A => Boolean, 
      msg:String):IOAction[A] =
    flatMap{x => 
      if (p(x)) IOAction.unit(x) 
      else IOAction.fail(msg)}
  def filter(p: A => Boolean):IOAction[A] =
    filter(p, "Filter mismatch")

A zero also means we can create a monadic plus. As some infrastructure for creating it, HandlingAction is an action that wraps another action and if that action throws an exception then it sends that exception to a handler function. onError is a factory method for creating HandlingActions. Finally, "or" is the monadic plus. It basically says that if this action fails with an exception then try the alternative action.

    
  private class HandlingAction[+A](
      action:IOAction[A],
      handler: Exception => IOAction[A]) 
      extends IOAction[A] {
    def apply(state:WorldState) = {
      try {
        action(state)
      } catch {
        case e:Exception => handler(e)(state)
      }
    }    
  }

  def onError[B >: A](
      handler: Exception => IOAction[B]):
      IOAction[B] = 
    new HandlingAction(this, handler)      

  def or[B >: A](
      alternative:IOAction[B]):IOAction[B] =
    this onError {ex => alternative}
}

The final version of IOApplication stays the same

sealed trait WorldState{def nextState:WorldState}

abstract class IOApplication {
  private class WorldStateImpl(id:BigInt) 
      extends WorldState {
    def nextState = new WorldStateImpl(id + 1)
  }
  final def main(args:Array[String]):Unit = {
    val ioaction = iomain(args)
    ioaction(new WorldStateImpl(0));
  }
  def iomain(args:Array[String]):IOAction[_]
}

RTConsole stays mostly the same, but I've added a putLine method as an analog to println. I've also changed getString to be a val. Why not? It's always the same action.

//file RTConsole.scala
object RTConsole {
  val getString = IOAction(Console.readLine)
  def putString(s: String) = 
    IOAction(Console.print(s))
  def putLine(s: String) = 
    IOAction(Console.println(s))
}  

And now a HelloWorld application to exercise some of this new functionality. sayHello creates an action from a string. If the string is a recognized name then the result is an appropriate (or inappropriate) greeting. Otherwise it's a failure action.

Ask is a convenience method that creates an action that will display a specified string then get one. The >> operator ensures that the action's result will be the result of getString.

processsString takes an arbitrary string and, if it's 'quit' then it creates an action that will say goodbye and be done. On any other string sayHello is called. The result is combined with another action using 'or' in case sayHello fails. Either way the action is sequenced with the loop action.

Loop is interesting. It's defined as a val just because it can be - a def would work just as well. So it's not quite a loop in the sense of being a recursive function, but it is a recursive value since it's defined in terms of processString which in turn is defined based on loop.

The iomain function kicks everything off by creating an action that will display an intro then do what the loop action specifies.

Warning: because of the way the library is implemented this loop will eventually blow the stack. Do not use it in production code. Read the comments to see why.

object HelloWorld extends IOApplication {
  import IOAction._
  import RTConsole._
  
  def sayHello(n:String) = n match {
    case "Bob" => putLine("Hello, Bob")
    case "Chuck" => putLine("Hey, Chuck")
    case "Sarah" => putLine("Helloooo, Sarah")
    case _ => fail("match exception")
  }
  
  def ask(q:String) =
    putString(q) >> getString

  def processString(s:String) = s match {
    case "quit" => putLine("Catch ya later")
    case _ => (sayHello(s) or         
        putLine(s + ", I don't know you.")) >>

        loop 
  }
    
  val loop:IOAction[Unit] = 
    for {
      name <- ask("What's your name? ");
      _ <- processString(name)
    } yield ()
  
  def iomain(args:Array[String]) = {
    putLine(
        "This is an example of the IO monad.") >>
    putLine("Enter a name or 'quit'") >>
    loop
  }
}

Conclusion for Part 4

In this article I've called the IO monad 'IOAction' to make it clear that instances are actions that are waiting to be performed. Many will find the IO monad of little practical value in Scala. That's okay, I'm not here to preach about referential transparency. However, the IO monad is one of the simplest monads that's clearly not a collection in any sense.

Still, instances of the IO monad can be seen as containers. But instead of containing values they contain expressions. flatMap and map in essence turn the embedded expressions into more complex expressions.

Perhaps a more useful mental model is to see instances of the IO monad as computations or functions. flatMap can be seen as applying a function to the computation to create a more complex computation.

In the last part of this series I'll cover a way to unify the container and computation models. But first I want to reinforce how useful monads can be by showing an application that uses an elephantine herd of monads to do something a bit more complicated.

Monads are Elephants Part 3

In this series I've presented an alternative view on the old parable about the blind men and the elephant. In this view, listening to the limited explanations from each of the blind men eventually leads to a pretty good understanding of elephants.

So far we've been looking at the outside of monads in Scala. That's taken us a great distance, but it's time to look inside. What really makes an elephant an elephant is its DNA. Monads have a common DNA of their own in the form of the monadic laws.

This article is a lot to digest all at once. It probably makes sense to read it in chunks. It can also be useful to re-read by substituting a monad you already understand (like List) into the laws.

Equality for All

Before I continue, I have to semi-formally explain what I mean when I use triple equals in these laws as in "f(x) ≡ g(x)." What I mean is what a mathematician might mean by "=" equality. I'm just avoiding single "=" to prevent confusion with assignment.

So I'm saying the expression on the left is "the same" as the expression on the right. That just leads to a question of what I mean by "the same."

First, I'm not talking about reference identity (Scala's eq method). Reference identity would satisfy my definition, but it's too strong a requirement. Second, I don't necessarily mean == equality either unless it happens to be implemented just right.

What I do mean by "the same" is that two objects are indistinguishable without directly or indirectly using primitive reference equality, reference based hash code, or isInstanceOf.

In particular it's possible for the expression on the left to lead to an object with some subtle internal differences from the object on the right and still be "the same." For example, one object might use an extra layer of indirection to achieve the same results as the one on the right. The important part is that, from the outside, both objects must behave the same.

One more note on "the same." All the laws I present implicitly assume that there are no side effects. I'll have more to say about side effects at the end of the article.

Breaking the Law

Inevitably somebody will wonder "what happens if I break law x?" The complete answer depends on what laws are broken and how, but I want to approach it holistically first. Here's a reminder of some laws from another branch of mathematics. If a, b, and c are rational numbers then multiplication (*) obeys the following laws:

1. a * 1 ≡ a
2. a * b ≡ b * a
3. (a * b) * c ≡ a * (b * c)

Certainly it would be easy to create a class called "RationalNumber" and implement a * operator. But if it didn't follow these laws the result would be confusing to say the least. Users of your class would try to plug it into formulas and would get the wrong answers. Frankly, it would be hard to break these laws and still end up with anything that even looks like multiplication of rational numbers.

Monads are not rational numbers. But they do have laws that help define them and their operations. Like arithmetic operations, they also have "formulas" that allow you to use them in interesting ways. For instance, Scala's "for" notation is expanded using a formula that depends on these laws. So breaking the monad laws is likely to break "for" or some other expectation that users of your class might have.

Enough intro. To explain the monad laws, I'll start with another weird word: functor.

WTF - What The Functor?

Usually articles that start with words like "monad" and "functor" quickly devolve into soup of Greek letters. That's because both are abstract concepts in a branch of mathematics called category theory and explaining them completely is a mathematical exercise. Fortunately, my task isn't to explain them completely but just to cover them in Scala.

In Scala a functor is a class with a map method and a few simple properties. For a functor of type M[A], the map method takes a function from A to B and returns an M[B]. In other words, map converts an M[A] into an M[B] based on a function argument. It's important to think of map as performing a transformation and not necessarily having anything to do with loops. It might be implemented as a loop, but then again it might not.

Map's signature looks like this

class M[A] {
 def map[B](f: A => B):M[B] = ...
}

First Functor Law: Identity

Let's say I invent a function called identity like so

def identity[A](x:A) = x

This obviously has the property that for any x

identity(x) ≡ x

It doesn't do much and that's the point. It just returns its argument (of whatever type) with no change. So here's our first functor law: for any functor m

• F1. m map identity ≡ m // or equivalently *
• F1b. m map {x => identity(x)} ≡ m // or equivalently
• F1c. m map {x => x} ≡ m

In other words, doing nothing much should result in no change. Brilliant! However, I should remind you that the expression on the left can return a different object and that object may even have a different internal structure. Just so long as you can't tell them apart.

If you were to create a functor that didn't follow this law then the following wouldn't hold true. To see why that would be confusing, pretend m is a List.

F1d. for (x <- m) yield x ≡ m

Second Functor Law: Composition

The second functor law specifies the way several "maps" compose together.

F2. m map g map f ≡ m map {x => f(g(x))}

This just says that if you map with g and then map with f then it's exactly the same thing as mapping with the composition "f of g." This composition law allows a programmer to do things all at once or stretch them out into multiple statements. Based on this law, a programmer can always assume the following will work.

val result1 = m map (f compose g)
val temp = m map g
val result2 =  temp map f
assert result1 == result2

In "for" notation this law looks like the following eye bleeder

F2b. for (y<- (for (x <-m) yield g(x)) yield f(y) ≡ for (x <- m) yield f(g(x))

Functors and Monads, Alive, Alive Oh

As you may have guessed by now all monads are functors so they must follow the functor laws. In fact, the functor laws can be deduced from the monad laws. It's just that the functor laws are so simple that it's easier to get a handle on them and see why they should be true.

As a reminder, a Scala monad has both map and flatMap methods with the following signatures

class M[A] {
 def map[B](f: A => B):M[B] = ...
 def flatMap[B](f: A=> M[B]): M[B] = ...
}

Additionally, the laws I present here will be based on "unit." "unit" stands for a single argument constructor or factory with the following signature

def unit[A](x:A):M[A] = ...

"unit" shouldn't be taken as the literal name of a function or method unless you want it to be. Scala doesn't specify or use it but it's an important part of monads. Any function that satisfies this signature and behaves according to the monad laws will do. Normally it's handy to create a monad M as a case class or with a companion object with an appropriate apply(x:A):M[A] method so that the expression M(x) behaves as unit(x).

The Functor/Monad Connection Law: The Zeroth Law

In the very first installment of this series I introduced a relationship

FM1. m map f ≡ m flatMap {x => unit(f(x))}

This law doesn't do much for us alone, but it does create a connection between three concepts: unit, map, and flatMap.

This law can be expressed using "for" notation pretty nicely

FM1a. for (x <- m) yield f(x) ≡ for (x <- m; y <- unit(f(x))) yield y

Flatten Revisited

In the very first article I mentioned the concept of "flatten" or "join" as something that converts a monad of type M[M[A]] into M[A], but didn't describe it formally. In that article I said that flatMap is a map followed by a flatten.

FL1. m flatMap f ≡ flatten(m map f)

This leads to a very simple definition of flatten

1. flatten(m map identity) ≡ m flatMap identity // substitute identity for f
2. FL1a. flatten(m) ≡ m flatMap identity // by F1

So flattening m is the same as flatMapping m with the identity function. I won't use the flatten laws in this article as flatten isn't required by Scala but it's a nice concept to keep in your back pocket when flatMap seems too abstract.

The First Monad Law: Identity

The first and simplest of the monad laws is the monad identity law

• M1. m flatMap unit ≡ m // or equivalently
• M1a. m flatMap {x => unit(x)} ≡ m

Where the connector law connected 3 concepts, this law focuses on the relationship between 2 of them. One way of reading this law is that, in a sense, flatMap undoes whatever unit does. Again the reminder that the object that results on the left may actually be a bit different internally as long as it behaves the same as "m."

Using this and the connection law, we can derive the functor identity law

1. m flatMap {x => unit(x)} ≡ m // M1a
2. m flatMap {x => unit(identity(x))}≡ m // identity
3. F1b. m map {x => identity(x)} ≡ m // by FM1

The same derivation works in reverse, too. Expressed in "for" notation, the monad identity law is pretty straight forward

M1c. for (x <- m; y <- unit(x)) yield y ≡ m

The Second Monad Law: Unit

Monads have a sort of reverse to the monad identity law.

• M2. unit(x) flatMap f ≡ f(x) // or equivalently
• M2a. unit(x) flatMap {y => f(y)} ≡ f(x)

The law is basically saying that unit(x) must somehow preserve x in order to be able to figure out f(x) if f is handed to it. It's in precisely this sense that it's safe to say that any monad is a type of container (but that doesn't mean a monad is a collection!).

In "for" notation, the unit law becomes

M2b. for (y <- unit(x); result <- f(y)) yield result ≡ f(x)

This law has another implication for unit and how it relates to map

1. unit(x) map f ≡ unit(x) map f // no, really, it does!
2. unit(x) map f ≡ unit(x) flatMap {y => unit(f(y))} // by FM1
3. M2c. unit(x) map f ≡ unit(f(x)) // by M2a

In other words, if we create a monad instance from a single argument x and then map it using f we should get the same result as if we had created the monad instance from the result of applying f to x. In for notation

M2d. for (y <- unit(x)) yield f(y) ≡ unit(f(x))

The Third Monad Law: Composition

The composition law for monads is a rule for how a series of flatMaps work together.

• M3. m flatMap g flatMap f ≡ m flatMap {x => g(x) flatMap f} // or equivalently
• M3a. m flatMap {x => g(x)} flatMap {y => f(y)} ≡ m flatMap {x => g(x) flatMap {y => f(y) }}

It's the most complicated of all our laws and takes some time to appreciate. On the left side we start with a monad, m, flatMap it with g. Then that result is flatMapped with f. On the right side, we create an anonymous function that applies g to its argument and then flatMaps that result with f. Finally m is flatMapped with the anonymous function. Both have same result.

In "for" notation, the composition law will send you fleeing in terror, so I recommend skipping it

M3b. for (a <- m;b <- g(a);result <- f(b)) yield result ≡ for(a <- m; result <- for(b < g(a); temp <- f(b)) yield temp) yield result

From this law, we can derive the functor composition law. Which is to say breaking the monad composition law also breaks the (simpler) functor composition. The proof involves throwing several monad laws at the problem and it's not for the faint of heart

1. m map g map f ≡ m map g map f // I'm pretty sure
2. m map g map f ≡ m flatMap {x => unit(g(x))} flatMap {y => unit(f(y))} // by FM1, twice
3. m map g map f ≡ m flatMap {x => unit(g(x)) flatMap {y => unit(f(y))}} // by M3a
4. m map g map f ≡ m flatMap {x => unit(g(x)) map {y => f(y)}} // by FM1a
5. m map g map f ≡ m flatMap {x => unit(f(g(x))} // by M2c
6. F2. m map g map f ≡ m map {x => f(g(x))} // by FM1a

Total Loser Zeros

List has Nil (the empty list) and Option has None. Nil and None seem to have a certain similarity: they both represent a kind of emptiness. Formally they're called monadic zeros.

A monad may have many zeros. For instance, imagine an Option-like monad called Result. A Result can either be a Success(value) or a Failure(msg). The Failure constructor takes a string indicating why the failure occurred. Every different failure object is a different zero for Result.

A monad may have no zeros. While all collection monads will have zeros (empty collections) other kinds of monads may or may not depending on whether they have a concept of emptiness or failure that can follow the zero laws.

The First Zero Law: Identity

If mzero is a monadic zero then for any f it makes sense that

MZ1. mzero flatMap f ≡ mzero

Translated into Texan: if t'ain't nothin' to start with then t'ain't gonna be nothin' after neither.

This law allows us to derive another zero law

1. mzero map f ≡ mzero map f // identity
2. mzero map f ≡ mzero flatMap {x => unit(f(x)) // by FM1
3. MZ1b. mzero map f ≡ mzero // by MZ1

So taking a zero and mapping with any function also results in a zero. This law makes clear that a zero is different from, say, unit(null) or some other construction that may appear empty but isn't quite empty enough. To see why look at this

unit(null) map {x => "Nope, not empty enough to be a zero"} ≡ unit("Nope, not empty enough to be a zero")

The Second Zero Law: M to Zero in Nothing Flat

The reverse of the zero identity law looks like this

MZ2. m flatMap {x => mzero} ≡ mzero

Basically this says that replacing everything with nothing results in nothing which um...sure. This law just formalizes your intuition about how zeros "flatten."

The Third and Fourth Zero Laws: Plus

Monads that have zeros can also have something that works a bit like addition. For List, the "plus" equivalent is ":::" and for Option it's "orElse." Whatever it's called its signature will look this

class M[A] {
   ...
   def plus(other:M[B >: A]): M[B] = ...
}

Plus has the following two laws which should make sense: adding anything to a zero is that thing.

• MZ3. mzero plus m ≡ m
• MZ4. m plus mzero ≡ m

The plus laws don't say much about what "m plus n" is if neither is a monadic zero. That's left entirely up to you and will vary quite a bit depending on the monad. Typically, if concatenation makes sense for the monad then that's what plus will be. Otherwise, it will typically behave like an "or," returning the first non-zero value.

Filtering Revisited

In the previous installment I briefly mentioned that filter can be seen in purely monadic terms, and monadic zeros are just the trick to seeing how. As a reminder, a filterable monad looks like this

class M[A] {
   def map[B](f: A => B):M[B] = ...
   def flatMap[B](f: A=> M[B]): M[B] = ...
   def filter(p: A=> Boolean): M[A] = ...
}

The filter method is completely described in one simple law

FIL1. m filter p ≡ m flatMap {x => if(p(x)) unit(x) else mzero}

We create an anonymous function that takes x and either returns unit(x) or mzero depending on what the predicate says about x. This anonymous function is then used in a flatMap. Here are a couple of results from this

1. m filter {x => true} ≡ m filter {x => true} // identity
2. m filter {x => true} ≡ m flatMap {x => if (true) unit(x) else mzero} // by FIL1
3. m filter {x => true} ≡ m flatMap {x => unit(x)} // by definition of if
4. FIL1a. m filter {x => true} ≡ m // by M1

So filtering with a constant "true" results in the same object. Conversely

1. m filter {x => false} ≡ m filter {x => false} // identity
2. m filter {x => false} ≡ m flatMap {x => if (false) unit(x) else mzero} // by FIL1
3. m filter {x => false} ≡ m flatMap {x => mzero} // by definition of if
4. FIL1b. m filter {x => false} ≡ mzero // by MZ1

Filtering with a constant false results in a monadic zero.

Side Effects

Throughout this article I've implicitly assumed no side effects. Let's revisit our second functor law

m map g map f ≡ m map {x => (f(g(x)) }

If m is a List with several elements, then the order of the operations will be different between the left and right side. On the left, g will be called for every element and then f will be called for every element. On the right, calls to f and g will be interleaved. If f and g have side effects like doing IO or modifying the state of other variables then the system might behave differently if somebody "refactors" one expression into the other.

The moral of the story is this: avoid side effects when defining or using map, flatMap, and filter. Stick to foreach for side effects. Its very definition is a big warning sign that reordering things might cause different behavior.

Speaking of which, where are the foreach laws? Well, given that foreach returns no result, the only real rule I can express in this notation is

m foreach f ≡ ()

Which would imply that foreach does nothing. In a purely functional sense that's true, it converts m and f into a void result. But foreach is meant to be used for side effects - it's an imperative construct.

Conclusion for Part 3

Up until now, I've focused on Option and List to let your intuition get a feel for monads. With this article you've finally seen what really makes a monad a monad. It turns out that the monad laws say nothing about collections; they're more general than that. It's just that the monad laws happen to apply very well to collections.

In part 4 I'm going to present a full grown adult elephant er monad that has nothing collection-like about it and is only a container if seen in the right light.

Here's the obligatory Scala to Haskell cheet sheet showing the more important laws

	Scala	Haskell
FM1	m map f ≡ m flatMap {x => unit(f(x))}	fmap f m ≡ m >>= \x -> return (f x)
M1	m flatMap unit ≡ m	m >>= return ≡ m
M2	unit(x) flatMap f ≡ f(x)	(return x) >>= f ≡ f x
M3	m flatMap g flatMap f ≡ m flatMap {x => g(x) flatMap f}	(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
MZ1	mzero flatMap f ≡ mzero	mzero >>= f ≡ mzero
MZ2	m flatMap {x => mzero} ≡ mzero	m >>= (\x -> mzero) ≡ mzero
MZ3	mzero plus m ≡ m	mzero 'mplus' m ≡ m
MZ4	m plus mzero ≡ m	m 'mplus' mzero ≡ m
FIL1	m filter p ≡ m flatMap {x => if(p(x)) unit(x) else mzero}	mfilter p m ≡ m >>= (\x -> if p x then return x else mzero)

Monads are Elephants Part 2

In part 1, I introduced Scala's monads through the parable of the blind men and the elephant. Normally we're supposed to take the view that each blind man doesn't come close to understanding what an elephant is, but I presented the alternative view that if you heard all the blind men describe their experience then you'd quickly build a surprisingly good understanding of elephants.

In part 2 I'm going to poke at the beast some more by exploring Scala's monad related syntactic sugar: "for comprehensions."

A Little "For"

A very simple "for" looks like this

val ns = List(1, 2)
val qs = for (n <- ns) yield n * 2
assert (qs == List(2, 4))

The "for" can be read as "for [each] n [in] ns yield n * 2." It looks like a loop, but it's not. This is our old friend map in disguise.

val qs = ns map {n => n * 2}

The rule here is simple

for (x <- expr) yield resultExpr

Expands to¹

expr map {x => resultExpr}

And as a reminder, that's equivalent to

expr flatMap {x => unit(resultExpr)}

More "For"

One expression in a "for" isn't terribly interesting. Let's add some more

val ns = List(1, 2)
val os = List (4, 5)
val qs = for (n <- ns; o <- os)  
   yield n * o
assert (qs == List (1*4, 1*5, 2*4, 2*5))

This "for" could be read "for [each] n [in] ns [and each] o [in] os yield n * o. This form of "for" looks a bit like nested loops but it's just a bit of map and flatMap.

val qs = ns flatMap {n => 
   os map {o => n * o }}

It's worth while to spend a moment understanding why this works. Here's how it gets computed (red italics gets turned into bold green):

val qs = ns flatMap {n => 
   os map {o => n * o }}
val qs = ns flatMap {n => 
   List(n * 4, n * 5)}
val qs = 
   List(1 * 4, 1 * 5, 2 * 4, 2 * 5)

Now With More Expression

Let's kick it up a notch.

val qs = 
   for (n <- ns; o <- os; p <- ps)
      yield n * o * p

This "for" gets expanded into

val qs = ns flatMap {n => 
   os flatMap {o => 
      {ps map {p => n * o * p}}}}

That looks pretty similar to our previous "for." That's because the rule is recursive

for(x1 <- expr1;...x <- expr) 
   yield resultExpr

expands to

expr1 flatMap {x1 => 
   for(...;x <- expr) yield resultExpr
}

This rule gets applied repeatedly until only one expression remains at which point the map form of expansion is used. Here's how the compiler expands the "val qs = for..." statement (again red italics turns to bold green)

val qs = 
   for (n <- ns; o <- os; p <- ps)
   yield n * o * p
val qs = 
   ns flatMap {n => for(o <- os; p <- ps)
   yield n * o * p}
val qs = 
   ns flatMap {n => os flatMap {o => 
   for(p <- ps) yield n * o * p}}
val qs = 
   ns flatMap {n => os flatMap {o => 
   {ps map {p => n * o * p}}}

An Imperative "For"

"For" also has an imperative version for the cases where you're only calling a function for its side effects. In it you just drop the yield statement.

val ns = List(1, 2)
val os = List (4, 5)
for (n <- ns; o <- os)  println(n * o)

The expansion rule is much like the yield based version but foreach is used instead of flatMap or map.

ns foreach {n => os foreach {o => println(n * o) }}

Now, you don't have to implement foreach if you don't want to use the imperative form of "for", but foreach is trivial to implement since we already have map.

class M[A] {
   def map[B](f: A=> B) : M[B] = ...
   def flatMap[B](f: A => M[B]) : M[B] = ...
   def foreach[B](f: A=> B) : Unit = {
       map(f)
       ()
   }
}

In other words, foreach can just call map and throw away the results. That might not be the most runtime efficient way of doing things, though, so Scala allows you to define foreach your own way.

Filtering "For"

So far our monads have built on a few key concepts. These three methods - map, flatMap, and forEach - allow almost all of what "for" can do.

Scala's "for" statement has one more feature: "if" guards. As an example

val names = List("Abe", "Beth", "Bob", "Mary")
val bNames = for (bName <- names;
   if bName(0) == 'B'
) yield bName + " is a name starting with B"

assert(bNames == List(
   "Beth is a name starting with B", 
   "Bob is a name starting with B"))

"if" guards get mapped to a method called filter. Filter takes a predicate function (a function that takes on argument and returns true or false) and creates a new monad without the elements that don't match the predicate. The for statement above gets translated into something like the following.

val bNames = 
   (names filter { bName => bName(0) == 'B' })
   .map { bName => 
      bName + " is a name starting with B" 
   }

First the list is filtered for names that start with B. Then that filtered list is mapped using a function that appends " is a name..."

Not all monads can be filtered. Using the container analogy, filtering might remove all elements and some containers can't be empty. For such monads you don't need to create a filter method. Scala won't complain as long as you don't use an "if" guard in a "for" expression.

I'll have more to say about filter, how to define it in purely monadic terms, and what kinds of monads can't be filtered in the next installment

Conclusion for Part 2

"For" is a handy way to work with monads. Its syntax is particularly useful for working with Lists and other collections. But "for" is more general than that. It expands into map, flatMap, foreach, and filter. Of those, map and flatMap should be defined for any monad. The foreach method can be defined if you want the monad to be used imperatively and it's trivial to build. Filter can be defined for some monads but not for others.

"m map f" can be implemented as "m flatMap {x => unit(x)}. "m foreach f" can be implemented in terms of map, or in terms of flatMap "m flatMap {x => unit(f(x));()}. Even "m filter p" can be implemented using flatMap (I'll show how next time). flatMap really is the heart of the beast.

Remember, monads are elephants. The picture I've painted of monads so far emphasizes collections. In part 4, I'll present a monad that isn't a collection and only a container in an abstract way. But before part 4 can happen, part 3 needs to cover some properties that are true of all monads: the monadic laws.

In the mean time, here's a cheat sheet showing how Haskell's do and Scala's for are related.

Haskell	Scala
do var1<- expn1 var2 <- expn2 expn3	for {var1 <- expn1; var2 <- expn2; result <- expn3 } yield result
do var1 <- expn1 var2 <- expn2 return expn3	for {var1 <- expn1; var2 <- expn2; } yield expn3
do var1 <- expn1 >> expn2 return expn3	for {_ <- expn1; var1 <- expn2 } yield expn3

Footnotes

¹. The Scala spec actually specifies that "for" expands using pattern matching. Basically, the real spec expands the rules I present here to allow patterns on the left side of the <-. It would just muddy this article too much to delve too deeply into the subject.

Monads are Elephants Part 1

Introductions to monads are bit of cottage industry on the Internet. So I figured, "why buck tradition?" But this article will present Scala's way of dealing with monads.

An ancient parable goes that several blind men were experiencing their first elephant. "It's a tree," one said while wrapping his arms around its legs. "A large snake," another said while holding its trunk. A third said...um, something about a broom or a fan or whatever.

From this parable we can conclude this: the ancients believed that the visually impaired like to fondle large mammals. Fortunately we live in a more enlightened age.

We're also supposed to learn something about how our limitations can prevent us from grasping the whole picture and that we're all blind in some way. It's so Zen.

I think there's a third lesson to be learned - the opposite of the main intent: that it's possible to learn much about the big picture by getting a series of limited explanations. If you had never seen an elephant and people told you things like "it has legs as thick as tree trunks," "a nose like a snake," "a tail like a broom," "ears like fans," etc. then you'd soon have a pretty good understanding. Your conception wouldn't be perfect, but when you finally saw an elephant it would fit neatly into the mental picture you had slowly built up. Just as the elephant was about to step on you, you'd think "wow, the legs really are like trees."

Monads are Container Types

One of the most commonly used container types is List and we'll spend some time with it. I also mentioned Option in a previous article. As a reminder, an Option is always either Some(value) or None. It might not be clear how List and Option are related, but if you consider an Option as a stunted List that can only have 0 or 1 elements, it helps. Trees and Sets can also be monads. But remember that monads are elephants, so with some monads you may have to squint a bit to see them as containers.

Monads are parameterized. List is a useful concept, but you need to know what's in the List. A List of Strings (List[String]) is pretty different from a List of Ints (List[Int]). Obviously it can be useful to convert from one to the other. Which leads us to the next point.

Monads Support Higher Order Functions

A higher order function is a function that takes a function as a parameter or returns a function as a result. Monads are containers which have several higher order functions defined. Or, since we're talking about Scala, monads have several higher order methods.

One such method is map. If you know any functional languages then you're probably familiar with map in one form or another. The map method takes a function and applies it to each element in the container to return a new container. For instance

def double(x: Int) = 2 * x
val xs = List(1, 2, 3)
val doubles = xs map double
// or val doubles = xs map {2 * _}
assert(doubles == List(2, 4, 6))

Map does not change the kind of monad, but may change its parameterized type...

val one = Some(1)
val oneString = one map {_.toString}
assert(oneString == Some("1"))

Here the {_.toString} notation means that the toString method should be called on the element.

Monads are Combinable

Now let's say we have a configuration library that let's us fetch parameters. For any parameter we'll get back an Option[String] - in other words we may or may not get a string depending on whether the parameter is defined. Let's say we also have a function, stringToInt, which takes a String and returns Some[Int] if the string is parseable as an integer or None if it's not. If we try to combine them using map we run into trouble.

val opString : Option[String] = config fetchParam "MaxThreads"
def stringToInt(string:String) : Option[Int] = ...
val result = opString map stringToInt

Unfortunately, since we started with an Option and mapped its contained element with a function that results in another Option, the variable "result" is now an Option that contains an Option, ie result is an Option[Option[Int]]. That's probably not terribly useful in most cases.

To motivate a solution, imagine if instead of Option we'd used List and ended up with List[List[Int]]] - in other words a list containing some number of lists. Given that, we just need "flatten" - a function which takes a list of lists (List[List[A]]) and returns a single list (List[A]) by concatenating everything together.¹

A flatten function for Option[Option[A]] works a bit differently.

def flatten[A](outer:Option[Option[A]]) : Option[A] = 
   outer match {
     case None => None 
     case Some(inner) => inner 
   }

If the outer option is None, then result is None. Otherwise the result is the inner Option.

These two flatten functions have similar signatures: they take an M[M[A]] and turn it into an M[A]. But the way they do it is quite different. Other monads would have their own ways of doing flatten - possibly quite sophisticated ways. This possible sophistication is why explanations of monads will often use "join" instead of "flatten." "Join" neatly indicates that some aspect of the outer monad may be combined (joined) with some aspect of the inner monad. I'll stick with "flatten," though, because it fits with our container analogy.

Now, Scala does not require you to write flatten explicitly. But it does require that each monad have a method called flatMap.². What's flatMap? It's exactly what it sounds like: doing a map and then flattening the result.

class M[A] {
  private def flatten[B](x:M[M[B]]) : M[B] = ...
  def map[B](f: A => B) : M[B] = ...
  def flatMap[B](f: A => M[B]) : M[B] = flatten(map(f))
}

With that, we can revisit our problematic code...

val opString : Option[String] = config fetchParam "MaxThreads"
def stringToInt(string:String) : Option[Int] = ...
val result = opString flatMap stringToInt

Because of flatMap we end up with "result" being an Option[Int]. If we wanted, we could take result and flatMap it with a function from Int to Option[Foo]. And then we could faltMap that with a function from Foo to Option[Bar], etc.

If you're keeping score, many papers on monads use the word "bind" instead of "flatMap" and Haskell uses the ">>=" operator. It's all the same concept.

Monads Can Be Built In Different Ways

So we've seen how the flatMap method can be built using map. It's possible to go the other way: start with flatMap and create map based on it. In order to do so we need one more concept. In most papers on monads the concept is called "unit," in Haskell it's called "return." Scala is an object oriented language so the same concept might be called a single argument "constructor" or "factory." Basically, unit takes one value of type A and turns it into a monad of type M[A]. For List, unit(x) == List(x) and for Option, unit(x) == Some(x).

Scala does not require a separate "unit" function or method, and whether you write it or not is a matter of taste. In writing this version of map I'll explicitly write "unit" just to show how it fits into things.

class M[A](value: A) {
  private def unit[B] (value : B) = new M(value)
  def map[B](f: A => B) : M[B] = flatMap {x => unit(f(x))}
  def flatMap[B](f: A => M[B]) : M[B] = ...
}

In this version flatMap has to be built without reference to map or flatten - it will have to do both in one go. The interesting bit is map. It takes the function passed in (f) and turns it into a new function that is appropriate for flatMap. The new function looks like {x => unit(f(x))} meaning that first f is applied to x, then unit is applied to the result.

Conclusion for Part I

Scala monads must have map and flatMap methods. Map can be implemented via flatMap and a constructor or flatMap can be implemented via map and flatten.

flatMap is the heart of our elephantine beast. When you're new to monads, it may help to build at least the first version of a flatMap in terms of map and flatten. Map is usually pretty straight forward. Figuring out what makes sense for flatten is the hard part.

As you move into monads that aren't collections you may find that flatMap should be implemented first and map should be implemented based on it and unit.

In part 2 I'll cover Scala's syntactic sugar for monads. In part 3 I'll present the elephant's DNA: the monad laws. Finally, in part 4 I'll show a monad that's only barely a container. In the meantime, here's a cheat sheet for translating between computer science papers on monads, Haskell, and Scala.

Generic	Haskell	Scala
M	data M a or newtype M a or instance Monad (M a)	class M[A] or case class M[A] or trait M[A]
M a	M a	M[A]
unit v	return v	new M(v) or M(v)
map f m	fmap f m	m map f
bind f m	m >>= f or f =<< m	m flatMap f
join	join	flatten
	do	for

Footnotes

¹. The Scala standard library includes a flatten method on List. It's pretty slick, but to explain it I would have to go into implicit conversions which would be a significant distraction. The slick part is that flatten makes sense on List[List[A]] but not on List[A], yet Scala's flatten method is defined on all Lists while still being statically type checked.

². I'm using a bit of shorthand here. Scala doesn't "require" any particular method names to make a monad. You can call your methods "germufaBitz" or "frizzleMuck". However, if you stick with map and flatMap then you'll be able to use Scala's "for comprehensions"

Martians vs Monads: Null Considered Harmful

I hate null. More specifically I hate NullPointerExceptions(NPEs). Scala has an alternative, but let me explain why I hate NPEs. They're like evil, sneaky muppets. Remember the Martians on Sesame Street? They'd ask each other if a phone was a cow and then say "nope, nope, nope, nope." To my eye, NPE looks a lot like "NoPE."

Me: Is my unit test working?
Computer: NoPE
Me: Um...okay, fixed that problem...how 'bout now?
Computer: NoPE, NoPE, NoPE, NoPE
Me: ARGGHRHGR! You're a Sesame Street Martian!
Computer: Yip, yip, yip, yip¹

Does all this code/test/fix/Martians/yelling have to be part of the game? Can't a static typing system save me from this? Can't we stop the Muppets from chanting in my head?

The answer in Java and C# is "No! Well, sorta! Um, no." It is possible to implement a pattern whereby you should never get NoPEs. It's pretty painful to do and the "should" qualifier means it's not really worth it, but it does help illuminate a solution that's available in Scala.2

Some Craptacular Code

First, what's the big deal? Can't I just check for null and deal with it? Here's Java to demonstrate. Any resemblance to a C# code is purely coincidental.

public interface Spaceship {
  public Martian getMartian();
}

// the main method...
Spaceship spaceship = getSpaceshipSomehow();
Martian m = spaceship.getMartian()
if (m != null) {
  m.dieDieDie();
  System.out.println(m.toString() + 
    " is toast.");
} else
  System.out.println(
    "No Martians here!");
}  

The idea here is that some spaceships have Martians while others don't. If there is a Martian, that little bastard will never NoPE me again. Checking for null certainly works. But there's a problem - how do I know for certain that getMartian can return a null? If I didn't write Spaceship, what made me decide to do the null check? And how do I know that getSpaceshipSomehow() won't ever give me a null if I didn't wite it? The answer is I don't, that's how. It might be in the documentation or might not. The docs might be right or they might not. I might have access to the source code or I might not. I might remember what I wrote last week or I might not. The only answer would seem to be to wait for the NoPE to show up in testing or check for null defensively everywhere. Hmmm...stupid Martians.

Okay, let's try creating a holder that I'll call "Option" for reasons we'll see later. Once again, here's some Java (C#ers please consult your magic decoder rings).

public class Option<T> {
  private T value;

  public Option<T>(T value) {
    this.value = value;
  }
}

public interface Spaceship {
  public Option<Martian> getMartian();
}

// the main method...
Spaceship spaceship = getSpaceshipSomehow();
Option<Martian> o = spaceship.getMartian();
if (!o.value() == null) {
  Martian m = o.value();
  m.dieDieDie();
  System.out.println("I'm a 733T Martian h4x0r."
    + m.toString() + " has been pwned.");
} else
  System.out.println("W00T");
}

The idea is that API builders indicate nullibility by saying methods return an Option. getSpaceshipSomehow promises that it will return a Spaceship while getMartian may or may not return a Martian. It's okay as far as it goes, but it's entirely too easy to call o.value() without checking for null first. I'd like the type checker to help me here - maybe with subclasses. Here's the attempt in Java. The equivalent C# should be...um...equivalent.

public abstract class Option<T> {}
public class None<T> extends Option<T>{}
public class Some<T> extends Option<T>{
   private T value;

   public Some<T>(T value) {
     this.value = value;
   }
   public T value() {
     return value;
   }
}

public interface Spaceship {
  public Option<Martian> getMartian();
}

Spaceship spaceship = ...
Option<Martian> o = spaceship.getMartian();
if (o instanceof Some<Martian>) {
  Martian m = ((Some<Martian>)o).value();
  m.dieDieDie();
  System.out.println(m.toString() + 
    " has been laterally motivated.");
} else
  System.out.println("Thinking outside the " +
    "box leverages synergies.");
}

I've got an abstract base class, Option, that's really just a marker that a value might be "null" or not. None means "null", and Some means it's a real value. Code depending on this structure uses instanceof checks to determine which way to cast.

Unfortunately, this code has three holes and one major (huge) annoyance. The first hole is that the spaceship designer has to ensure getMartian always returns an Option and never a null. If that gets blown, we get NoPEd. The second hole is that there's no way in Java to prevent somebody else from creating a subclass of Option - and that would break the logic. The third hole is that I could just cast an Option to a Some without doing an instanceof check, turning a NoPE into an equally irritating ClassCastException . Finally, the major (huge) annoyance is that I have to write all that crappy code every time I deal with this construct. Frankly, I wouldn't blame you if you'd rather deal with NoPE.

Making it Optional in Scala

In Scala, equivalents to Option/Some/None already exist³ - but they're far, far easier to use and they're "sealed" so no logic breaking subclasses are allowed. Here's the last Java example translated into Scala

trait Spaceship {
  def getMartian: Option[Martian]
}

val spaceship = getSpaceshipSomehow
spaceship getMartian match {
  case Some(m) =gt; {
    m dieDieDie;
    println(m + " was terminated.")
  }
  case _ =gt; println("I'll be back.")
}

The Spaceship trait requires all spaceships to implement a getMartian method which may return Some[Martian] or Nothing. Once we have a spaceship we do a match to see if we got a Martian or not, and if we did then it's...retired.

The first thing you might notice is less annotation of types. Let me assure you that the code is just as statically typed as the Java version, it's just that the Scala compiler can figure out the types of "spaceship" and "m" just fine, thank you very much. You may also notice a lot fewer dots, parens, semicolons etc. Scala's syntax allows you to type all that line noise but generally only requires it when things get ambiguous. Finally, in Scala, square brackets work more or less like angle brackets in Java/C# for denoting "generics."

More importantly notice in the "Some" case how cleanly the Martian, m, is "pulled out". The code is easily as clear as the Java version that checked for null. But unlike the null checking Java code it's clear in this case that I have to do the check. If the check wasn't required the code wouldn't even compile. Unlike the Java versions of Option, the Scala version ensures that I've done my checking right.

Confessions of A Leaky Abstraction

Now a bit of a confession. You see, one of Scala's design goals is to interoperate with Java and .Net seamlessly. That's a great source of strength since the libraries for those platforms are huge, the underlying VMs are heavily optimized, and targeting those environments may be a way for Scala to sneak in through the back door of corporate America.

It's also a source of holes. In order to be truly seamless Scala has to have both null and casting. As a result, Scala's Option ends up with some of the same holes as we found in the Java subclassing code. If Scala had tried to plug the null and casting holes, the result would have been an impedance mismatch between Scala and the target VM environments.

Still, the Scala libraries use Option whenever a "null" could be used and Scala projects are following that pattern. As long as you never ever create a cast or a null, you'll only have to worry about NoPE when dealing with existing Java or .Net code. Which is to say, a lot <sigh>. So even though it's not the static guarantee that I want, Scala's Option is incredibly useful since it's just as easy to use as null and far more expressive ⁵

A Closing Note With Some Rabble Rousing

In Scala, Option is a class and that means it can have methods. One of those methods is a nifty shorthand for getting Some value is available or getting a default value if None. Imagine my Muppet bloodlust (stuffinglust) is so high that if the spaceship doesn't have a Martian, I'll create a new one just to kill it.

val m = spaceship.getMartian.getOrElse(new Martian)
m.dieDieDie

Due to another feature of Scala, optional laziness, a Martian is only constructed when needed. Think of it the way an expression might or might not be evaluated in Java/C# when you use logical or. For example, in Java/C# "m = a() || b()" the b() method won't be called if a() is true. Laziness just generalizes this concept.

Option can also be chained with other Option returning expressions using orElse. If I have 3 ships, s1, s2, s3 and I want to get the first available Martian (if any) then

val o=s1.getMartian.orElse(s2.getMartian.orElse(s3.getMartian))

Again, laziness ensures that we only keep looking for Martians until we find one.

Finally, in Scala, Option is a monad. I won't explain all about monads in this article, but I do want to show that Option brings far more power than what I've shown so far. Imagine that from a spaceship I want to get a Martian, get the Martian's ray gun, see who the ray gun's target is, and tell the target to duck. In other words, in Java/C# I want spacehip.getMartian().getRayGun().getTarget().duck(). A nice, easy, one liner. Cool, but now imagine the Martian, the ray gun, and the target are each optional and my rule is that if any of them are null then nobody needs to duck and for God's sake no NoPEs. Urk! In Java/C# you could chain together a bunch of logical ands

if (spacehips.getMartian() != null
  && spacehip.getMartian().getRayGun() != null
  && ...

Or you could pile up a series of ifs

RayGun r = null;
Target t = null;
Martian m = spacehip.getMartian();
if (m != null) {
  r = m.getRayGun();
}
if (r != null) {
  ...

Either way, it ain't pretty. Because Option is a Monad in Scala the code looks like this

for (
  m <- spaceship getMartian;
  r <- m getRayGun;
  t <- r getTarget
) t duck

It might not be clear just yet how the "for" keyword is doing this magic, but you have to admit the code is eminently readable. Far more readable than the Java/C# alternatives.

Hopefully this has convinced you that null really should be considered harmful. Just as it's become accepted that there are better alternatives to "goto" there really are better alternatives to "null."

So go spread the word! End the NoPE madness! Monads are the keys to defeating our Martian overlords!

Yip, yip, yip, yip.

Footnotes

¹. My apologies to Sesame Street. Realy, sorry, Muppets.

². There are several languages with the same solution including most notably Haskell. But don't be scared - I won't use the word "monad." Oops, I just did. Also I used it in the title and in the closing section. Oh, and in the next footnote.

³. In Haskell, the Option monad is called Maybe. ⁴

⁴. Monad. Just wanted to say "monad" again.

⁵. Haskell and OCaml don't have these holes since they have neither null nor casting.

The Kingdom of Nerbs

In his famous rant Execution in the Kingdom of Nouns, Steve Yegge hilariously excoriates Java for being so "noun oriented" that it's difficult to express ideas that are simple to express in functional programming languages. Scala is a language for the JVM that attempts to unify the funcional and object oriented worlds using first class functions, pattern matching, and what I'm going to call nerbs.

First, a short attention span theater version of Steve's post.¹

Once Upon A Time In The Land of JVM

Nouns(together): You there, verbs, get encapsulated at once!
Verbs: Oh please set us free.
Noun1 (implements an interface with only one verb): I am a verb. I am a functor!
Nouns(together): Hahahaha, what a clown.
Citizens of functional lands: Look how much power our verbs have.
Verbs: Free, free, set us free.²

So what was to be done for the poor denizens of the JVM?

To Make a Nerb

There are a bunch of language implementations that support functional programming on the JVM to one extent or another (Cal, Jaskell, Kawa, SISC, Jython, JRuby, Groovy, Rhino, ABCL, hey guys, 'sup?). Unfortunately, none of them are named Java.

For this post I'm going to pretend that Scala is the One True Answer(TM). Other answers will require their own fairy tales er blog entries. Scala is interesting because it not only supports "mere" first class functions, it also supports nerbs.

So what is a nerb?³ Good question, I'm so glad you asked. A nerb is a noun that has been verbed. If you don't believe me, go Google it. But before you do, realize that Google is a publicly traded corporation that makes oodles of cash from selling paid advertising using free web search as a loss leader. But in saying "Google it" I'm not referring to the noun that offers free donuts to its programmers, I'm referring to the verb that this noun is most well known for enabling. Hence the ever so slightly tautological definitions "Google: (verb) to search the web using a web search engine provided by Google - (noun) the company that lets you Google(verb)." ⁴

Before I continue, let me say that the word "nerb" does not from my close scrutiny seem to appear in any portion of the Scala language specification. But it should.

Back to my butchering of Steve's fairy tale. The verbs are clearly functions and the nouns are clearly objects.⁵ So a nerb would be an object that's been turned into a function. But in my version of the fairy tale, the verbs all laughed at the noun um object pretending to be a function. Why? Well, because while such beasts work they're just so, so, ... verbose and awkward. Here's one in Java:

public interface Transformer<P, R> {
  public R execute(P param)
}

public class NumberToFrenchStringTransformer 
    implements Transformer<Integer, String> {
  public String execute(Integer param) {
    switch (param.intValue()) {
      case 0: return "zero";
      case 1: return "un";
      case 2: return "deux";
      case 3: return "trois";
      default: throw new 
        RuntimeException("Je ne sais quoi");
    }
  }
}

public class Test {
  void countToThree(Transformer<Integer, String> 
      numberToStringTransformer) {
    for (int i=1;i<4;i++)
      System.out.println(
        numberToStringTransformer.execute(
          new Integer(i)));
  }
  
  public static void main(String[] args) {
    new Test().countToThree(
      new NumberToFrenchStringTransformer());
  }
}

Transformer is a generic interface that requires two types to fully specify: a parameter and a return type. The countToThree method requires a Transformer from Integer to String. The goal is that another Transformer could allow counToThree to speak in some other language, but this code only implements French. The main method hooks everything together.

For a toy example this may not seem so bad. But consider: every time you want to turn an existing function into an object you recreate a significant amount of boilerplate. Imagine writing a significant portion of a real application this way. I could have made it slightly more concise by using an anonymous class, but that would have been a minor change. Let's clean things up for the Scala interpreter.⁶

def numberToGermanString(n: Int) = n match {
  case 0 => "null"
  case 1 => "ein"
  case 2 => "zwei"
  case 3 => "drei"
  case _ => throw new RuntimeException(
    "Ich bin nicht ein Berliner")
}

def countToThree(
    numberToString: Int => String) =
  for (n <- List.range(1,4)) 
    println(numberToString(n))

countToThree(numberToGermanString)

The play by play: numberToGermanString is a function from integers to strings, countToThree just happens to require such a function, and the last line makes everybody go to town. It's concise and exactly to the point. In a lot of ways it's similar to any other language with first class functions. Again, I could have used an anonymous function but that would have been a minor change. Still we haven't created a nerb - at least not obviously. First class functions are more like gerunds - verbs turned into nouns.

To motivate the desire for a nerb, I ask you this: what else, when given an integer can return a string? Well, how 'bout an array of strings? I can hear you now, "yeah, but an array is a noun not a v.... hey...wait a minute..."

def countToThree(numberToString: Int => String) =
  for (n <- List.range(1,4))
    println(numberToString(n))
  
val words = 
  Array("none", "one", "a couple", "many")
  
countToThree(words)

Yup, in Scala an Array is a nerb. Clearly, an Array is a noun. But we didn't change countToThree a bit and it took the array - the array was verbed. Cool, eh? In scala, getting the 3rd element from the words array just do words(3).

So you might be thinking that arrays must get some special treatment, then, some special syntactic sugar all their own. Nope. You can sprinkle that sugar anywhere you want and turn any of your classes into nerbs.

How? Well, much like you would in Java but you use interfaces (well, traits) that Scala provides.

object NumberToSpanishStringTransformer() 
    extends Function1[Int, String] {
  def apply(n: Int) = n match {
    case 0 => "cero"
    case 1 => "uno"
    case 2 => "dos"
    case 3 => "tres"
    case _ => throw new 
      RuntimeException("Soy un sustantivo")
  }
}

def countToThree(
    numberToString: Int => String) =
  for (n <- List.range(1,4)) 
    println(numberToString(n))
  
countToThree(NumberToSpanishStringTransformer)

Obviously in this case it would be cleaner if I just used a function instead of creating a nerb. But the point here is that I CAN create a nerb - which is nice when I have a more complex class like Array. The "object" keyword means I'm creating a singleton. Function1 is an interface (trait in Scala terms) that is parameterized by two types. Think of it like a generic in Java or a template class in C++ but using square brackets instead of angle braces. The trait requires me to implement one method: apply. In other words, it's pretty much the same as the Java implementation above, except that I was able to treat my object as a function.

The Nerbs United Shall Never be Divided

Earlier I said of our first class function that we had not created a nerb "at least not obviously." Here's the punch line to my cryptic hint: whenever you use a function in a first class manner Scala implicitly creates a nerb. So this code

def numberToGermanString(n:Int) = ... 

def countToThree(numberToString: Int => String) =
  for (n <- List.range(1,4)) 
    println(numberToString(n))
  
countToThree(numberToGermanString)

translates into something along the lines of

def numberToGermanString(n: Int) = ... 

def countToThree(
    numberToString: Function1[Int, String]) =
  for (n <- List.range(1,4)) 
    println(numberToString.apply(n))
  
val $anonymousNerb = new Function1[Int, String]{
  def apply(n: Int) = numberToGermanString(n)
}

countToThree($anonymousNerb)

The byte code generated won't be exactly that but the the gist will be the same: underneath the hood Scala turns first class function creation into nerb creation. This might just seem like just an implementation detail, but it turns out that the Function1 trait provides additional methods for creating function compositions and those methods can be used anytime you create a first class unary function. It's also how Java code can interact with Scala first class functions.

The Grand Unification

In Scala, classes and objects can be turned into nerbs using the object oriented technique of inheritance. Functions and methods can be turned into gerunds using typical functional programming techniques but the gerunds turn out to be nerbs.

Nerbs are a key part to how Scala unifies the object oriented and functional paradigms. There's much more to the unification story including closures and pattern matching. I'll save those for another time.

Once Upon a Time in the Land of Scala

Unlike the land of Java the land of Scala was all peace and harmony. Verbs could be nouned and nouns could be verbed as needed. Together they held hands and sang the songs of nerbiness.

Footnotes

1. My apologies to Steve. Really, sorry dude.

2. My apologies to The Police. Really, sorry dudes.

3. Due credit - I stole the word "nerb" from Nancy Allison's "Every noun can be...".

4. To be madly self referential I would say the word "Google" has been nerbed.

5. Actually, the fairy tale draws the analogy of nouns being both objects and classes but Steve didn't make much distinction and I didn't either. I also won't make the distinction between functions and methods. Please just read on and pretend I know what I'm analogizing.

6. For compiled Scala we just need to wrap all the code in an object that extends Application. I know, I know, it's ironic after all my talk about setting verbs free, but please bear with me until I can talk about singletons.

You Might Be a Blub Neck

In Beating the Averages, Paul Graham formulated the Blub paradox. In short a programmer who only knows a language called Blub looks down on all languages that don't support features that Blub has. At the same time, he¹ is incapable of understanding why he would want to use some weird language that has features that Blub doesn't have. The Blub programmer is so used to thinking in Blub that he can't get his head around anything non-Blub.The question is, how do you know if you or somebody else is a Blub programmer? Of course it goes without saying that anybody who reads this blog is kind, highly intelligent, open minded, and motivated to learn.

The comedian Jeff Foxworthy had about five minutes of fame with a schtick of starting each joke with "you might be a redneck if..." Five minutes is a lot more fame than the average blog entry gets, so I thought I'd steal his formula for success.

Here, with a slight modification of the formula, I present

That Jerk on the Internet Might be a Blub Programmer If...

He dismisses other language features as "mere syntactic sugar"

Of course its syntactic sugar. Anything above raw machine code is syntactic sugar. Syntactic sugar is what helps programmers think and work at higher levels. Look at it this way: C and C++ have "goto" and "if". But they also have "while" which is really just syntactic sugar for the right combination of "goto" and "if." C, C++, C# and Java have "for", but it's just syntactic sugar for a certain kind of "while" loop. C++ has object oriented programming, but C++ type OO can be created in C using the right combination of structs and pointers.

In other language families I could go on and on about list comprehensions, pattern matching, type inference, regular expressions, function composition, currying, etc. But one in particular deserves mention: Lisp's most powerful feature is all about syntactic sugar. Lisp macro facilities (including quasiquotes, @ splices, etc) are syntactic sugar that make it easy for a programmer to create new syntactic sugar. If you understand macros then you'll think they're damned cool or damned scary (or both), but you won't dismiss them as "mere" anything. In On Lisp , Paul Graham creates an entire embedded Prolog in Common Lisp. Or take a look at Qi. It creates an incredibly powerful, statically typed, Haskell like language on top of the dynamically typed Common Lisp using a whole lot of macro black magic.²

He dismisses most examples as "toys" that don't show a feature is useful

Face it, most teaching examples are going to be a toys. Real world code is frequently complicated with error conditions, domain specific logic, and adherence to proprietary code standards. None of these things help demonstrate the feature being demonstrated, so examples tend to be small and focused on something that most people are familiar with or can learn in a few minutes. Refusing to try to grok a feature because the example given isn't immediately pertinent to you is a failure of one's imagination.

He questions why "anybody would want to do that in the real world"

The phrase "real world" is highly loaded. It depends entirely on the domains you have experience in. You might not see why C's unsafe casts and unions are useful but let me assure you that for extremely low level performance critical code they can be critical. Haskell's concept of monads might seem arbitrary and weird, but monads have been used to statically prove significant aspects of real programs. And Ruby's dynamic metaprogramming facilities really do help create an environment that is extremely productive in non-trivial systems.

He says his favorite language "can do that" and then creates a giant ball of crufty boilerplate to prove it

Most programming languages are Turing complete. All such languages can perform the same computations somehow. But if you have to create a ball of cruft every time you want to do some particular action, how often are you going to use that feature? If you had to recreate all of number theory every time you wanted to multiply two numbers wouldn't you stop tipping waiters?

Again Lisp is special here. Any feature in another language can be implemented in Lisp using a bit of macro cruft; the difference is that in Lisp the cruft only has to be created in one place. Besides that, macros can be surprisingly uncrufty - most look very much like the syntax they're trying to generate.³

He denies that another language is more powerful than his because "they are all Turing complete"

Hmmm, is he writing raw machine code? If not, he's implicitly admitting that some languages are more "powerful" for some sense of the word "powerful". Powerful is a surprisingly tricky concept to pin down, but because our Blub programmer has chosen Blub and not machine code he must have some definition beyond the computational theoretic meaning. Either that or he's splitting hairs about "powerful" vs "expressive" or some other term.

He dismisses language feature because the syntax isn't "intuitive"

If you think blocks must be denoted using curly braces then you're going to miss out on a very rich set of languages that use some other arbitrary choice. All programming languages are artificial creations and nothing about them is "intuitive" except in the narrow sense of "similar to something you already know." For example, most imperative languages use the single equal sign (=) to mean (re)assignment. It might seem "intuitive," but what's intuitive about using a symmetrical symbol for a fundamentally asymmetrical operation? Before programming languages stole it, that symbol already had a deep history and meaning in mathematics that is completely incompatible. Frankly, Scheme's "set!" and Smalltalk/Pascal's ":=" seem like more reasonable choices, and what could be more intuitive than "<-". But try getting any of them past the Blub lawyers.

This isn't to deny the utility of working on syntax when adding a feature to an existing language. The sense of "intuitive" given above definitely applies here. It's just to say that dismissing a feature in another language because it has a different syntax is pure parochialism.

Help Stamp Out Blub Programmers

This post has been unusually strident for this blog. I mostly intend to present my thoughts with more gentleness and good humor.In a sense, though, this entry is all about preventative medicine. In my future posts I intend to talk about several languages and features. In the process I expect to get many poorly thought-out comments from Blub programmers. It's my hope that this post will at least slow some of them down to think, "if I write this, will everybody think I'm that jerk on the Internet?"

It probably won't work, but that's never stopped me before.

Before I close this out, there are a few things that do not make you a Blub programmer:

You probably aren't a Blub programmer if...

You can admit ignorance

While ignorance is a key ingredient for Blubness, it's not the only ingredient. The Blub programmer is willfully ignorant, actively pushing back against anything new. But ignorance itself is just a temporary condition if its joined with an open mind.

You've tried something and just don't like it

Hey, not every feature is all the hype promises it to be. Not liking something that you have tried isn't the same as not liking something you never want to try. Just be open to the possibility that the feature might work well in some other environment, in another language, or with a better implementation.

Footnotes

1. The usual apologies about using "he" instead of "he or she." One Div Zero officially recognizes that women have full and equal rights to be jerks and Blub programmers.

2. Liskell does the opposite. It puts a Lisp like syntax, including macros, on top of Haskell.

3. One complaint that even thoughtful people have leveled against both Common Lisp and Scheme is that they seem more like Language Development Kits than languages. In part this impression is created by the fact that the standard definitions for both are getting a bit crusty with age. Sure, you can build a nice list comprehension macro but wouldn't it be nice if a standard one came in the box? The counter argument is that the language development kit allows you to move your environment into domains that are too specialized for a standard.