Friday, October 30, 2009

99 Beers!

I was perusing Lau Jensen's excellent Best In Class blog. Now, Lau Jensen is a Clojure-person, and that's one of the best languages out there in my opinion. So, when he compares it to other languages, that's never a nice experience to those being compared.

Personally, I think OO and infix methods (dot-style or operator notation) are essential for a well-rounded, popular language, which makes something of an uncrossable chasm between Clojure and me for "serious" stuff.

At any rate, his recent second take at Python got me curious about the Rosetta Code project. First, I got curious about his discussion of the Counting Programming Example problem, and the Python and Clojure implementations shown. I took my own shot at it, going the parallel way like the Clojure version, but I'm unsatisfied with the result. Sure, it is short, but it lacks... sense of cohesion, I guess. In fact, I just changed it from what I submitted to Rosetta. Here:

import java.net.{URL, URLEncoder}

val URLs = Map(
'allTasks -> "http://www.rosettacode.org/w/api.php?action=query&list=categorymembers&cmtitle=Category:Programming_Tasks&cmlimit=500&format=xml",
'oneTask -> "http://www.rosettacode.org/w/index.php?title=%s&action=raw"
)
def oneTaskURL(title: String) = URLs('oneTask) format URLEncoder.encode(title.replace(' ', '_'), "UTF-8")

def getPage(url: String) = scala.io.Source.fromURL(new URL(url))(scala.io.Codec.UTF8)

val pattern = "(?i)==\\{\\{header\\|".r
def countPattern(title: String) =
pattern findAllIn (getPage(oneTaskURL(title)) mkString) length

val allTasks = scala.xml.parsing.XhtmlParser(getPage(URLs('allTasks)))
val counts =
for (task <- allTasks \\ "cm" \\ "@title" map (_.text))
yield actors.Futures.future((task, countPattern(task)))

counts map (_.apply) map Function.tupled("%s: %d examples." format (_, _)) foreach println
println("\nTotal: %d examples." format (counts map (_.apply._2) sum))

I won't bother explaining it, because I think it is self-explanatory, if a bit arcane. Scala's partial XPath support is put to good use, and future just works here. In case you aren't familiar with Future, it just detaches a thread to handle some computation you passed, and then, when you call "apply", it joins that thread and get the result. Sort of. If anyone wants to take a go at making this better, I'd like to see the results.

At any rate, while perusing the Rosetta site, I noticed that 99 Bottles of Beer problem allowed for creativity in reaching a solution. Most examples went for conciseness. My own concise Scala looks like this:

99 to 1 by -1 foreach {n =>
println("""|%d bottles of beer on the wall
|%d bottles of beer
|Take one down, pass it around
|%d bottles of beer on the wall\n""".stripMargin format (n, n, n -1))}

However, as I thought about the problem and how to make it interesting, I decided to model it with Actors. Sure, it is an absolute overkill for this problem, but I think the modelling itself shows off Actors pretty nice.

Here it is:

object Song {
import scala.actors._
import scala.actors.Actor._

abstract class Beverage { def name = this.toString.toLowerCase }
case object Beer extends Beverage

object Wall {
private var contents: List[Beverage] = Nil

def count(what: Beverage) = contents count (_ == what)
def isEmpty = contents isEmpty
def stock(n: Int, what: Beverage) = contents :::= List.fill(n)(what)
def get(what: Beverage) {
def takeOneFrom(contents: List[Beverage]): List[Beverage] = contents match {
case `what` :: rest => rest
case other :: rest => other :: takeOneFrom(rest)
case Nil => println("Sorry, we are out of "+what.name); Nil
}
contents = takeOneFrom(contents)
}
}

sealed abstract class Messages
case class SingSong(what: Beverage) extends Messages
case class HowManyMore(what: Beverage) extends Messages
case class HowManyNow(what: Beverage) extends Messages
case class ThereAreStill(n: Int, what: Beverage) extends Messages
case class ThereAreNow(n: Int, what: Beverage) extends Messages
case class Gimme(what: Beverage) extends Messages
case class HereIs(what: Beverage) extends Messages
case object ClosingTime extends Messages

def plural(count: Int, noun: String, nouns: String) = if (count == 1) noun else nouns
def countIt(n: Int, what: Beverage) = "%d %s of %s" format (n, plural(n, "bottle", "bottles"), what.name)

object Waitress extends Actor {
def tellThem(what: String) = println("%s on the wall" format what)
def act = loop {
react {
case HowManyMore(it) =>
val total = Wall count it
tellThem(countIt(total, it))
reply (ThereAreStill(total, it))
case Gimme(it) =>
print("Take one down, ")
Wall get it
reply (HereIs(it))
case HowManyNow(it) =>
val total = Wall count it
tellThem(countIt(total, it))
if (Wall isEmpty) {
reply (ClosingTime) // You don't have to go home, but you can't stay here
exit
} else
reply (ThereAreNow(total, it))
case _ =>
println("You wish, honey!")
}
}
}

object Patrons extends Actor {
def act = loop {
react {
case SingSong(what: Beverage) =>
Waitress ! HowManyMore(what)
case ThereAreStill(n, it) =>
println(countIt(n, it))
Waitress ! Gimme(it)
case HereIs(it) =>
println("pass it around")
Waitress ! HowManyNow(it)
case ThereAreNow(n, it) =>
println()
Waitress ! HowManyMore(it)
case ClosingTime =>
exit
case _ =>
println("Say what???")
}
}
}

def Sing99Beers = {
Wall stock (99, Beer)
Waitress.start
Patrons.start

Patrons ! SingSong(Beer)
}
}

Now, this code has a structure to it. To begin with, there are two concerns. First, there is the "wall", where the beverages are kept, and the beverages themselves. The beverages are modeled as case objects derived from a sealed class, which is an alternative to enumerations, as I have discussed in my Matrix series.

I suppose the wall ought to be synchronized, but I'm working with an assumption here. Only one agent can get things from the wall, and the wall can only be restocked while that agent is not working. It would be nice to have this enforced by the compiler, and a paper from the EPFL guys gives me hope of being able to in the future.

The second concern is the interaction between the patrons and the waitress. Again, it is further divided into two: the messages they exchange between themselves, and the actors themselves and their behavior.

Defining the messages as a subclass from an abstract class doesn't really give me anything. The Actors in the standard library are untyped, so they can receive anything as message. There is one typed Actor library for Scala, though, which is a model much more to my liking. If used, I'd not have to provide for handling of unknown messages.

The song gets sang as the patrons ask how many beers there are, the waitress answers, the patrons order one beer, get it, and then ask again how many beers there are. No actor ever waits for the answer. Instead, they finish their present reaction, and wait for another message -- which might be the answer they were waiting for, or not. What the actor do is solely defined by what message they received.

To get the song started, the wall is first stocked, patrons and waitress started, and, then, the patrons are asked to begin the song. I'm pretty sure bar owners everywhere hope it would be this easy to get people drinking until the stock is sold-out. :-)

I hope you enjoyed this post half as much as I enjoyed writing that code! If you are feeling the need to write some code right now, try modifying the program so that, when the stock of whatever is being consumed is finished, the patrons ask what else there is, and start a new song on a new beverage.

Or, better yet, why don't you find a fun problem on Rosetta Code, for which no solution exists in a language you like, and submit a solution to it? It's as easy as editting a wiki article, so go for it!

Wednesday, October 28, 2009

Strict Ranges?

Note: This article was created before Scala 2.8.0 was out, and is mostly related to a problem that is no longer present as of that version. The code in here is supposed to be run on Scala 2.7.x unless otherwise noted, and the output of Scala 2.8.0 usually refers to some work-in-progress version of it, not the final version.

A common mistake newcomers to Scala usually make is to treat Scala ranges as strict. It's easy to see why they make such mistake, because the very expression "strict", though relatively easy to find in the Scala API documentation, is unfamiliar to them.

So, before getting into the problem, I'll make a brief detour. In functional languages, there is a concept of "strict functions" and "non-strict functions". Informally, a "strict function" is one which always evaluates its argument. For programmers from a non-functional background, that's most of the functions they ever saw, but not all. For instance, the trinary operator, "test ? f1 : f2", does not evaluate all its arguments, f1 and f2, even though it always evaluate at least one of them.

Now, to see where that can lead to trouble, let's first see an example of non-strictness in action, with Scala 2.7:

scala> object X {
| val x = -10 to 10 map (2 / _)
| }
defined module X

scala> object Y {
| val y = List.range(-10, 10) map (2 / _)
| }
defined module Y

scala> Y.y(0)
java.lang.ArithmeticException: / by zero
at Y$$anonfun$1.apply(<console>:5)
at Y$$anonfun$1.apply(<console>:5)
at scala.List.map(List.scala:812)
at Y$.<init>(<console>:5)
at Y$.<clinit>(<console>)
at .<init>(<console>:6)
at .<clinit>(<console>)
at RequestResult$.<init>(<console>:3)
at RequestResult$.<clinit>(<console>)
at RequestResult$result(<console>)
at sun.reflect.Nativ...
scala> X.x(0)
res2: Int = 0

We see an error happens when the map on the list is applied, but not when the map on the range is applied. That's because the function "map" for Range (the result of "x to y" or "x until y" expressions) is non-strict. I can get the value for any part of that Range, except the eleventh element, without throwing an exception.

But let say we have a function expensiveComputation, which takes quite a while to process. What happens, then, if I do this:

scala> import scala.actors.Futures._
import scala.actors.Futures._

scala> val m = 1 to 1000 map (i => future(expensiveComputation(i)))
m: RandomAccessSeq.Projection[scala.actors.Future[Int]] = RangeM(<function>, <function>, <function>,
<function>, <function>, <function>, <function>, <function>, <function>, <function>, <function>, <fu
nction>, <function>, <function>, <function>, <function>, <function>, <function>, <function>, <functi
on>, <function>, <function>, <function>, <function>, <function>, <function>, <function>...

If you haven't seen it before, the "future" function uses threads to compute the function you passed to it. Your program can go on to do other stuff, while all that work is being done concurrently.

Except, of course, that's not what's happening. No computation is being done, because Range's non-strict map hasn't evaluated its arguments. In fact, each time I call "apply" to get the result of the computation, the function I passed to map (the future) will be computed again! For example:

scala> def expensiveComputation(n: Int) = {
|   println("Starting expensive computation")
|   val x = n * 2
|   println("Finished expensive computation")
|   x
| }
expensiveComputation: (Int)Int

scala> val m = 1 to 10 map (i => future(expensiveComputation(i)))
(output from "m.toString" skipped)

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res12: Int = 2

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res13: Int = 2

To see where that can be a problem to beginners, take a look at the code in this question at Stack Overflow:

def ttest() = {
val threads =
for (i <- 1 to 5)
yield new Thread() {
override def run() {
println("going to sleep")
Thread.sleep(1000)
println("awake now")
}
}

threads.foreach(t => t.start())
threads.foreach(t => t.join())
println("all done")
}

Can you imagine what happens?

Well, gladly, Scala 2.8 should have a strict Range, so newcomers will be spared the trouble and lost debugging time. Here's what this will look like with Scala 2.8:

scala> val m = 1 to 10 map (i => future(expensiveComputation(i)))
Starting expensive computation
Finished expensive computation
Starting expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
m: scala.collection.immutable.Vector[scala.actors.Future[Int]] = NewVectorImpl(<function0>, <function0>, <function0>, <f
unction0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>)
Finished expensive computation
Starting expensive computation
Finished expensive computation

scala> Finished expensive computation


scala> m(0).apply
res11: Int = 2

scala> m(0).apply
res12: Int = 2

Also, if you try out the first code snippet on Scala 2.8, "x.x(0)" will also throw an exception. Now, if we want the previous behavior, we can just call the "view" method. It will work not only on Range, but on pretty much all standard collections, as it is defined on the class IterableLike.

scala> val m = (1 to 10 view) map (i => future(expensiveComputation(i)))
m: scala.collection.SeqView[scala.actors.Future[Int],Seq[_]] = SeqViewM(...)

scala> m.toList
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Starting expensive computation
Starting expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Finished expensive computation
Finished expensive computation
Finished expensive computation
Starting expensive computation
Starting expensive computation
Finished expensive computation
res5: List[scala.actors.Future[Int]] = List(, , , , , 
, , , , )
Finished expensive computation

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res6: Int = 2

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res7: Int = 2

And, for the first example:

scala> object X {
| val x = (-10 to 10 view) map (2 / _)
| }
defined module X

scala> object Y {
| val y = List.range(-10, 10).view map (2 / _)
| }
defined module Y

scala> Y.y(0)
res0: Int = 0

scala> X.x(0)
res1: Int = 0

And, speaking of Scala 2.8 changes, there is one that is also likely to reduce confusion among newcomers, and is related to what we spoke of. It's related to how guards on for-comprehensions work. For instance, take a look at this code:

scala> def find(n: Int, l: List[Int]) = {
| var found = false
| for (el <- l; if !found) found = el == n
| found
| }
find: (Int,List[Int])Boolean

scala> find(5, List.range(1, 10))
res14: Boolean = false

This code doesn't work as expected because of how for-comprehensions are translated:

l.filter(el => !found).foreach(el => found = el == n)

Since "filter" for List is a strict method, this just doesn't work, as "filter" evaluates before "foreach". However, Range's "filter" on Scala 2.7 is non-strict. Does it work? Yes:

scala> def findR(n: Int, l: Range) = {
| var found = false
| for (el <- l; if !found) found = el == n
| found
| }
findR: (Int,Range)Boolean

scala> findR(5, 1 to 10)
res17: Boolean = true

But, back to the first example, as of Scala 2.8 the for-comprehension code will translate like this:

l.withFilter(el => !found).foreach(el => found = el == n)

This new function, "withFilter", will be non-strict for standard Scala collections. There's no way, however, to ensure that third-party collections will preserve the non-strictness. Hopefully, people will act in a sensible manner! :-) At any rate, the "find" function, as written, will work on Scala 2.8.

I hope this helps people working with Scala 2.7, and hope even more for Scala 2.8 to arrive soon! As a parting thought, though, I'd like to briefly speak of "<-", seen in for-comprehensions. I have seen people calling it many things. Martin Odersky's (et al) Programming in Scala book, however, calls it "in". So "for (el <- l)" ought to read "for el in l". So, if you weren't sure what to call it, now you know! Happy coding!



Tuesday, September 29, 2009

Scala's Delimited Continuations -- A Use Case

When I first talked about the upcoming Scala 2.8 Delimited Continuations, I did not go into what uses I foresaw for them, mostly because I was pretty sure people would find uses I could never have imagined for it.

Well, people did find uses I could never have imagined, it turns out! If Scala and Distributed Computing are your things -- hell, if even one of them is your thing! -- do go check Swarm out.

Thursday, September 17, 2009

Is rewritting really bad?

Paul Chiusano tell us his Scala success story, and while I find it interesting, there's something that attracts my attention in it. He says:
Finally, I'd like to scrutinize the folk wisdom that rewrites are generally a bad idea.
That got me thinking a bit. That wisdom predates some developments which only became widespread practices recently. In particular, BDD and Continuous Integration.

It occurs to me that if I decide to rewrite something from scratch, I'll have a large set of tests in the form of BDD (which tests for Behavior, so a lot of it should still apply), plus the tests for all bugs that were caught and fixed, for which you them add tests to help with CI.

Furthermore, because you are doing BDD and CI, and possibly TDD for low level stuff, you won't get far with the same errors in case you re-introduce them.

That's something to think about... maybe the old wisdom requires some revisiting.

At any rate, I'd like to point out that this particular piece of wisdom might have become widespread because of this article by Joel Spolsky. I'll quote one part of it, though:
These problems can be solved, one at a time, by carefully moving code, refactoring, changing interfaces. They can be done by one programmer working carefully and checking in his changes all at once, so that nobody else is disrupted. Even fairly major architectural changes can be done without throwing away the code.
Well, that's precisely what Paul Chiusano did! So, on the other hand, perhaps is too soon to dispose of that wisdom...


Wednesday, September 9, 2009

Type Safe Builder Pattern

I was reading these days an interesting article by Jim McBeath about type safe builder patterns. The interesting part was the use of Church encoding to be able to control the ordinality of certain types, but as I went to the original article by Rafael de F. Ferreira, I found the silliest criticism, which I quote below:

My but it's sad that Java/Scala has to resort to a design pattern for this (if I'm understanding the post correctly).

In Python, we have keyword arguments and default argument values, which allows for very rich parameter declarations.

Well, first of all, a builder pattern is targetted at complex objects. Imagine, for instance, a maze with multiple rooms and passages, where the creation process might entail adding hundred of such components. Not exactly the sort of thing you want to pass as a single parameter list, I'd imagine. In fact, it might not even be possible to do it, because you might not have all information needed in the same place and/or time.

But, most importantly, "keyword arguments" do not enforce type safety. So even if it were an alternative to any problem requiring the Builder pattern, it would fail at the basic premise of the article, which is providing type safety.

So, I decided to show something you can't do with keyword arguments, which, by the way, are called "named parameters" in Scala 2.8, which is mutual exclusion. I'm adapting this example from here, which was written in reply to a follow up by Jim on his original article.

For this example, I assume a "Car" builder, where one has to make a choice about number of doors and brand, and may also choose to get a convertible, but the convertible is incompatible with cars with five doors. This code is nowhere as clear as Jim's, but gets the job done faster, so I could get on with my life. :-)

So, I hope you like it. And if you can clean it up, or come up with more likely scenarios, please share it.



// This code is based on an idea of Rafael de F. Ferreira and was implemented as a response to
// Jim McBeath's blog post http://jim-mcbeath.blogspot.com/2009/09/type-safe-builder-in-scala-part-2.html
// Everyone is free to use, modify, republish, sell or give away this work without prior consent from anybody.

object Scotch {
sealed abstract class Preparation
case object Neat extends Preparation
case object OnTheRocks extends Preparation
case object WithWater extends Preparation

case class OrderOfScotch private[Scotch](val brand:String, val mode:Preparation, val isDouble:Boolean)

trait Option[+X]
case class Some[+X](x:X) extends Option[X]{
def get:X = x
}
trait None extends Option[Nothing] // this differs in the original implementation
case object None extends None

case class Builder[HAS_BRAND<:Option[String],HAS_MODE<:Option[Preparation],HAS_DOUBLE<:Option[Boolean]] private[Scotch]
(brand:HAS_BRAND
,mode:HAS_MODE
,isDouble:HAS_DOUBLE
) {
def ~[X](f:Builder[HAS_BRAND,HAS_MODE,HAS_DOUBLE] => X):X = f(this)
}

def withBrand[M<:Option[Preparation],D<:Option[Boolean]](brand:String)(b:Builder[None,M,D]):Builder[Some[String],M,D] =
Builder(Some(brand),b.mode,b.isDouble)
def withMode[B<:Option[String],D<:Option[Boolean]](mode:Preparation)(b:Builder[B,None,D]):Builder[B,Some[Preparation],D] =
Builder(b.brand,Some(mode),b.isDouble)
def isDouble[B<:Option[String],M<:Option[Preparation]](isDouble:Boolean)(b:Builder[B,M,None]):Builder[B,M,Some[Boolean]] =
Builder(b.brand,b.mode,Some(isDouble))

def build(b:Builder[Some[String],Some[Preparation],Some[Boolean]]):OrderOfScotch =
OrderOfScotch(b.brand.get,b.mode.get,b.isDouble.get)

def builder:Builder[None,None,None] = Builder(None,None,None)

def test {
val x:OrderOfScotch = builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ build
// builder ~ isDouble(true) ~ withMode(Neat) ~ build // fails
// builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ withBrand("Blubber") ~ build // fails
x
}
}


Tuesday, September 8, 2009

A Number Puzzle

My friend came up with a new puzzle. Given a 3x3 matrix, fill it with the numbers 1 through 9, without repetition, in such a way that adding the three digits from any line, column or diagonal will yield exactly the same result.

This time I went for conciseness. Instead of laying out a 3x3 array -- or what have you -- I'll take a list of 9 elements, and assume the elements are laid out left to right, then top to down, so that the third element of the second line is the sixth element of the list, for example. Now, before I try to solve it, I have to devise a way to test the conditions. First, let's create a list of list of indices for each line, column of diagonal possible. This can be done programmatically, of course, like this:

 
val cols = List.range(0,3)
val lines = cols map (_ * 3)
val allLines = lines map (l => cols map (l + _))
val allCols = cols map (c => lines map (c + _))
val diagLR = lines zip cols map Function.tupled(_+_)
val diagRL = lines zip cols.reverse map Function.tupled(_+_)
val indices = diagLR :: diagRL :: allLines ::: allCols


I decided just to enter it by hand, though:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))


Now, I want to test this. Suppose I have a list of numbers representing the solution. I can replace the indices by the corresponding number like this:

 
indices map (_ map (solution(_)))


from which is quite easy to compute how much each line, column and diagonal adds to:

 
indices map (_ map (solution(_)) sum)


One way, then, to check if all numbers are equal is to simply compare them:

 
indices map (_ map (solution(_)) sum) match { case head :: tail => tail forall (_ == head) }


Not concise enough for me, though. I prefer this:

 
(indices map (_ map (solution(_)) sum) removeDuplicates).size == 1


Our test function, then, is:

 
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1


Now, how to compute the solutions? We can do it recursively with lists, recursions, filters, etc. Too much work. Let's just enumerate the possible solutions. The first element can be represented by the index over a nine-elements list of a "seed" solution. The second element can be represented by an index over the eight-element list of remaining elements, and so on. We can disambiguate the first index from the second by multiplying the second by 9, and add both. We can repeat this over and over for every other element in the list. So, to go from a number representing the solution, plus a seed list, to the solution, we can write this function:

 
def numToIndices(n: Int, l: List[Int]): List[Int] =
if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))


