λ Tony’s blog λ

Here is how a continuation data type might look in Scala:

sealed trait Continuation[R, +A] {
  def apply(f: A => R): R
 
  import Continuation.continuation
 
  def map[B](k: A => B) = 
    continuation[R, B](z => apply(z compose k))
 
  def flatMap[B](k: A => Continuation[R, B]) = 
    continuation[R, B](z => apply(k(_)(z)))
}

Note that there are map and flatMap functions that satisfy the functor and monad laws. Continuation[R, _] is a monad.

Now let’s add some construction functions:

 
object Continuation {
  def continuation[R, A](g: (A => R) => R) = new Continuation[R, A] {
    def apply(f: A => R) = g(f)
  }
 
  def unit[R] = new {
    def apply[A](a: A) = continuation[R, A](f => f(a))
  }
 
  def callcc[R, A, B](f: (A => Continuation[R, B]) => Continuation[R, A]) =
    continuation[R, A](k => f(a => continuation(x => k(a)))(k))
}

The continuation function is a straight-forward construction. The unit function constructs a continuation is such a way as to satisfy the monad laws against the flatMap method. The callcc function (call with current continuation) is to allow “escaping” from the current continuation.

Here is some example client code that squares a number using a continuation (see squarec):

object Square {
  import Continuation._
 
  def square(n: Int) = n * n
 
  // Continuation for square
  def squarec[R](n: Int) = unit[R](square(n))
 
  // Continuation for effect (Unit) on square.
  // This is simply to help the type inferencer by applying a type argument.
  def squareE(n: Int) = squarec[Unit](n)
 
  def main(args: Array[String]) {
    val k = squareE(args(0).toInt)
    k(println)
  }
}

A slightly more complicated example for modelling exceptions. Let’s divide where the denominator must be 0 or an “exception” is thrown:

object Divide {
  import Continuation._
 
  // Division
  def div[R](c: String => Continuation[R, Int])
            (n: Int, // numerator
             d: Int) // denominator
                    : Continuation[R, Int] =
    callcc[R, Int, String](ok => 
      callcc[R, String, String](err =>
        if(d == 0) err("Denominator 0")
        else ok(n / d)
      ) flatMap c)
 
  def main(args: Array[String]) {
    def divError[R] = div[R](error(_)) _
    println(divError(7, 3)(x => x))
    println(divError(7, 0)(x => x)) // throws error
  }
}

I used to lecture at university. These days I teach for fun. Sometimes I am asked about controlling effects in a pure programming language such as Haskell by people who are very familiar with Scala’s flatMap method on List type, Option and so on (sadly, it is missing from the most fundamental of all — Function1). I often do this on a white-board and it has been reasonably successful at producing “aha! moments” so maybe it will help you.

Scala includes special syntax for using this method in the form of for-comprehensions. Specifically code like the following…

for(k <- e1;
    l <- e2(k);
    m <- e3;
    n <- e4(k, m)) 
  yield f(k, l, m, n)

…is translated into…

e1 flatMap (k => 
e2(k) flatMap (l => 
e3 flatMap (m => 
e4(k, m) map (n => 
f(k, l, m, n)))))

Notice the final call to map which is a specialisation of a call to flatMap by taking the unital for the type constructor under consideration. Gobbledy-gook? It’s simple really. Consider Lists:

x map f
// can also be written
x flatMap (z => List(f(z)))

That is because x => List(x) is the unit for List. For Option this function is the unit operation: x => Some(x). Try it next time you call map — use flatMap instead plus the unit operation for whatever type constructor you’re using (List, Option, whatever) — you’ll always get the same result. For Function1 the unit operation is x => y => x. I digress.

When I am asked about controlling side-effects I point to this flatMap business first so that I can assume familiarity (simple right?), then I switch to a completely different discussion about say, the following Java program snippet:

T t = e1();
e2(t);
U u = e3(t);
V v = e4(t, u);
return e5(u, v);

What I do with this snippet is invent a new programming that has very similar, but still different syntax to Java and I rewrite the program above. I do two things first

