Sunday, June 28, 2009

Matrices 4

We have a reasonable Matrix class at this point, but it still has some deficiencies. There are a few common matrix operations we can add to it, and there are some problems related to the usability of the class. Let’s see them.

Equality

If you try “unitMatrixInt(2) == unitMatrixInt(2)”, you’ll get false as result. This happens because we did not provide an “equals” method, and the default “equals” method compares object references. Or, in other words, it tests if the objects are the same, not if the objects are equal. If that’s still unclear, see the following example:
`scala> unitMatrixInt(2) == unitMatrixInt(2)res8: Boolean = falsescala> val a = unitMatrixInt(2)a: teste.MatrixInt =/ 1 0 \\ 0 1 /scala> val b = unitMatrixInt(2)b: teste.MatrixInt =/ 1 0 \\ 0 1 /scala> val c = ac: teste.MatrixInt =/ 1 0 \\ 0 1 /scala> a == ares9: Boolean = truescala> a == bres10: Boolean = falsescala> a == cres11: Boolean = true`

Writing an equals method can be tricky, but I’m not going to discuss here why such a method must be written this or that way, as there are good references on the web. I usually recommend this one.

I will talk about the syntactical aspect of making such a method. First, though the examples show the method “==”, I keep talking about “equals”. That’s because “==”, as well as “!=”, in Scala is implemented in terms of the “equals” method. So if you want to change them, you implement “equals”.

Now, it’s not enough just to call it “equals”. It has to have the correct signature, which is to receive a single parameter of type Any, and return a Boolean. The method below will be good enough, with the addition of a canEqual method, and a small change in our class declaration:
`class MatrixInt private (private val self: Array[Array[Int]]) {...  override def equals(other: Any): Boolean = other match {    case that: MatrixInt =>      that.canEqual(this) && self.deepEquals(that.self)    case _ => false  }   def canEqual(other: Any): Boolean = other.isInstanceOf[MatrixInt]`

We changed the constructor so that self got declared as a “private val”, otherwise it won’t be visible even to other objects of the same class. We could also get a copy of a MatrixInt’s array representation, and compare against that, but that can make equals quite slow. To get such a copy, though, we would use the “toArray” method, which I thought I had presented in the first installment of these posts, but I now find I didn’t. Let’s correct that oversight:
`  def toArray = MatrixInt.clone(self)`

We produce a copy of the array, so that changes to it won’t affect this object. Anyway, now the test works as expected:
`scala> val a = unitMatrixInt(2)a: teste2.MatrixInt =/ 1 0 \\ 0 1 /scala> val b = unitMatrixInt(2)b: teste2.MatrixInt =/ 1 0 \\ 0 1 /scala> val c = ac: teste2.MatrixInt =/ 1 0 \\ 0 1 /scala> a == ares12: Boolean = truescala> a == bres13: Boolean = truescala> a == cres14: Boolean = true`

Updating

We also want to check to see it returns false for different matrices. To do that, though, we would like to produce a different matrix easily. Unfortunately, we have no way to do that. Well, we can generate unit matrices of different sizes, but if we just wanted to change a small value in one we have, we can do that.

Since our class is immutable, we do not expect it to actually change to something else, but when we do “1+1”, we do not change “1”, we just produce a new value. We can do the same thing, and enable individual cell changes in our matrix, like this:
`  def update(row: Int, col: Int, newValue: Int): MatrixInt =    new MatrixInt(createArrays(rows, cols, (i,j) =>      if (row == i && col == j) newValue else this(i,j)))`

Here are some tests, then:
`scala> val a = unitMatrixInt(2)a: teste3.MatrixInt =/ 1 0 \\ 0 1 /scala> a == unitMatrixInt(3)res20: Boolean = falsescala> a == unitMatrixInt(2)res21: Boolean = truescala> a == (a + a)res22: Boolean = falsescala> a == a*2res23: Boolean = falsescala> a == a * a // True! 1 == 1 * 1res24: Boolean = truescala> val b = a(1,0) = 1b: teste3.MatrixInt =/ 1 0 \\ 1 1 /scala> ares25: teste3.MatrixInt =/ 1 0 \\ 0 1 /scala> a == bres26: Boolean = false`