Now, given this representation of the solutions of this problem, it should be clear that the number of solutions is the factorial of 9, so there are solutions from 0 to 9! - 1. So, let's create a seed, and, non-strictly (to avoid out of memory errors), generate our possible solutions:

 
val seed = 1 to 9 toList
val possibleSolutions = Stream.range(0, seed reduceLeft (_*_)) map (numToIndices(_, seed))


Keeping the head of a stream is not a good idea, though. We need to filter for the actual solutions before assigning it to any val. Which, of course, we'll give you the final solutions:

 
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList


Not particularly efficient, but the line count is good:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1
def numToIndices(n: Int, l: List[Int]): List[Int] =
if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))
val seed = 1 to 9 toList
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList


Which we can then print with:

 
println(solutions map (_.iterator grouped 3 map (_ mkString) mkString "\n") mkString "\n")

Friday, September 4, 2009

A Puzzle

A couple of days ago a friend of mine was playing with a puzzle I knew of a few years ago: a maze through which one had to drive a car. Here's the setup:

At each intersection, the car must take one of a limited number of allowed paths, as indicated by the arrows. The goal is to reach the exit on the other side.

At any rate, I felt an urge to solve it programmatically -- in Scala, of course. So, later, I sat down and started coding the solution. The first step, obviously, was getting the maze into some sort of data structure. I briefly tried to find the data being used in the puzzle, but gave up on it. Instead, I'd input the maze by hand.

