Sieve of Eratosthenes (the real one) Scala One-Liner

Here's a cute Sieve of Eratosthenes one liner (which I'm posting mostly so I won't loose it again):

(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))

It requires the forward pipe operator, such as the one provided by Scalaz or the one defined here.

Type Class pattern example

I was pleasantly suprised by the popularity of my last article, but some people expressed the wish to see a more practical example, outside Scala library. It is always difficult to use practical examples in blog articles, as they often require a lot of context to be properly understood and introduce a lot of unnecessary complexity.

So I'm going to compromise here. The example below discuss a common task in many systems, but which I'm going to present in a very simplistic manner. Specifically, how to format stuff for output.

There is much discussion about the proper place to handle output formatting. On one hand, for instance, we have the toString method available on every Java object. It is not uncommon to have serializer, toXML, or similar stuff either. On the other hand, such approach is not scalable and mixes business rules with presentation concerns, and architectures such as Model-View-Controller try to avoid it.

So let's try to solve this problem using the type class pattern. First, let's create or type class for a formatter which produces XML output (NodeSeq class), just as described in the last article. This time, there is one method we want this type class to have, though. Here it is:

import scala.xml.NodeSeq

abstract class FormatterXML[T] {
  def format(input: T): NodeSeq
}

To test it, we'll create a very simple method that takes this type class and use it to print stuff to the console.

def output[T](what: T)(implicit formatter: FormatterXML[T]) = println(formatter.format(what))

And, to finish the initial example, we'll create a simple class, good old Person, to test it. We'll put the implicit type class object inside the companion object of Person, so that it can be found automatically. Already, the class Person has become free of concerns about formatting, though companion object might be too close for some. This, however, is not necessary, as we'll see later.

In the code below, as in other examples later on, I'm declaring the case class and the companion object in the same line, so that it can be easily pasted on REPL (which won't recognize the companion object as a companion object otherwise). I added a test line too at the end.

case class Person(name: String, age: Int); object Person {
  implicit object Formatter extends FormatterXML[Person] {
    def format(input: Person): NodeSeq = <Person><Name>{input.name}</Name><Age>{input.age}</Age></Person>
  }
}

output(Person("John", 32))

So far, this can be trivially done in other ways, so we are gaining nothing. We'll gradually increase the complexity so that benefits of this approach start to show up. First, we'll create a Song class which has a Person member, so that we show off composition of the formatter.

case class Song(title: String, author: Person); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      <Author>{implicitly[FormatterXML[Person]].format(input.author)}</Author>
    </Song>
  }
}

output(Song("War Pigs", Person("Ozzy Osbourne", 61)))

Now, I'm sure all of you must be up in arms right now, because, as everyone knows, Ozzy Osbourne wasn't the sole author of War Pigs. We need to change the Song class to accomodate more authors, but that will make the formatter more complex. To help us here, let's create a formatter for generic lists, that we can use to simplify the Song formatter:

def ListFormatterXML[T](implicit formatter: FormatterXML[T]) = new FormatterXML[Traversable[T]] {
  def format(input: Traversable[T]): NodeSeq = <List>{input map formatter.format}</List>
}

Here we start to see an advantage to this approach. This method will work for any list (any traversable, in fact!), as long as there is a formatter for its members. Anyway, let's see the Song again:

case class Song(title: String, authors: Person*); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      <Authors>{ListFormatterXML[Person].format(input.authors)}</Authors>
    </Song>
  }
}

output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

This works, but having as the sole child of looks a bit weird. Let's do away with this:

def ListFormatterXML[T](kind: String)(implicit formatter: FormatterXML[T]) = new FormatterXML[Traversable[T]] {
  def format(input: Traversable[T]): NodeSeq = <List>{input map formatter.format}</List>.copy(label = kind)
}

case class Song(title: String, authors: Person*); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      {ListFormatterXML[Person]("Authors").format(input.authors)}
    </Song>
  }
}

output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

Personally, I like this better, but your milleage may vary. Anyway, let's increase complexity a bit. If we want scalability, we'd better make the formatter more flexible, able to handle many different formats. Let's redefine our type class, in a way that avoids changes to the code we have written so far:

abstract class Formatter[T, Format] {
  def format(input: T): Format
} 

abstract class FormatterXML[T] extends Formatter[T, NodeSeq] {
  def format(input: T): NodeSeq
}

We also need a new output, but here we have a problem. How do we specify the format type explicitly while, at the same time, inferring the input type? I'll confess not having given much thought to this problem, but the following code will work:

def as[F] = new {
  def output[T](what: T)(implicit formatter: Formatter[T, F]) = println(formatter.format(what))
}

With this new definition in place, we can recompile Person, Song and ListFormatterXML above, and try it out like this:

as[NodeSeq].output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

And, without changing any of that code, let's add a new output format to conclude this article:

implicit object PersonFormatterString extends Formatter[Person, String] {
  def format(input: Person): String = "%s, age %d" format (input.name, input.age)
}

def ListFormatterString[T](kind: String)(implicit formatter: Formatter[T, String]) = new Formatter[Traversable[T], String] {
  def format(input: Traversable[T]): String = input map formatter.format mkString (kind+" ", ", ", "; ")
}