So, where’s “update”? It is actually used when declaring “b”. When you write “id(…) = value” in Scala, the compiler translates that to “id.update(…,value)”. So we could have also written this:
`scala> val b = a.update(1,0,1)b: teste3.MatrixInt =/ 1 0 \\ 1 1 /`

Let’s also make it easy to change a whole column or a whole row. We can already do “a.row(0)” or “c.col(1)”, so doing “a.row(0) = …” would be nice. Scala has something similar, in that any method called “field_=” will be called if you write “id.field = …”. Unfortunately, if we try that here it won’t work, because “id.field” is already the name of a method which takes a parameter (the row or column). If it did not take any parameters, it would work. As it is, we’ll just have to make do with something else:
`  def replaceCol(col: Int, newValue: Array[Int]): MatrixInt =    new MatrixInt(createArrays(rows, cols, (i,j) =>      if (col == j) newValue(i) else this(i,j)))       def replaceRow(row: Int, newValue: Array[Int]): MatrixInt =    new MatrixInt(createArrays(rows, cols, (i,j) =>      if (row == i) newValue(j) else this(i,j)))`

And we can use it like this:
`scala> val a = unitMatrixInt(3)a: teste6.MatrixInt =/ 1 0 0 \| 0 1 0 |\ 0 0 1 /scala> a.replaceCol(0, a.col(2))res39: teste6.MatrixInt =/ 0 0 0 \| 0 1 0 |\ 1 0 1 /`

There is one alternative, though, which I show below. I’m using the update method, and a symbol to identify what is being updated:
`  def update(what: Symbol, where: Int, newValue: Array[Int]): MatrixInt =    what match {      case 'row => replaceRow(where, newValue)      case 'col | 'column => replaceCol(where, newValue)      case _ => throw new IllegalArgumentException    }scala> val a = unitMatrixInt(3)a: teste7.MatrixInt =/ 1 0 0 \| 0 1 0 |\ 0 0 1 /scala> a('row, 1) = a.row(0)res41: teste7.MatrixInt =/ 1 0 0 \| 1 0 0 |\ 0 0 1 /scala> a('column, 2) = a.row(0)res42: teste7.MatrixInt =/ 1 0 1 \| 0 1 0 |\ 0 0 0 /`

Symbols are similar to String. The technical differences aren’t really much important – it’s their intent usage that differs. While strings are made to be shown to a user or received from them, a symbol is a piece of information exchanged between different parts of a program. They are very popular in some languages, but not so much on Scala.

One reason for their lack of popularity is that you don’t get any compile-time checks using them. If I misspelled “colunm” instead of “column”, the program would compile, and I’d get an exception at run-time – if I was lucky enough to catch it before the user.

Since we are using a statically typed language, we would like to catch such errors at compile-time. We can do that with Enumerations. Using a Scala enumeration is a bit more complex than other languages, as it’s not built in the language, but a library like anything else. It will provide just the checks we want, though.

First, we need to declare an object to be our enumeration. We’ll do this in the MatrixInt object-companion. We’ll also declare a type inside the object, to be used in our method declaration. It goes like this:
`  object Dimension extends Enumeration {    type Dimension = Value    val Row, Column = Value  }`

“Value”, here, is both a subclass of Enumeration and a method which will return a new instance of type Value each time it is called. These instances will always be different between them. Note that when you declare “val Row, Column = Value”, Scala converts this into “val Row = Value; val Column = Value”, so “Value” gets invoked twice. If “Value” was called only once, then Row would be equal to Column, which is not something we want.