I had two problems to solve, then. First, I had to figure out a good data structure to represent the maze. I thought a directed graph with the intersections as vertices seemed like a good representation to me, but the matricial nature of the maze was also appealing. So I decided on a compromise: I'd store the maze as a matrix, but each element of the matrix would be a vertex, which would be represented as a set of arrows.

The second problem related to how I'd represent the maze before inputting it. I decided to write it down as a big string and then parse it, but that still leaves the problem of what to write. I pondered writing each edge, but that seemed a bit error-prone. So I decided on a rather unconventional format: I'd write the directions going out from each intersection, as well as undirected edges represented by the two directions the edge connects.

In effect, the actual vertices of my graph are not the intersections, but the streets! Each intersection is just a set of directed edges.

So, having decided all that, I wrote down the data I expected to be used for the maze:



val graphString = """|
|DR: DR, RLD: RD LD, L: DL LR, LR: DR LR, DL: DL
|UR: LU RU DU LR, LRD: LR UD LU RU LD RD, UDLR: UD LR UR LD, UDLR: UD LR RD, UL: UD UL
|UDR: UD RU RD, UDLR: LR LD DR RU, UD: UD UL DL, UDR: UD UR, UD: UD LD
|UDR: UD RU RD, UDLR: UR UL LR RD, UR: UD LR LU RU DR, ULR: LR UR UL DR DL, UDLR: UD UL DR
|UR: UR, ULR: UL UR LR, ULR: UL UR RL, ULR: UL UR RL, UL: UL
|""".stripMargin

Ugly as hell, but it should do the job. My task, then, was to specify the data structure, and write a parser for that.

First, directions. Not only my input is written in terms of directions, I was thinking of solving the problem by manipulating directions. So, let's create them. I don't particularly like Scala's Enumeration class, so I went with case objects:



object DirectionSet {
sealed abstract class Direction
case object Up extends Direction
case object Down extends Direction
case object Left extends Direction
case object Right extends Direction
val U = Up
val D = Down
val L = Left
val R = Right
}


That gives me warnings on pattern matching, and short aliases for each direction. Please note, though, that Scala already has objects called Left and Right. This shouldn't present much of a problem, but, once I improved on these objects a bit, I made sure Scala knew to which objects I was referring to. Let's talk about these improvements and show them.

As I wrote the code, I found myself needing to get the opposite direction to the one I had. This was clearly a method to be added to Direction, and so I did. Another thing I did was to write a function to convert a Char into a Direction. Later, while refactoring, it was clear this function was better as a DirectionSet method, so I added it, and, while doing it, wrote a variant for Strings, though I never use it in my final code. Let's see, them, the full object:



object DirectionSet {
sealed abstract class Direction {
def opposite: Direction
}
case object Up extends Direction { override def opposite = DirectionSet.Down }
case object Down extends Direction { override def opposite = DirectionSet.Up }
case object Left extends Direction { override def opposite = DirectionSet.Right }
case object Right extends Direction { override def opposite = DirectionSet.Left }
val U = Up
val D = Down
val L = Left
val R = Right
def apply(s: Char): Direction = s.toLowerCase match {
case 'u' => Up
case 'd' => Down
case 'l' => Left
case 'r' => Right
case _ => throw new IllegalArgumentException
}
def apply(s: String): Direction = s.toLowerCase match {
case "up" => Up
case "down" => Down
case "left" => Left
case "right" => Right
case _ => throw new IllegalArgumentException
}
}

And that's that. So, let's proceed. Our graph is composed of intersections, each of which is composed of the arrows present at that intersection. The next step, then, is defining these arrows. Here's how I did it:



import DirectionSet.{apply => _, _}


case class Arrow(from: Direction, to: Direction) {
override def toString = from+"->"+to
}
object Arrow {
def apply(t: Tuple2[Direction,Direction]): Arrow = new Arrow(t._1, t._2)
}

Each arrow is described as going from a Direction to another Direction. A couple of helper methods, and we are done. At first, it might seem that the intersection being just a set of arrows, so it doesn't need a class of it's own. However, to validate the correctness of the maze I inputted, it would be nice to have a more "graphical" representation of it. I could leave that to the graph class, but, as it happens, it's a rather long code, so I separated it into a class of its own.

So, first, I decided on the ASCII-art I'd be using to represent an intersection. I got it in as a literal, converted it into an array of arrays, and then, in the class main constructor, changed each relevant character from the ASCII-art into a space if the intersection didn't contain the corresponding arrow. The central character was a little bit more complex than that, and I used some pattern matching on it. Here's the final result:



case class Intersection(arrows: List[Arrow]) {
private val drawing = """| ^
| /|\
|<-+->
| \|/
| v """.stripMargin split "\n" map (_ toArray)
private def hasUp = arrows exists (_.to == Up)
private def hasDown = arrows exists (_.to == Down)
private def hasLeft = arrows exists (_.to == Left)
private def hasRight = arrows exists (_.to == Right)
private def hasArrowBetween(a: Direction, b: Direction) = (arrows contains Arrow(a, b)) || (arrows contains Arrow(b, a))
private def testAndSet(line: Int, col: Int, test: Boolean) =
if (!test) drawing(line)(col) = ' '

testAndSet(0, 2, hasUp)
testAndSet(1, 1, hasArrowBetween(Left, Up))
testAndSet(1, 2, hasArrowBetween(Up, Down))
testAndSet(1, 3, hasArrowBetween(Up, Right))
testAndSet(2, 0, hasLeft)
testAndSet(2, 1, hasArrowBetween(Left, Right))
testAndSet(2, 3, hasArrowBetween(Left, Right))
testAndSet(2, 4, hasRight)
testAndSet(3, 1, hasArrowBetween(Left, Down))
testAndSet(3, 2, hasArrowBetween(Up, Down))
testAndSet(3, 3, hasArrowBetween(Down, Right))
testAndSet(4, 2, hasDown)
drawing(2)(2) = (hasArrowBetween(Left, Right), hasArrowBetween(Up, Down)) match {
case (false, false) => ' '
case (false, true) => '|'
case (true, false) => '-'
case (true, true) => '+'
}

override def toString = drawing map (_ mkString) mkString "\n"
}
object Intersection {
def apply(arrows: Arrow*): Intersection = new Intersection(arrows.toList)
}