implicit object SongFormatterString extends Formatter[Song, String] {
  def format(input: Song): String = input.title+" "+ListFormatterString[Person]("by").format(input.authors)
}

as[String].output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

Implicit tricks -- the Type Class pattern

Some people have been recently discovering the Scala equivalent of Haskell's Type Classes. I was a bit suprised because I thought everyone with enough Scala experience already knew about them, but, apparently, I was wrong.

A type class is basically a way to classify types based on the methods they offer. It offers an alternative to inheritance, in that you can group many different classes (types) that share a common set of methods, just like a superclass can be used to group its subclasses.

While Scala does not support type classes directly, the same patterns that hold true for Haskell can be simulated by using implicits in Scala. Perhaps a bit improperly, Scala programmers have been calling this pattern "type classes" as well.

It will feature proeminently in Scala 2.8, where examples can be found with Numeric, Ordering and even, I think, CanBuildFrom. In fact, one can find many questions on Stack Overflow related to Numeric being used precisely as a type class.

So, let me give a simple example of the kind of usage this can be put to. This is something someone just asked me on the #Scala channel on IRC, and I decided it makes for a nice example.

The problem put to me was restricting the options of a type parameter T without resorting to inheritance. For instance, if I want a method to work for Long and Int, but not any other type, there is no way to express that through a superclass. But the type class pattern can be used to solve it!

Here is the idea: I'll create an abstract class that will represent my type class. I'll then create elements representing the classes belonging to that type class. Finally, I'll use an implicit parameter to restrict my type parameter to that type class.

First, my abstract class:

abstract class Acceptable[T]

Yes, that's it. Not much to it, is there? Well, most often I would add to that class the methods I wish that type class to have. For instance, Numeric have all the normal operators you'd expect from classes that represent numbers. In this case, however, that won't be necessary, so I'm keeping it simple.

Next, let me create the members of my type class. I wish to create two of them: one for Int, and another for Long. To make them available without need for any import statements, I'll put them inside the companion class to Acceptable. Also, note that they are implicits.

object Acceptable {
  implicit object IntOk extends Acceptable[Int]
  implicit object LongOk extends Acceptable[Long]
}

Little to it, right? So, how do I get to use it? Well, let's create a simple method that will only accept Int and Long, as we wanted:

def f[T: Acceptable](t: T) = t

That weird declaration of T is called a context bound in Scala lingo. It's new to Scala 2.8, precisely to make this stuff easier. What it actually does is automatically define an implicit parameter -- and, for that very reason, it cannot be combined with other implicit parameters, though you can always use the full syntax to get the same result. Here's the full syntax:

def f[T](t: T)(implicit ev: Acceptable[T]) = t

So, does it work? Well, here is a small session using it:

scala> f(1)
res0: Int = 1

scala> f(1L)
res1: Long = 1

scala> f(1.0)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Double]
       f(1.0)
        ^

scala> f(1: Byte)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Byte]
       f(1: Byte)
        ^

Now, to those of you who may think this is neat but of little use, I'll point you to two examples of its usage in the new collections: the methods sum and max. If you try to call sum on a list of things that are not Numeric, it won't work -- at compile time. Likewise, if you try max on a list of things for which there are no Ordering available, it won't compile either. This way, these methods could be safely added to the collections without resorting to throwing exceptions at run-time!

This is just little window into what is possible -- enough to get a hang on the pattern without risking information overload. But look around, as there is much more to it!

String interpolation in Scala with Regex

Some new stuff I was waiting for has arrived on Scala. We can now have a limited form of string interpolation very easily:

def interpolate(text: String, vars: Map[String, String]) =
  """\$\{([^}]+)\}""".r.replaceAllIn(text, (_: scala.util.matching.Regex.Match) match { 
    case Regex.Groups(v) => vars.getOrElse(v, "") 
  })

Which can then be used like this:

scala> "The ${name} of the ${game}"
res0: java.lang.String = The ${name} of the ${game}

scala> Map("name" -> "X", "game" -> "Y")
res1: scala.collection.immutable.Map[java.lang.String,java.lang.String] = Map(name -> X, game -> Y)

scala> interpolate(res0, res1)
res2: String = The X of the Y

Why do I love APL?

I love the strangest languages for various reasons. Some of them have immense power, but can easily produce unmaintainable messes. Some have the elegant simplicity of zen, but never attracted the people who build kitchen sinks. Some are perfect matches for certain applications, and quickly degenerate for other usages.

In Scala I have found for the first time a positive combination of these attributes. Immense power, kitchen sinks, check. Simplicity? Perhaps not, but more so than the more popular alternatives. Some code has definitely a zen-like quality to it. And, yet, it is of general use, and has good enough resilience against unmaintainable messes. Not perfect, but better than anything else I know of, for now.

That doesn't mean I do not appreciate other languages. There is much to learn and admire in many, many languages, and I would not mind using quite a few of them if chance favors it.

So I'll leave you with the answer that came to my mind as I explained to a bewildered person why I loved APL -- a language I could spend a whole afternoon producing half a line of code:

There's joy to be found in writing code which is solely about what you want, and not about how to get there. Of expressing the fulness of your intent as a single expression. It's like the ultimate perfect katana cut.

Of course, in a real fight I'd rather have a gun.