1. The syntax for assignment occurs in reverse
2. I remove type annotations (like T, U and V)

Here is how the program looks now:

e1() = t;
e2(t);
e3(t) = u;
e4(t, u) = v;
return e5(u, v);

Next I replace semi-colons (except the last one) with => and I rename return to unit:

e1() = t =>
e2(t) =>
e3(t) = u =>
e4(t, u) = v =>
unit e5(u, v)

Finally, I replace the equals sign with flatMap and I add a special case for the call to e2 which has no return value by calling flatMap but ignoring the parameter to the given function (denoted with an underscore):

e1() flatMap t =>
e2(t) flatMap _ =>
e3(t) flatMap u =>
e4(t, u) flatMap v =>
unit e5(u, v)

Since we know that the call to flatMap with unit can be replaced with a call to map let’s do that:

e1() flatMap t =>
e2(t) flatMap _ =>
e3(t) flatMap u =>
e4(t, u) map v =>
e5(u, v)

Wahlah! Have we just turned an imperative program into a pure one just by altering syntax!? Not really — rather, the distinction between imperative and pure is entirely dependent on the colour of your glasses. There is no hard-and-fast divide between one and the other (let that not detract from the huge implications of using one or the other). Importantly, we have seen that we can control side-effects with flatMap.

The flatMap method is at the very essence of a computational model called monads. Note that while we can control side-effects with monads, monads are not always about controlling side-effects! Indeed, when we call flatMap on Option or List we are using monads that have nothing to do with side-effects.

Haskell calls flatMap by a different name >>= and instead of for-comprehensions, Haskell has do-notation.

Pretty simple really isn’t it?

Scalaz is no longer on the workingmouse website but is hosted on Google Code at http://code.google.com/p/scalaz/.

If you say “Microsoft Windows = bad” you are almost certainly making a false claim within your own beliefs. Not because Windows is not bad necessarily and not because I might think it is good, but because Windows = bad is likely to give rise to an absurdity within your own beliefs should I interrogate you on the matter. There is a difference. Consider also “Hitler = bad”. If you think that “Windows = bad” and “Hitler = bad” then you also think “Windows = Hitler”. I will expect you don’t believe “Windows = Hitler”.

What you likely intend instead is “Windows ⇒ bad”. You could read this as “Windows implies bad”. Now you are free to believe the following three statements without giving rise to an inconsistency in your belief:

1. Windows ⇒ bad
2. Hitler ⇒ bad
3. Windows ≠ Hitler

Here is the truth table for implication:

P Q P⇒Q
0 0 1
0 1 1
1 0 0
1 1 1

Notice how ⇒ does not commute? Specifically, if you swap the propositions around you might get a different result. Bad ⇒ Windows is not the same as Windows ⇒ Bad — of course. This cannot be said for =. Bad = Windows is the same as Windows = bad.

You might wonder why I care so much. After all, if you said “Windows = bad” I’d know what you meant. But did you know what you meant and is this understanding universal each time you relax your discourse like this?

I have often observed a confusion between equivalence (also often called bi-implication) and implication in general discussion. Indeed, I hypothesise that this tendency to subvert a proposition in this manner is responsible for many failings in humanity’s general faculty of reason. I think we as a species would be better for it if we repair this failure of intellectual discipline (for what gain anyway?).

Therefore, I think that not only is this trivial correction important, but very much so. Thanks for listening.

Inspired by a very important point made by Jamis Buck.

If you use Windows then you have my sympathy but nothing more. However, if you are stupid enough to elect to use Windows then you don’t even have my sympathy.

This attitude — although somewhat stolen — is incredibly vital to maintaining my sanity. If I may replace Windows with other values maintaining the same sentiment:

• Java
• Maven (I’m looking at you my Functional Java users)
• Ruby
• Ruby on Rails
• Eclipse

The Scala API leaves a lot to be desired. I’m going to pick on a few methods that should appear, but do not, on scala.Function1.

They are:

• map
• flatMap
• <*> (the S combinator)
• on