The main class, the graph, started as simple as this:



case class Graph(g: Array[Array[Intersection]])

After that, I started on the parser. The first thing was breaking up the string into basic components: each line, each intersection on the line, the outgoing arrows and the edges:



def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))


Lot's of "trim" just so I needn't worry where there were space. The next two steps were easy: for each line, for each intersection... It looks like a for-comprehension, but to return an array of arrays I'd need to nest two for-comprehensions, which makes them unyieldy. It's better simply to go with "map". So, given the input string representing each intersection, return an intersection instance. The mapping code ended looking like this:



(
brkString(s)
map (line =>
line map (col =>
Intersection(arrows(col): _*)
)
)
)


Which leaves just "arrows" to be defined. The idea behind "arrows" is to convert each letter into a direction, then, for each direction representing an outgoing arrow, find all undirected edges containing that direction and yield a directed edge in the form of an Arrow instance:



def arrows(a: Array[String]): List[Arrow] = {
def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
val dsts = str2Directions(a(0).trim)
val paths = a(1).trim split "\\s+" map str2Directions
for(dst <- dsts;
path <- paths if path contains dst;
org <- path filter (_ != dst))
yield Arrow(org, dst)
}


These functions were all independent originally, but, as I refactored, they came to be part of the Graph object:



object Graph {
def apply(s: String) = new Graph(str2Graph(s))

def str2Graph(s: String) = {
def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))
def arrows(a: Array[String]): List[Arrow] = {
def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
val dsts = str2Directions(a(0).trim)
val paths = a(1).trim split "\\s+" map str2Directions
for(dst <- dsts;
path <- paths if path contains dst;
org <- path filter (_ != dst))
yield Arrow(org, dst)
}
(
brkString(s)
map (line =>
line map (col =>
Intersection(arrows(col): _*)
)
)
)
}
}

With that I could now create an instance of my graph. I could verify each intersection individually, but printing them side by side posed a problem: each intersection was composed of multiple lines, so I needed to interpolate the lines of all intersections belonging the the same "line" in the graph before I could concatenate them.

I approached this as a general problem in concatenating string with multiple lines. I'd split each string into its component lines, and keep a list of those. I'd then try to "fold" them into a big string, but that was too hacky for my tastes. I then modified it to iterate over these lists, concatenating the "heads" and looping with the "tails". Finally, I'd take each of those lines of intersection, and concatenate with interpoling newlines to the next. Here's the final result:



override def toString = {
def concatStrings(ss: String*) = {
// Turn my arguments into a list of lists of lines, get the length
// of the biggest chunk, a pad of the same size, and a function to
// make them all the same length
val lines = ss.toList map (_ split "\n" toList)
val maxLineSize = lines flatMap (_ map (_ length)) reduceLeft (_ max _)
val pad = " " * maxLineSize
def fmtStr(s: String) = "%"+maxLineSize+"s" format s

// Make an iterator for "lines"
def tailOrNil[T](l: List[T]) = if (l.isEmpty) Nil else l.tail
def getTails[T](l: List[List[T]]): List[List[T]] = l map tailOrNil[T]
def hasLines(l: List[List[_]]) = l exists (!_.isEmpty)
val linesIterator = Iterator.iterate(lines)(getTails) takeWhile hasLines

// Get the head of each list, or a pad in the absence of a head,
// make them all the same size, and then concatenate with an interpoling
// pad.
def concatHead(l: List[List[String]]): String =
l map (_.headOption getOrElse pad) map fmtStr mkString pad

// Iterate over lines, concatenating the heads of the list, and then
// concatenate them all with interpolating newlines
(for(nextLines <- linesIterator)
yield concatHead(nextLines)) mkString "\n"
}
g map (line => concatStrings(line map (_ toString): _*)) mkString "\n\n\n"
}

You can tell by the amount of comments that I'm not really satisfied with it yet, but it does its job. Here's an example:







> < > <--- <---> <
/ \ / \ / \
v v v




^ ^ ^ ^
/|\ /|\ |\ | /|
-+-> <-+-> <-+-> <-+-> < |
| \|/ \| |/ |
v v v




^ ^ ^ ^ ^
|\ \ /| |\ |
| > <---> | | > |
|/ \ / \| | \|
v v v v v




^ ^ ^ ^ ^
|\ / \ /|\ / \ /|
| > <---> -+-> <---> < | >
|/ / |/ \ / |/
v v v




^ ^ ^ ^ ^
\ / \ / \ / \ /
> <---> <---> <---> <






Now I started on the solving algorithm properly. This part of it was rather faster and problem-free. First, I had to have a way to indicate where my car was. I created a class Position for that. This class has two components: one is the actual coordinates, indicating at which intersection the car had stopped -- I called it Coordinates. The other component is the direction from which the car was entering the intersection. Here's the class:



case class Coordinates(line: Int, column: Int) {
override def toString = "("+line+","+column+")"
}
case class Position(from: Direction, at: Coordinates) {
override def toString = from.opposite.toString.toLowerCase+" to "+at
}

They didn't have any toString method originally. When I finally got to print the answer, I changed those methods to make the answer more readable.

Finally, I added a couple of methods to Graph. First, given a Position, to which directions the car could go? This one is quite natural:



def directionsFrom(pos: Position):List[Direction] = (
g(pos.at.line)(pos.at.column).arrows
filter (_.from == pos.from)
map (_.to)
)


Next, given a Position, which would be the next available positions? This one required a helper method, which would compute the correct coordinates when moving in a given direction. I use "opposite" here. The idea is that, if I'm going "down", for example, I'd end at the upper side of the next intersection.



def positionsFrom(pos: Position): List[Position] = {
def moveTo(to: Direction) = Position(to.opposite, to match {
case Up => Coordinates(pos.at.line - 1, pos.at.column)
case Down => Coordinates(pos.at.line + 1, pos.at.column)
case Left => Coordinates(pos.at.line, pos.at.column - 1)
case Right => Coordinates(pos.at.line, pos.at.column + 1)
})
directionsFrom(pos) map moveTo
}

And, with that, we are ready to solve the problem. All we need to do is keep following the coordinates. Since I receive a list of coordinates at each intersection, I have to try all of them. There's two ways of going about it. First, I can take the first option out of each intersection and keep going, until I start looping around, get to a dead end, or arrive at my destination. I can then opt to backtrack and try one of the other options. That's a depth first algorithm, a natural for recursion.

Alternatively, I can keep a list of all possible paths, and keep extending each one until one arrives. That can be done nicely with queues. I take one path from the beginning of a queue, compute all possible paths from there, and add them to the back of the queue. Once I find a path that has arrived at the goal, I stop. This is what I decided to do. Here's the algorithm:



val graph = Graph(graphString)
val origin = Position(Left, Coordinates(1, 0))
val goal = Coordinates(3, 5)

def solve = {
import scala.collection.mutable.{Set, Queue}

def nextPaths(path: Path, visited: Set[Position]): List[Path] = (
graph
positionsFrom path.head
filter (to => !(visited contains to))
map (to => to :: path)
)
val visited = Set[Position]()
val next = new Queue[Path]()
var path = List(origin)
while(path.head.at != goal) {
visited += path.head
next enqueue (nextPaths(path, visited): _*)
path = next dequeue
}
printAnswer(path)
}


I still did a little trick to print the answer in a readable way, but it was hacky enough that I won't get into details. Here's the whole program, though. You can paste it directly into REPL and run it with "Problem.solve", or compile it and run Problem. So, how would you code this in YOUR favorite language? Please drop me a link on the comments below if you take this challenge too.



object DirectionSet {
sealed abstract class Direction {
def opposite: Direction
}
case object Up extends Direction { override def opposite = DirectionSet.Down }
case object Down extends Direction { override def opposite = DirectionSet.Up }
case object Left extends Direction { override def opposite = DirectionSet.Right }
case object Right extends Direction { override def opposite = DirectionSet.Left }
val U = Up
val D = Down
val L = Left
val R = Right
def apply(s: Char): Direction = s.toLowerCase match {
case 'u' => Up
case 'd' => Down
case 'l' => Left
case 'r' => Right
case _ => throw new IllegalArgumentException
}
def apply(s: String): Direction = s.toLowerCase match {
case "up" => Up
case "down" => Down
case "left" => Left
case "right" => Right
case _ => throw new IllegalArgumentException
}
}

import DirectionSet.{apply => _, _}

case class Arrow(from: Direction, to: Direction) {
override def toString = from+"->"+to
}
object Arrow {
def apply(t: Tuple2[Direction,Direction]): Arrow = new Arrow(t._1, t._2)
}

case class Intersection(arrows: List[Arrow]) {
private val drawing = """| ^
| /|\
|<-+->
| \|/
| v """.stripMargin split "\n" map (_ toArray)
private def hasUp = arrows exists (_.to == Up)
private def hasDown = arrows exists (_.to == Down)
private def hasLeft = arrows exists (_.to == Left)
private def hasRight = arrows exists (_.to == Right)
private def hasArrowBetween(a: Direction, b: Direction) = (arrows contains Arrow(a, b)) || (arrows contains Arrow(b, a))
private def testAndSet(line: Int, col: Int, test: Boolean) =
if (!test) drawing(line)(col) = ' '

testAndSet(0, 2, hasUp)
testAndSet(1, 1, hasArrowBetween(Left, Up))
testAndSet(1, 2, hasArrowBetween(Up, Down))
testAndSet(1, 3, hasArrowBetween(Up, Right))
testAndSet(2, 0, hasLeft)
testAndSet(2, 1, hasArrowBetween(Left, Right))
testAndSet(2, 3, hasArrowBetween(Left, Right))
testAndSet(2, 4, hasRight)
testAndSet(3, 1, hasArrowBetween(Left, Down))
testAndSet(3, 2, hasArrowBetween(Up, Down))
testAndSet(3, 3, hasArrowBetween(Down, Right))
testAndSet(4, 2, hasDown)
drawing(2)(2) = (hasArrowBetween(Left, Right), hasArrowBetween(Up, Down)) match {
case (false, false) => ' '
case (false, true) => '|'
case (true, false) => '-'
case (true, true) => '+'
}

override def toString = drawing map (_ mkString) mkString "\n"
}
object Intersection {
def apply(arrows: Arrow*): Intersection = new Intersection(arrows.toList)
}

