Monads in Scala

Here's the beginning of a little tutorial on Monads in Scala. Michel Schinz provided encouragement and large parts of code, especially the trick to use bind and unit

In Informatics, there are two (related) meanings of the word "monad":

• A triple (T,eta,mu) following some laws in category theory
• A way of structuring functional programs

The first meaning can probably not be described easily in natural language. Michael Arbib and Ernest Manes' "Arrows, Structure, Functors - The Categorical Imperative". describe them as (generalized monoids) in Section 10.2 and through adjointness to the forgetful functor from algebras to sets. That last connection basically makes everything that we can write down or model using abstract syntax / universal algebra a monad.

In order to make sense of the "triple" jargon above, say T is a polymorphic type List (including the higher-order function map:(A->B)->(List[A]->List[B])). Then mu is nothing else but the well-known function flatten: List[List[A]] -> List[A], and eta:A -> List[A] is a constructor of singleton lists.

The second view is described in a dozen of Phil Wadler's papers and shall be considered from the Scala programmer's point of view. I mention category theory here because one should keep in mind that we can describe things that are not computations as monads. It also reminds us why a monad is a collection of things taken together. With the List example in mind, a potentially more revealing account on monads (aka triples) can be found in the free book Barr, Wells (2000) Toposes, Triples and Theories, p. 104.

Computation

In programming, the prime use of constructing a monad is to build objects which are computations. These computations are things that are waiting to be carried out. Presumably, the programmer has some interest in not carrying them out directly (for instance the computation to be done is not fully known at compile-time; check Gamma's Command design pattern).

In those paper mentioned before, a monad is always described as some type constructor M and two functions unit, bind with these types:

      def unit: a -> M[b]
      def bind: M[a] -> (a->M[b]) -> M[b]
    

(Where is the connection to the theory? Call M a functor T, unit a natural transformation eta, and call mu: M[M[a]] -> M[a] another natural transformation. The functor T lifts any function f:a-<b to a function Tf:T[A] -> T[B], so one can see that the mu is kind of hidden in the bind. bind is called a Kleisli extension, (M, unit, bind) a Kleisli triple. mu is also known as flatten or join. The ability of the functor T of lifting functions is often done by a function called map

To stay with the List example from above, take bind (x) (f) to be flatten(map(f)(x)). This explains the use of the name flatMap in Scala code. In the tutorial, we will continue to use bind to avoid confusion.

These functions must satisfy certain laws (Kleisli laws, also called monad laws):

           bind(unit(t),{b=>y}) == y[t/b]
          bind(m, {x => unit x} == m
  bind(m, {x=> bind(n, {y=> o}} == bind(bind(m, {x=>n}), {y=>o})    (if x ∉ fv(o))
  

Examples

(The monad examples will soon be in the examples/monads directory of the Scala distribution.)

Scala's for comprehensions

"do-notation" is a syntax to write monad based program fragments:

do
    x <- m1
    y <- m2
    return (x + y)

In Scala, this would look like this:

for(val x <- m1                     m1.flatMap { x =>            m1.flatMap { x =>
    val y <- m2)      ==becomes==>  m2.map     { y =>   i.e. =!= m1.flatMap { x =>
    yield {x + y}                          x+y }}                     unit (x+y) }}

If we take flatMap to be bind there you have convenient syntax for monad thingies. However that the =!= part has to hold, a consequence of the monad laws, is up to the programmer. We can use for-comprehension to help writing monadically structured programs, but they become monadically structured by the implementations of bind and unit, not by using for-comprehensions.

The Continuation Monad

The monad of continuations given here is a straightforward adaptation of Phil Wadler's paper "The Essence of Functional Programming" (1992). The other examples from that paper can be found in the src/examples directory of the Scala distribution.

I call instances of M "monadic artifacts", or just artifacts. They are values (hence Scala objects), which can be passed around and bound or decomposed.

object Main {

  //type Cont[A] = (A => Unit) => Unit;

  /** a class for "monadic artifacts" */
  case class M[+A](in: (A=>Any)=>Any) {
    def map[B](f: A => B)        = bind(this, {x: A => unit(f(x))});
    def flatMap[B](f: A => M[B]) = bind(this, f);
  }
  
  def unit[A](x:A) = 
    M(k:(A=>Any) => k(x));
    
  def bind[A,B](m:M[A], f:A=>M[B]):M[B] = 
    M(k => m.in (x => f(x).in(k)));

  def callCC[A](e:(A=>M[A])=>M[A]):M[A] =   
    M(k => e(a => M(ignored => k(a))).in(k));

    // Michel's Explanation:

    // The argument given to "e" must be a reified continuation, i.e.
    // a function which, when invoked with some parameter, replaces
    // the current continuation with the one of the call to callCC. In
    // the code above, "ignored" is the current continuation, and "k"
    // is the one of the call to callCC. Finally, "a" is the value
    // which will be "returned" by the call to callCC.

    // We also have to give a continuation to the whole callCC
    // expression, because it is perfectly possible that the reified
    // continuation is never invoked. This continuation is "k", quite
    // naturally. We therefore pass it to e's "input".
  
  // the "final continuation"
  def show[A]():(A)=>Unit = {x:A => Console.println(x)}

  // convenience
  def show[A](m:M[A]):Unit = { m.in (show()) }

  // convenience^2
  def showshow[A](m:M[M[A]]):Unit = { m.in (k => k.in (show())) }

  def reverse(s:String):String = {
    val sb = new StringBuffer();
    var i = s.length(); while(i > 0) {
      i = i - 1;
      sb.append(s.charAt(i));
    }
    sb.toString();
  }

  def main(args:Array[String]): Unit = {

    // example 1
    val p = unit[Int](3);              // computation that simply returns 3
    Console.println("example 1 (unit)");
    show(p);                                     // same as `p.in (show())'
    Console.println("---");


    // example 2a
    val m = unit[String]("42");                   // result of Deep Thought
    val f = {x:String => M(k:(String=>Any) => k("meaning of life:"+x))};
    val n = bind(m, f);
    Console.println("example 2a (bind)");
    show(n);                                     // same as `n.in (show())'
    Console.println("---");


    // example 2b (same as 2a, but with convenient syntax)
    val _n2 = for(val x <- unit("42");
		  val n <- M(k:(String=>Any) => k("meaning of life:"+x))) 
	      yield n;
    
    Console.println("example 2b (bind, nice syntax)");
    show(_n2);                                 // same as `_n2.in (show())'
    Console.println("---");


    // example 3
    val _r = for(val x <- n;
		 val m <- unit(reverse(x))) yield m;
    //           same as `val _r = bind(n, {x:String => unit(reverse(x))})'
    Console.println("example 3 (composition)");
    show(_r);      //same as `_r.in (show())'
    Console.println("---");


    // example 4
    def meaning(_x:M[String]=>M[M[String]]):M[M[String]] = {
      bind(unit(unit("42")), _x)
    }
        
    val someComputation = 
      meaning({x => unit(bind(x, {z:String => unit("the meaning of life is "+z)}))});

    Console.println("example 4 (why callCC matters)");
    showshow( someComputation ) ; //.in {k => k.in (show())};

    
    showshow( callCC(meaning) )                      // look Ma, no scheme!
  }
}