Using some magic with the implicit keyword I can make it appear as if these methods did in fact exist:

sealed trait RichFunction1[-T, +R] {
  def apply(t: T): R
 
  import RichFunction1.rich
 
  def map[X](g: R => X) = rich[T, X](g compose (apply(_)))
 
  def flatMap[TT <: T, X](g: R => RichFunction1[TT, X]) =
    rich[TT, X](t => g(apply(t))(t))
 
  // The S combinator (SKI)
  def <*>[TT <: T, X](f: RichFunction1[TT, R => X]) = (t: TT) => f(t)(apply(t))
 
  // S again, swapped arguments
  def <*>:[TT <: T, X](f: RichFunction1[TT, R => X]) = <*>(f)
 
  // map with swapped arguments
  def <-:[X](g: R => X) = map(g)
 
  def on[K](f: (R, R) => K, t1: T, t2: T): K = f(apply(t1), apply(t2))
}
 
object RichFunction1 {
  implicit def rich[T, R](f: T => R) = new RichFunction1[T, R] {
    def apply(t: T) = f(t)
  }
}

By having flatMap (and therefore map) this allows you to remove a lot of duplication. This may come at the expense of syntactical noise per Scala, but not always. Suppose you were given a String and you wanted to check if it was equal to one of a few Strings (ignoring case). You could use some trickery with existing methods on List, but I want to keep this example simple, so let us ignore that possibility for now (and accept that I could come up with a sufficient example that such trickery is insufficient).

  // For example, suppose this predicate function
  def predicate(s1: String) = s1 equalsIgnoreCase (_: String)

Here is the repetition

  // predicate(s, _) repeats
  def f(s: String) = predicate("x")(s) || predicate("y")(s) || predicate("z")(s)

But if we have flatMap and map we can use a for-comprehension:

  // Taking advantage of flatMap/map
  val g = for(a <- predicate("x");
              b <- predicate("y");
              c <- predicate("z"))
          yield a || b || c

Here is how that same code looks when expanded:

  // Expansion of g
  val h = predicate("x") flatMap (a =>
          predicate("y") flatMap (b =>
          predicate("z") map ((c =>
            a || b || c))))

How about some fancy stuff with the S combinator (<*>):

  val or = Function.curried((_: Boolean) || (_: Boolean) || (_: Boolean))
 
  // Using the S combinator
  val i = predicate("z") <*>
          (predicate("y") <*>
          (predicate("x") map
          or))

Or with the arguments swapped around:

  // Using S with swapped arguments
  val j = ((or <-: predicate("x")) <*>: predicate("y")) <*>: predicate("z")

Pretty neat eh?

Suppose you wanted to check if the length of one List was less than the length of another. You might be tempted to write x.length < y.length. Notice how _.length repeats? Again I want to keep this example simple so while the solution below is more noisy, there are cases where it is not.

Scala is let down a little by first-class function semantics. We’ll begin with assuming this first-class function value:

  val length = (_: List[Int]).length

Then comparing using length:

  val k = length on (_ < _, List(4, 5, 6, 7), List(1, 2, 3))

A bit noisier but the repetition is gone. It’s a shame that abstraction comes at a syntactic cost and in some cases it may even be worth that cost. I wish I had the choice.

I work from home now. It rocks I also live in a rental property in the warm climate of Brisbane, Australia.

I wish to convert one of the rooms — westward-facing, 3 metres by 3 metres — into my office. I currently work in the main living area under a split system A/C and this has some problems that I want to alleviate.

Below is an image of the only window in this room. It has a single slider 570mm by 1450mm (the pink line) which is fitted with a security screen by pop-rivets. This window faces west and there is drainage outside.

What is an appropriate set up for cooling such a room, given that it is a rental property? I have looked at evaporative coolers and portable air conditioners but have been advised against both given our climate. It also appears somewhat difficult to use a portable A/C given the fixed security screen and the need for an external vent — can it me reversibly modified somehow? I find no other appropriate option and am a bit of a deadlock. Advice?