case class Coordinates(line: Int, column: Int) {
override def toString = "("+line+","+column+")"
}
case class Position(from: Direction, at: Coordinates) {
override def toString = from.opposite.toString.toLowerCase+" to "+at
}

case class Graph(g: Array[Array[Intersection]]) {
def directionsFrom(pos: Position): List[Direction] = (
g(pos.at.line)(pos.at.column).arrows
filter (_.from == pos.from)
map (_.to)
)

def positionsFrom(pos: Position): List[Position] = {
def moveTo(to: Direction) = Position(to.opposite, to match {
case Up => Coordinates(pos.at.line - 1, pos.at.column)
case Down => Coordinates(pos.at.line + 1, pos.at.column)
case Left => Coordinates(pos.at.line, pos.at.column - 1)
case Right => Coordinates(pos.at.line, pos.at.column + 1)
})
directionsFrom(pos) map moveTo
}

override def toString = {
def concatStrings(ss: String*) = {
// Turn my arguments into a list of lists of lines, get the length
// of the biggest chunk, a pad of the same size, and a function to
// make them all the same length
val lines = ss.toList map (_ split "\n" toList)
val maxLineSize = lines flatMap (_ map (_ length)) reduceLeft (_ max _)
val pad = " " * maxLineSize
def fmtStr(s: String) = "%"+maxLineSize+"s" format s

// Make an iterator for "lines"
def tailOrNil[T](l: List[T]) = if (l.isEmpty) Nil else l.tail
def getTails[T](l: List[List[T]]): List[List[T]] = l map tailOrNil[T]
def hasLines(l: List[List[_]]) = l exists (!_.isEmpty)
val linesIterator = Iterator.iterate(lines)(getTails) takeWhile hasLines

// Get the head of each list, or a pad in the absence of a head,
// make them all the same size, and then concatenate with an interpoling
// pad.
def concatHead(l: List[List[String]]): String =
l map (_.headOption getOrElse pad) map fmtStr mkString pad

// Iterate over lines, concatenating the heads of the list, and then
// concatenate them all with interpolating newlines
(for(nextLines <- linesIterator)
yield concatHead(nextLines)) mkString "\n"
}
g map (line => concatStrings(line map (_ toString): _*)) mkString "\n\n\n"
}
}
object Graph {
def apply(s: String) = new Graph(str2Graph(s))

def str2Graph(s: String) = {
def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))
def arrows(a: Array[String]): List[Arrow] = {
def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
val dsts = str2Directions(a(0).trim)
val paths = a(1).trim split "\\s+" map str2Directions
for(dst <- dsts;
path <- paths if path contains dst;
org <- path filter (_ != dst))
yield Arrow(org, dst)
}
(
brkString(s)
map (line =>
line map (col =>
Intersection(arrows(col): _*)
)
)
)
}
}

object FormatLines {
def apply(s: String): String = {
def breakAt80(s: String): (String, String) = {
val m = """^(.{0,80})( (.*))?$""".r findFirstMatchIn s
m match {
case Some(result) =>
val rest = if (result.group(3) == null) "" else result.group(3)
(result.group(1), rest)
case None => (s, "")
}
}
def fmt(input: String, output: String): String =
if (input.isEmpty)
output
else {
val (nextLine, rest) = breakAt80(input)
fmt(rest, output+nextLine+"\n")
}
fmt(s, "")
}
}

object Problem {
type Path = List[Position]
val graphString = """|
|DR: DR, RLD: RD LD, L: DL LR, LR: DR LR, DL: DL
|UR: LU RU DU LR, LRD: LR UD LU RU LD RD, UDLR: UD LR UR LD, UDLR: UD LR RD, UL: UD UL
|UDR: UD RU RD, UDLR: LR LD DR RU, UD: UD UL DL, UDR: UD UR, UD: UD LD
|UDR: UD RU RD, UDLR: UR UL LR RD, UR: UD LR LU RU DR, ULR: LR UR UL DR DL, UDLR: UD UL DR
|UR: UR, ULR: UL UR LR, ULR: UL UR RL, ULR: UL UR RL, UL: UL
|""".stripMargin
val graph = Graph(graphString)
val origin = Position(Left, Coordinates(1, 0))
val goal = Coordinates(3, 5)

def printAnswer(path: Path) {
val answer = FormatLines(
"Arrived at "+path.head.at+
" through "+path.tail.reverse.mkString(", ")+
" and then "+path.head.from.opposite.toString.toLowerCase+"."
)
println(graph)
println(answer)
}

def solve = {
import scala.collection.mutable.{Set, Queue}

def nextPaths(path: Path, visited: Set[Position]): List[Path] = (
graph
positionsFrom path.head
filter (to => !(visited contains to))
map (to => to :: path)
)
val visited = Set[Position]()
val next = new Queue[Path]()
var path = List(origin)
while(path.head.at != goal) {
visited += path.head
next enqueue (nextPaths(path, visited): _*)
path = next dequeue
}
printAnswer(path)
}

def main(args: Array[String]) {
solve
}
}




Monday, August 17, 2009

Regex and Option trick

Neat trick:


def findBetween(s: String, p1: String, p2: String) = (
("\\Q"+p1+"\\E(.*?)\\Q"+p2+"\\E").r
findFirstMatchIn s
map (_ group 1)
getOrElse ""
)


The trick here is that map, on an Option, applies the function if the option is Some, otherwise returns None. So I get to convert my Match into a particular group before I check if I got anything at all and return a default if not.

Sunday, July 19, 2009

Software Engineering -- An Idea Whose Time Has Gone?

That's a powerful statement over there. One I'd never dare state (aloud, at least :). They are not my words, though, they are Tony DeMarco's, who famously said "You can't control what you can't measure" in his book, Controlling Software Projects: Management, Measurement, and Estimation, Prentice Hall/Yourdon Press, 1982.

Well, he hasn't changed his mind about that, but he seems to have come to the conclusion that the relative value of that, particularly balanced against the costs of measuring -- which he once discounted -- is not what he once thought. You can read it on this IEEE-published article.

Tuesday, July 7, 2009

Getting Around Type Erasure with Manifests

A friend posed an interesting problem to me yesterday. He wanted a registry-like structure in which he would put pairs of key/value, and then get them back. However, he wished for it to be type-safe. Specifically, if he put a List[Int] inside it, and tried to get a List[String] out, he shouldn’t get anything.

This is generally a problem because of type erasure, a restriction of the JVM. At runtime, a List object knows it is a List, but not of what kind of element.

Alas, an obscure, and experimental, feature of Scala let you get around that. It’s the Manifests. A Manifest is class whose instances are objects representing types. Since these instances are objects, you can pass them around, store them, and generally call methods on them. With the support of implicit parameters, it becomes a very powerful tool:

object Registry {
import scala.reflect.Manifest

private var _map= Map.empty[Any,(Manifest[_], Any)]

def register[T](name: Any, item: T)(implicit m: Manifest[T]) {
_map = _map(name) = (m, item)
}

def get[T](key:Any)(implicit m : Manifest[T]): Option[T] = {
val o = _map.get(key)

o match {
case Some((om: Manifest[_], s : Any)) =>
if(om <:< m) Some(s.asInstanceOf[T]) else None
case _ => None
}
}
}

scala> Registry.register('a, List(1,2,3))

scala> Registry.get[List[Int]]('a)
res6: Option[List[Int]] = Some(List(1, 2, 3))

scala> Registry.get[List[String]]('a)
res7: Option[List[String]] = None

Above, Manifest is being passed as an implicit parameter – defined inside scala.reflect.Manifest – based on the type parameter T, and stored along the value. When you put a value in the register, it is not necessary to specify its type, as this gets inferred.

When you take a registry out, though, you specify the type the type you want (inference won’t help you here), and, if the key does not exist or does not store the desired type, it will return None. If a key exists and the type is correct, it will return Some(value).

Note that the operator <:< tests for subclassing. That is, the desired type m must be a superclass of the stored type om.

Saturday, July 4, 2009

Delimited Continuations Explained (in Scala)

One of the promised features for Scala 2.8 is a delimited continuations plugin. A brief description was given in the Scala site, though the examples were, in my opinion, badly chosen.

Though my understanding is still pretty bare, I intend to shed a bit of light on it here. This is not directed at the experts, the people who will actually use them regularly, but at the people who will see them occasionally and will wonder what the heck is happening. Also, I might quite possibly have made mistakes below. If you do find mistakes, please correct me and I’ll fix the post.

First, let’s discuss why Scala is adopting continuations, and what, exactly, are them.

Continuations are, in essence, a program flow control structure, like conditional statements, loops, exceptions, etc. As mentioned in Scala’s Continuations Paper, classical, or full, continuations can be seen as a functional version of GOTO statements. If you haven’t heard of GOTO statements before, it’s enough to know they are essentially extinct for good reason.

Still quoting, delimited continuations are more like regular functions and less like GOTOs, and this makes them more powerful than the classical ones. So, basically, we are looking into a way of changing the execution flow of a program.

Using continuations is not easy. In fact, it’s difficult and error-prone, according to some references. But they can be very efficient performance-wise, and they allow one to build libraries with some interesting flow control abstractions built on top of continuations.

For these reasons, I doubt most Scala users will have much contact with them, and I suspect the ones who do will regret the necessity. The people writing libraries and frameworks, though, will likely be grateful that they are available. In that respect, continuation is not unlike some other advanced Scala features.

Ok, so let’s get to them. In Scala, continuations will be used through two keywords (or functions?), “reset” and “shift”. Like “catch” and “throw”, a “shift” always happen inside a “reset”, the later being responsible for delimiting the scope of the continuation. Before we proceed, let’s give some usage examples, which I’ll then try to explain.

Example 1:

reset {
shift { k: (Int=>Int) =>
 k(7)
} + 1
}
// result: 8


Example 2:
def foo() = {
println("Once here.")
shift((k: Int => Int) => k(k(k(7))))
}
def bar() = {
1+ foo()
}
def baz() = {
reset(bar() * 2)
}
baz()  // result 70

Example 3:
reset {
 println(1)
}
//prints: 1

reset {
 println(1)
 shift { (cont: Unit => Unit) => }
 println(2)
}
//prints: 1

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     println(2)
 }
 println(3)
}
//prints: 1 2

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     cont()
     println(2)
 }
 println(3)
}
//prints: 1 3 2

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     cont()
     cont()
     println(2)
 }
 println(3)
}
//prints: 1 3 3 2