We might like to import the contents of the Dimension object inside the class too, so that we can write “what: Dimension” instead of “what: Dimension.Dimension” (or even “what: MatrixInt.Dimension.Dimension”, if we hadn’t imported object MatrixInt’s contents already). Simple line:
`  import MatrixInt.Dimension._`

Now we can rewrite our method:
`  def update(what: Dimension, where: Int, newValue: Array[Int]): MatrixInt =    what match {      case Row => replaceRow(where, newValue)      case Column => replaceCol(where, newValue)    }`

It’s important that Row and Column were declared capitalized – the first letter is uppercase. If we used “row” and “column”, then the match would simply assign “what” to “row”, like it did to “even” and “odd” in “**”, and execute the first statement. Since we used capitalized identifiers, the case statement compares “what” to the value of Row, as if it was a literal, and assigns nothing.

Note also that we dropped the default case. One has to be careful, though, because the compiler won’t warn against missing case statements. Here are some usage examples:
`scala> a(Row, 2) = a.row(1)<console>:13: error: not found: value Row       a(Row, 2) = a.row(1)         ^scala> a(Dimension.Row, 2) = a.row(1)res1: teste.MatrixInt =/ 1 0 0 \| 0 1 0 |\ 0 1 0 /scala> import Dimension._import Dimension._scala> a(Row, 2) = a.row(1)res2: teste.MatrixInt =/ 1 0 0 \| 0 1 0 |\ 0 1 0 /`

Can we do something about not getting warnings about missing case statements? As a matter of fact, yes, we can. Let’s rewrite once again our method. This time, we’ll use a case objects. Let’s show it first, and then discuss it. First, we replace the whole Dimension object by this:
`  sealed abstract class Dimension  case object Row extends Dimension  case object Column extends Dimension`

Since we don’t have any nested declaration, we can do away with the extra import line. As for the rest… the update method doesn’t actually need any changes! The type, Dimension, has been declared. Row and Column are singleton objects, capitalized so that they can be used inside case statements as if they were literals.

There are two new things here. The “sealed” keyword, and the “case” keyword. Anyone reading about Scala has probably seen case classes. A case class is a class mostly like any other, but with a few methods automatically created by the compiler. A case object is similar to case class, and used instead of them when a case class would not declare any parameter in its constructor.

The “sealed” keyword means any subclass of “Dimension” must be declared in the same file as it. This way, the compiler can know, without doubt, all subclasses of Dimension, and, thus, perform checks when they get used in match statements. Leave “case Column” out of “update”, and you’ll get this warning:
`MatrixInt.scala:70: warning: match is not exhaustive!missing combination         Column    what match {    ^one warning found`

The usage won’t differ much either, and, in fact, won’t require any import beyond the object-companion’s contents:
`scala> val a = unitMatrixInt(3)a: teste3.MatrixInt =/ 1 0 0 \| 0 1 0 |\ 0 0 1 /scala> a(Row,2) = a.row(0)res15: teste3.MatrixInt =/ 1 0 0 \| 0 1 0 |\ 1 0 0 /`

You might wonder, then, why ever use an Enumeration instead of case objects. As a matter of fact, case objects do have advantages many times, such as here. The Enumeration class, though, has many Collection methods, such as elements (iterator on Scala 2.8), which returns an Iterator, map, flatMap, filter, etc.

We have seen three different ways of implementing our “update” method for rows and columns, each with different characteristics. The very thing that made symbols a bad choice for us – the inability to define what symbols are possible in advance – can be a necessary characteristic in other situations. This goes to the very heart of Scala’s philosophy: do not dictate a solution, but let the programmer find and use the optimal one for his needs.

In the next installment we’ll look into computing cofactors, determinants, inverse matrices and then use all that to solve linear equations. I’m afraid there won’t be almost anything new, but, on the positive side, it shouldn’t take long either, and we’ll end up with a reasonable complete Matrix class.

After that, we’ll look into branching Matrix into other types, and the trade-offs we must make.