So we have two examples of continuations as expressions, and one as purely flow control. The first example seems pretty simple: the whole shift is replaced with “7”, and, therefore, reset returns “7+1”. The third example shows that, in fact, the code before shift is executed once, the code after shift as many times as the function inside shift is repeated, and the code inside the shift itself is executed once, going back and forth to the code after it.

So we look at the second example, and see that… the code before shift seems to get executed many times! Actually, the method receiving the result of shift is being executed many times, once for each time “shift” return, but the statement right before shift only gets executed once.

These examples were probably enough to… make things more confusing, right? So let’s understand what is happening. Scala’s continuations are based on a selective Continuation Passing Style (CPS) transformation. The Wikipedia page on CPS is actually pretty good, so, please, take a moment to peruse it, and understand the examples given at the beginning, and then come back here.

Ready? Well, one thing that immediately came to mind is that this looks like programming backwards! They call it “inside-out” in that page, which is more appropriate, I suppose, but one has to pay attention to first impressions. :-)

What is happening there is that the innermost functions of normal programming style are outmost, and vice versa. You’ll see that this is what is happening with shift and reset.

I’ll now explain a bit of what is happening in a continuation. Notice, first, that the code associated with the shifts are functions: they are all in the form { k => … }. So, the first thing to keep in mind is that shifts are functions taking a parameter.

Now, pay attention, again, to the very first example. It defines the type of k as being “Int => Int”. In the first example, then, shift is a function which takes as parameter another function. This is actually true of all shifts, even if the function being passed to shift takes no parameters and returns Unit.

So a shift is a function which receives another function as parameter. As the body of the shift gets executed, that function-parameter may get called or not. From the second example, it is pretty obvious that the code after the shift only gets executed if that function-parameter is called.

By now you probably have an uneasy intuition that that parameter is, in fact, the code after the shift. That’s essentially right, but let’s further into this.

The result of reset is the result of the code inside shift. So, in the first example, “8”, the result of reset, is also the result of the shift code, “k: (Int => Int) => k(7)”. It should be obvious, then, that the value passed to “k” is “x: Int => x + 1”, which is a function of Int => Int, as required. Now, take a look at the two lines below:
shift { k: (Int=>Int) => k(7) } + 1
x                               + 1

So, the function being passed as parameter is formed by taking the whole code from the shift on, and replacing shift with “x”. In effect, when k(7) is executed, this is like replacing the whole shift with 7, and then continuing until the end of reset. At that point, though, the execution resumes inside the shift. In this example there is nothing more in there, so the result is 8.

What is actually happening is this:
((k: Int => Int) => k(7))((x: Int) => x + 1)

As said before, we are passing a function to another. You can paste that code inside REPL and it will work as expected. You may also try this code here:
((k: Int => Int) => k(k(k(7))))((x: Int) => (1 + x) * 2)

Are you getting a feeling now for it? So, whenever you see reset/shift, first think of the whole reset expression, replacing the shift inside it with an unknown variable – we’ll keep calling it x for now:
Reset { before shift { k => ... k(something) ... } after }
Reset { before x after }

Now replace Reset with a function declaration of one parameter:
Reset { before x after }
x => { before x after }

What type is “x” supposed to be? You can find it inside the shift, by looking into what is being passed to “k” – the “something” in the example. We can now rewrite the whole reset statement, placing first the shift code, then the reset code as parameter, like we did before:
( k => ... k(something) ... ) {x => { before x after }}

And this is pretty much what happens when you use continuations.

As for the second example, though the “1 + “ looks to be to the “left” of shift, it actually gets executed after shift returns, so it is part of the function being passed to shift. You find the same situation when making tail recursive functions. If you tried “1 + recurse()”, it would not be tail recursive, because “+” would only be executed after the call to “recurse” returned.

Pretty easy, right? Let’s try something with two shifts:
type Monadic[+U, C[_]] = {
def flatMap[V](f: U => C[V]): C[V]
}

class Reflective[+A, C[_]](xs: Monadic[A,C]) {
def reflect[B](): A @cps[C[B], C[B]] = {
 shift { k:(A => C[B]) =>
   xs.flatMap(k)
 }
}
}

implicit def reflective[A](xs:Iterable[A]) =
new Reflective[A,Iterable](xs)

reset {
val left = List("x","y","z")
val right = List(4,5,6)

List((left.reflect[Any], right.reflect[Any]))
}
// result: List[(String, Int)] = List((x,4), (x,5), (x,6), (y,4), (y,5), (y,6), (z,4), (z,5), (z,6)

Don’t hate me, it is in good cause. :-) If you can understand this… well, you can understand this. But I’m sure you’ll start to really get a grip in it.

First, let’s discard the irrelevant parts of the code above. Everything but the “reflect” definition and the reset code is irrelevant. They are there just to make “reflect” available to a List, it’s plain-old Enrich My Library pattern, though the use of a structural type is cool. :-)

Now, let’s replace left.reflect and right.reflect with the actual code getting executed – I’ll change k into k1 and k2 so as not to confuse both, so we are left only with the reset code:
reset {
val left = List("x","y","z")
val right = List(4,5,6)

List((shift { k1:(String => List[Any]) => left.flatMap(k1)}, shift { k2:(Int => List[Any]) => right.flatMap(k2)}))
}

Since there are two shifts, should we have two unknowns being passed to shift? If you look at the type signatures for k1 and k2, the answer is no. Each shift gets a single parameter.

You may think that the “Any” type means one list is formed by a single element, and the other by a tuple, but that’s not true. You can change both types to “List[(String,Int)]”, and it would still work. No, the type signatures are right, the trick is in how they are composed together.

If you think it through simply in terms of flow control, the first shift will return a value (“x”), and then the second shift will return a value (4), producing a list. The flow then returns to the last shift, which will return another value (5), and then another still (6). At this point, the flow returns once again to the first shift, which will produce it’s next value (“y”). So the trick is in how we compose the functions.

Let’s see, first, both shifts:
((k1: String => List[(String,Int)]) => left.flatMap(k1))
((k2: Int => List[(String,Int)]) => right.flatMap(k2))

These can’t and won’t be changed. The trick is how we compose them:
((k1: String => List[(String,Int)]) => left.flatMap(k1))
((x: String) => ((k2: Int => List[(String,Int)]) => right.flatMap(k2))
             ((y: Int) => List((x,y)))
)

So what happens is that the function which takes a String and returns a List of (String,Int) that gets passed to the first shift is composed of both the reset function and the second shift function.

The function passed to the second shift does not need an additional String parameter because the string is already bound.

Now you have seen both the control flow of reset/shift, and how to translate them into common functions to understand what values they will produce. I hope it will be of help when the time comes in which you need to understand these structures.

Note: many things have changed since I wrote this blog. Continuations have gone through minor changes in the annotations, and collections have gone through big changes. I haven't checked out all examples yet, but I know the one with the two lists doesn't work anymore. The following code will work for that example, though I wish I could make it more general than it presently is:

type Monadic[+U, C[_]] = {
  def flatMap[V, That](f: U => C[V])(implicit cbf: collection.generic.CanBuildFrom[C[U], V, That]): That
}

class Reflective[+A](xs: Monadic[A,Traversable]) {
  def reflect[B](): A @cps[Traversable[B]] = {
    shift { k:(A => Traversable[B]) =>
      xs.flatMap(k)(collection.breakOut) : Traversable[B]
    }
  }
}

implicit def reflective[A](xs:Traversable[A]) = new Reflective[A](xs)

reset {
  val left = List("x","y","z")
  val right = List(4,5,6)

  List((left.reflect[Any], right.reflect[Any]))
}

Thursday, July 2, 2009

Matrices 6

In this last installment of the Matrices series, we’ll look into making the Matrix class parameterized. What does that means? Basically, we want to have Matrix declared like this:

class Matrix[T]

So that we can create matrices of Ints, Doubles, or whatever other numeric type we need. This is not a trivial exercise, because of the way numeric types are defined in Java, and Scala’s backward compatibility with it. Basically, there is no common superclass to them.

Paul Chisuano offered two alternatives around that. One would involve the “Enrich My Library” pattern, but I do not think it would offer any gains over MatrixInt as it was built, and I see a problem or two implementing it.

We’ll discuss the other solution he proposes, which is, indeed, very clever. If we were building this in Java, would idea would be creating an interface with the operations we need, and a concrete class for each type we need. For instance, let’s call our interface Scalar, and our concrete classes implementing it IntScalar, DoubleScalar, etc. We would then define a Matrix class parameterized with an “upper bound” of Scalar, created from an Array of Arrays of Scalar. That would work, but can be quite slow.

Instead of that, we’ll use one of the more wizardry of Scala’s features, the implicit type conversion argument. You have probably seen things like this before:
implicit def xToY(x: X): Y = Y(x)

This definition makes it possible to convert an object of class X to an object of class Y without explicitly doing so. If I ever need an object of class Y and I have an object of class X instead, Scala will apply that definition to object X without any explicit statement on my part to do so.

Even if you haven’t seen that before, you almost certainly have used it. See the two examples below:
scala> val a = 1.0; val b = 1
a: Double = 1.0
b: Int = 1

scala> a + b
res12: Double = 2.0

scala> val c = Map('a -> 1)
c: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 1)

In each case, there is an implicit conversion at work. These definitions can, in fact, be found inside the object scala.Predef, which is imported automatically into scope of every Scala program. The first one is obvious, the second one, not so much. To understand the second, you have to realize that class Symbol does not define the method “->”, and that “->” is not a Scala keyword. I’ll leave as an exercise to find what implicit conversion is being used here.

What that means for us is that we can create a Scalar class, as well as implicit conversions from our desired types to it. Scalar would look like this:
abstract class Scalar[T](self: T) {
 def +(other: T): T
 def -(other: T): T
 def /(other: T): T
 def %(other: T): T
 def *(other: T): T
}

One thing to note here is that none of the operations defined for Scalar take another Scalar as argument, nor do they return a Scalar. The reason for this is that we do not want to store Scalars. They are bulky and inefficient. We just want to quickly convert an Int or Double into Scalar, and then produce, through an Int or Double operation, and Int or Double result to be stored in an Array, or returned as result of determinant or similar methods.

Even without implicits, we could define Matrix like this:
class Matrix[T](self: Array[Array[T]], toScalar: T => Scalar[T])

We could then use toScalar everywhere we do an operation over a type T. With implicit, we could just add an implicit definition to the top of class Matrix, so we don’t need bother explicitly using toScalar. But we don’t need to do even that. Look at the following definition:
class Matrix[T](self: Array[Array[T]])(implicit toScalar: T => Scalar[T])

This definition of Matrix constructor, with two sets of () for arguments, is said to be curried. I won’t be explaining what that means here, because what interests us is the implicit keyword in there. The important thing here is that when you define something like that, then two things useful for us happen:

1. If there is an implicit definition of the type “T => Scalar[T]” in scope when we call Matrix, then it will be automatically passed to the constructor. Or, in other words, you can call “new Matrix(Array(Array(1)))” anywhere there is an implicit definition from Int to Scalar[Int], without having to pass that implicit definition as well.
2. There is no need to define an implicit conversion inside Matrix itself. Any implicit conversion passed as an argument will already be used inside the class.

This rule is also valid for implicit conversions arguments on method definitions, by the way.

Anyway, this is so useful and powerful that Scala has another way of saying the same thing:
class Matrix[T <% Scalar[T]](self: Array[Array[T]])

The “<%” keyword means there should be an implicit conversion between the first type and the second in scope where Matrix constructor is called, or that one such conversion must be explicitly passed.

So, we search&replace every instance of MatrixInt for Matrix[T], define our constructor as above (plus minor details such as “private” and “val”), replace Int with T where appropriate (remember that row and column coordinates are still Ints!), create the Scalar class, the subclasses for the types we want, the implicit conversions, and we are done, right?

Not so. Scalar, alas, is not enough. If you look at the definitions of sign, isDivisibleBy and invert, you will see we mix “T” with -1, 0 and 1. Since we do not know that -1, 0 and 1 can be mixed with “T”, we still need something else. Alas, what we need is actually very simple: an implicit definition between Int and T, so that when we use -1, it can be converted to the proper type, be it Int, Double or whatever.

We have to be careful of one thing, though. See the two lines below:
map Function.tupled((value, col) => value * cofactor(0, col).determinant * sign(0, col))
map Function.tupled((value, col) => sign(0, col) * value * cofactor(0, col).determinant)

The first line works, because it is converted into this:
map Function.tupled((value, col) => toScalar(value) * toScalar(cofactor(0, col).determinant) * intToT(sign(0, col)))

The second line doesn’t work, as it would need to be converted into this:
map Function.tupled((value, col) => toScalar(intToT(sign(0, col))) * toScalar(value) * cofactor(0, col).determinant)

On the first line there was at most one implicit conversion for each parameter. On the second line, though, since T doesn’t have the method “*”, and Int doesn’t have the method “*(T)”, two implicit conversions would need to be applied.

Scala won’t apply two implicit conversions on the same element. In this case, we can make “sign” return T, so the extra implicit conversion will be applied inside “sign”, thus avoiding this rule. We need to be careful, however, about such situations. As it happens, MatrixInt, as it was written, won’t present any such problems.

Anyway, we need, thus, two implicit conversions. The “<%” syntax isn’t enough for our particular case, so we have to do it the other way. Here’s our Matrix declaration:
class Matrix[T] private (private val self: Array[Array[T]])
                       (implicit toScalar: T => Scalar[T], intToT: Int => T) {

Note that I write “implicit” only once in the declaration. All parameters in these last parentheses will be defined as implicit. Also, please note that implicit parameters must come last in such a declaration.

This does take care of almost everything, with a bit of judicious editing on various declarations to make the signatures match. There are some places, though, where that is not the case. Look at these lines inside the method “toString”:
   val maxNumSize = self.projection flatMap (_ map (_.toString.size)) reduceLeft (_ max _)
   val numFormat = "%"+maxNumSize+"d"
   def formatNumber(n: T) = numFormat format n

We obviously can’t use “%d” for Doubles, for one thing. Also, maxNumSize doesn’t quite cut it, since we would like numbers to be aligned on the decimal point (or comma, depending on your locale), so we need to know at least two sizes. And then there are complex numbers, and who knows what else, so we don’t really know what information might be needed.

Therefore, I feel it is better to leave the choice inside Scalar itself. I propose to add the method below to Scalar, define it for Int as shown next, and then use as show last:
abstract class Scalar[T](self: T) {
 ...
 def numFormat(xs: Iterator[T]): String
}

class IntScalar(self: Int) extends Scalar(self) {
 ...
 def numFormat(xs: Iterator[Int]) = {
   val maxNumSize = xs map (_.toString.size) reduceLeft (_ max _)
   "%"+maxNumSize+"d"
 }
}

 lazy val numFormat = this(0,0).numFormat(self flatMap (x => x) elements)
 override def toString = {
   def formatNumber(n: T) = numFormat format n
   ...

It would have been more appropriate to define that method inside a companion object, but this way is simpler. Note, as well, that “numFormat” became a visible property, so we can re-use all this logic inside LinearEquations.

Another place that needs fixing is inverse. We use the following rule:
 lazy val inverse: Option[Matrix[T]] =
   if (determinant == 0 || !isDivisibleBy(determinant))

Now, isDivisibleBy is implemented in terms of “%”, but that is just plain wrong for Double numbers. We could “fix” it by defining “%” to return 0, but that would make “%” act in a very unexpected way. So, instead, I’ll just define an “isDivisibleBy” operator inside Scalar:
 def isDivisibleBy(other: T): Boolean

The last problem, as far as I can see, is with the equality methods. You’ll get erasure warnings in them if you use “Matrix[T]” on the case statement of equals or inside asInstanceOf on canEqual. Instead, use “Matrix[_]”, to indicate you don’t care what type T is. Since we are doing a deepEquals, T will sort itself out.

The Scalar class and subclasses for Int and Double look like this:
abstract class Scalar[T](self: T) {
 def absolute: T
 def +(other: T): T
 def -(other: T): T
 def /(other: T): T
 def %(other: T): T
 def *(other: T): T
 def numFormat(xs: Iterator[T]): String
 override def numberSign: String
 def isDivisibleBy(other: T): Boolean
}

class IntScalar(self: Int) extends Scalar(self) {
 override def absolute = self.abs
 override def +(other: Int) = self + other
 override def -(other: Int) = self - other
 override def /(other: Int) = self / other
 override def %(other: Int) = self % other
 override def *(other: Int) = self * other
 override def numFormat(xs: Iterator[Int]) = {
   val maxNumSize = xs.map(_.toString.size).foldLeft(0)(_ max _)
   "%"+maxNumSize+"d"
 }
 override def numberSign = if (self < 0) "-" else "+"
 override def isDivisibleBy(other: Int) = (self % other) == 0
}

class DoubleScalar(self: Double) extends Scalar(self) {
 override def absolute = self.abs
 override def +(other: Double) = self + other
 override def -(other: Double) = self - other
 override def /(other: Double) = self / other
 override def %(other: Double) = self % other
 override def *(other: Double) = self * other
 override def numFormat(xs: Iterator[Double]) = {
   val numbers = xs.toList
   val maxIntSize = (
     numbers
     .map(_.toString.takeWhile(c => c != '.' && c != ',').length)
     .foldLeft(0)(_ max _)
   )
   val maxDecimalSize = (
     numbers
     .map(_.toString.dropWhile(c => c != '.' && c != ',').length)
     .foldLeft(0)(_ max _)
   ) - 1
   "%"+maxIntSize+"."+maxDecimalSize+"f"
 }
 override def numberSign = if (self < 0) "-" else "+"
 override def isDivisibleBy(other: Double) = true
}

Note that we transform “xs” into a List inside DoubleScalar. That’s because we are iterating through it twice, which isn’t possible with an Iterator. Also note we added “absolute” and “numberSign”, which are used by LinearEquations.

The method “absolute” is not called “abs”, though, because “abs” is defined on RichInt, RichDouble, etc. So if we defined it for IntScalar, and then tried to use “abs” on an Int, the compiler would not know whether to use RichInt’s abs or IntScala’s abs.

We’ll also add the following two lines to the Matrix companion-object:
 implicit def intToScalar(n: Int): Scalar[Int] = new IntScalar(n)
 implicit def doubleToScalar(n: Double): Scalar[Double] = new DoubleScalar(n)

This way these two types, Int and Double, will automatically become available after importing “Matrix._”. The user can arbitrarily extend Matrix to cover any type, though, by creating a subclass of Scalar and defining an implicit conversion from the desired type to it.

Performance-wise, the boxing of the numeric types for each operation is detrimental, but it can probably be optimized by either the compiler or the JIT. In Scala 2.8 there will also be the option of marking a class “specialized”, which is creates specially optimized versions of a class for Java’s “primitive” types. I’m not sure it applies in this situation, though.

I’ll finish with the revised code for Matrix. If you have any questions or suggestions, please send them to me and I’ll try to address them. I hope you found this series useful!
class Matrix[T] private (private val self: Array[Array[T]])
                       (implicit toScalar: T => Scalar[T], intToT: Int => T) {
 import Matrix._

 val rows = self.size
 val cols = self(0).size

 private def _row(n: Int): Array[T] = self(n)
 private def _col(n: Int): Array[T] = self map (_(n))

 def row(n: Int): Array[T] = _row(n) map (x => x)
 def col(n: Int): Array[T] = _col(n)

 def apply(i: Int, j: Int): T =
   if (i >= rows || j >= cols || i < 0 || j < 0)
     throw new IndexOutOfBoundsException
   else
     self(i)(j)

 def update(row: Int, col: Int, newValue: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (i,j) =>
     if (row == i && col == j) newValue else this(i,j)))

 def update(what: Dimension, where: Int, newValue: Array[T]): Matrix[T] =
   what match {
     case Row => replaceRow(where, newValue)
     case Column => replaceCol(where, newValue)
   }
    
 def replaceCol(col: Int, newValue: Array[T]): Matrix[T] =
   new Matrix(createArrays(rows, cols, (i,j) =>
     if (col == j) newValue(i) else this(i,j)))

 def replaceRow(row: Int, newValue: Array[T]): Matrix[T] =
   new Matrix(createArrays(rows, cols, (i,j) =>
     if (row == i) newValue(j) else this(i,j)))

 override def equals(other: Any): Boolean = other match {
   case that: Matrix[_] =>
     that.canEqual(this) && self.deepEquals(that.self)
   case _ => false
 }

 def canEqual(other: Any): Boolean = other.isInstanceOf[Matrix[_]]
  
 def *(n: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (row, col) => this(row,col) * n))

 def /(n: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (row, col) => this(row,col) / n))

 def %(n: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (row, col) => this(row,col) % n))

 def +(other: Matrix[T]): Matrix[T] =
   if (rows != other.rows || cols != other.cols)
     throw new IllegalArgumentException
   else
     new Matrix(createArrays(rows, cols, (row, col) => this(row,col) + other(row,col)))

 def -(other: Matrix[T]): Matrix[T] =
   if (rows != other.rows || cols != other.cols)
     throw new IllegalArgumentException
   else
     new Matrix(createArrays(rows, cols, (row, col) => this(row,col) - other(row, col)))

 def *(other: Matrix[T]): Matrix[T] =
   if (cols != other.rows)
     throw new IllegalArgumentException
   else
     new Matrix(createArrays(rows, other.cols, (row, col) =>
       this._row(row) zip other._col(col) map Function.tupled(_*_) reduceLeft (_+_)
     ))

 def **(n: Int): Matrix[T] =
   if (rows != cols)
     throw new UnsupportedOperationException
   else n match {
     case 0 => unitMatrix(rows)
     case 1 => this
     case 2 => this * this
     case negative if negative < 0 =>
       (this ** negative.abs).inverse getOrElse (throw new UnsupportedOperationException)
     case odd if odd % 2 == 1 => this ** (odd - 1) * this
     case even => this ** (even / 2) ** 2
   }

 def toArray = Matrix.clone(self)

 def transpose = new Matrix(createArrays(cols, rows, (row,col) => this(col,row)))

 def cofactor(row: Int, col: Int) = new Matrix(createArrays(rows-1, cols-1, (i,j) =>
   this(i + (if (i < row) 0 else 1), j + (if (j < col) 0 else 1))))

 protected def sign(row: Int, col: Int): T = if ((col + row) % 2 == 0) 1 else -1

 lazy val determinant: T =
   if (rows != cols)
     throw new UnsupportedOperationException
   else rows match {
     case 1 => this(0,0)
     case 2 => this(0,0)*this(1,1) - this(1,0)*this(0,1)
     case n => (
       _row(0).zipWithIndex
       map Function.tupled((value, col) => value * cofactor(0, col).determinant * sign(0, col))
       reduceLeft (_+_)
       )
     }

 def minor(row: Int, col: Int) = cofactor(row, col).determinant

 lazy val adjugate: Matrix[T] = new Matrix(createArrays(cols, rows, (row, col) =>
   minor(col, row) * sign(col, row)
 ))

 def isDivisibleBy(n: T): Boolean =
   self flatMap (row => row) forall (_ isDivisibleBy n)

 lazy val inverse: Option[Matrix[T]] =
   if (determinant == 0 || !isDivisibleBy(determinant))
     None
   else
     Some(adjugate / determinant)

 lazy val numFormat = this(0,0).numFormat(self flatMap (x => x) elements)

 override def toString = {
   val numFormat = this(0,0).numFormat(self flatMap (x => x) elements)
   def formatNumber(n: T) = numFormat format n
   val top = rows match {
     case 1 => _row(0) map formatNumber mkString ("< ", " ", " >")
     case _ => _row(0) map formatNumber mkString ("/ ", " ", " \\") // Fix highlighter: "
   }
   val middle = rows match {
     case 1 | 2 => Nil
     case _ => self.toList.tail.init map (_ map formatNumber mkString("| "," "," |"))
   }
   val bottom = rows match {
     case 1 => Nil
     case _ => List(_row(rows - 1) map formatNumber mkString ("\\ ", " ", " /"))
   }
  
   top :: middle ::: bottom mkString "\n"
 }
}

object Matrix {
 import Matrix._
 implicit def toMatrix[T](m : Array[Array[T]])
                         (implicit toScalar: T => Scalar[T], intToT: Int => T) = Matrix(m)

 def apply[T](array: Array[Array[T]])
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   new Matrix(clone(array))
 def apply[T](rows: Int, cols: Int)
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   Matrix(rows, cols, 0)
 def apply[T](rows: Int, cols: Int, value: T)
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   new Matrix(createArrays(rows, cols, ((_,_) => value)))
 def apply[T](rows: Int, cols: Int, f: (Int,Int) => T)
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   new Matrix(createArrays(rows, cols, f))

 def unitMatrix[T](n: Int)(implicit toScalar: T => Scalar[T], intToT: Int => T) =
   Matrix[T](n, n, (row: Int,col: Int) => (if (row == col) intToT(1) else intToT(0)))

 protected def createArrays[T](rows: Int, cols: Int, f: (Int, Int) => T) =
   for((i: Int) <- (0 until rows).toArray)
     yield for((j: Int) <- (0 until cols).toArray)
       yield f(i,j)

 protected def clone[T](a: Array[Array[T]]) =
   createArrays(a.size, a(0).size, (row, col) => a(row)(col))
  
 sealed abstract class Dimension
 case object Row extends Dimension
 case object Column extends Dimension

 implicit def intToScalar(n: Int): Scalar[Int] = new IntScalar(n)
 implicit def doubleToScalar(n: Double): Scalar[Double] = new DoubleScalar(n)
}

class LinearEquations[T](val m: Matrix[T], val r: Matrix[T])
                       (implicit toScalar: T => Scalar[T], intToT: Int => T) {
 require(m.rows == r.rows && r.cols == 1)

 def maxColumnSize(matrix: Matrix[T], isAbs: Boolean): Int = (
   matrix.toArray
   flatMap (row => row)
   map (value => (if (isAbs) value.absolute else value).toString.length)
   reduceLeft (_ max _)
 )

 lazy val maxColsSize = m.cols.toString.length

 def numberSign(n: T) = " %s " format n.numberSign
 def formatConstant(n: T) = r.numFormat format n
 def formatCoefficient(n: T) = m.numFormat format n.absolute
 def formatUnknown(index: Int) = "x("+("%0"+maxColsSize+"d" format index)+")"

 // On Scala 2.8, replace drop(1) with tail and first with head below
 def formatLine(coefficients: Array[T],
                constant: T,
                printUnknown: Int => String) =
   coefficients
   .zipWithIndex
   .drop(1)
   .foldLeft(formatCoefficient(coefficients.first)+printUnknown(0))(
     (x,y) => x+numberSign(y._1)+formatCoefficient(y._1)+printUnknown(y._2)
   )+" = "+formatConstant(constant)

 def makeString(printUnknown: Int => String) = (
   for(row <- 0 until m.rows)
   yield formatLine(m.row(row), r(row,0), printUnknown)
 ).mkString("\n")
  
 override def toString = makeString(formatUnknown)

 def getUnknowns(u: Matrix[T]): Int => String =
   (index: Int) => " * "+(u.numFormat format u(index,0))

 lazy val solutionInverse: Option[Matrix[T]] =
   if (m.inverse == None)
     None
   else
     Some(m.inverse.get * r)

 def solveInverse =
   if (solutionInverse == None)
     "There is no unique solution"
   else
     makeString(getUnknowns(solutionInverse.get))

 lazy val solutionCramer: Option[Matrix[T]] = {
   val vector = r.toArray.flatMap(x => x)
   if (m.determinant == 0)
     None
   else
     Some(Matrix(
       for((col: Int) <- (0 until m.cols).toArray)
       yield for(row <- Array(0)) // Array[T](...) doesn't work, as it requires T <: AnyRef
         yield m.replaceCol(col, vector).determinant / m.determinant
     ))
 }
    
 def solveCramer =
   if (solutionCramer == None)
     "There is no unique solution"
   else
     makeString(getUnknowns(solutionCramer.get))
}