Scala Type Infix Operators

This post covers an interesting little corner of the Scala syntax: infix operators for types. I missed this corner when I first put together my Scala Syntax Primer. It is not in the "Programming in Scala" book (as of preprint 4), and is hardly mentioned anywhere else.

Let's start by backing up a bit and reviewing one of the syntax features of Scala. Scala syntax allows you to use operator characters such as + and * in method names and includes rules allowing you to specify things in a different order using different characters.

For example, you could define a right-associative operator ++: on your class Foo, then invoke it on an instance foo of class Foo with an integer argument, putting the instance of the right hand side of the operator because that operator is right-associative (since it ends with a colon):

class Foo() { def ++:(n:Int) = println(2*n) }
val foo = new Foo()
123 ++: foo

It turns out you can do something similar with types: if you define a higher-kinded type with two type parameters, you can then use that type name as an infix type operator. For example, the type specifier Pair[String,Int] can be written as String Pair Int. The following two lines are both valid and define equivalent vals:

val t1:String Pair Int = ("abc",123)
val t2:Pair[String Int] = ("abc",123)

This syntax looks odd when written this way for the Pair type. However, Scala lets you use operator characters for type names as well as for method names, so you could define a higher-kinded type named + or * and use it as an infix type operator. For example, you could make + an alias for Pair, then declare an abstract list of pairs of String and Ints like this:

type +[A,B] = Pair[A,B]
val pairlist:List[String + Int]

I have been looking for examples that use this feature, but it is a bit hard to come up with good search terms for this.

In section 3.2 on page 16 of the paper "Towards Equal Rights for Higher-Kinded Types" by Moors, Piessens and Odersky, July 2007, they discuss using Scala's type system to encode Church Numerals, along with a + type infix operator. Michael Dürig also has an implementation, from April of this year, of Church encoding of natural numbers using Scala types, with an addition operator implemented as a + type. He pushed it further, implementing a * (multiply) operator in a sequel to that entry.

So, is the ability to define a type infix operator a useful feature, or just a curiosity put in Scala to allow a bit of academic experimentation and playing with Church Numerals?

Turns out perhaps there actually is a practical use for Church Numerals and the + operator. Jesper Nordenberg has implemented an experimental units package with a composite type called Quantity that has slots for each unit and uses Church Numerals to represent the powers of the units in each slot. The * operation on unit-typed values uses the + type infix operator on the Church Numerals that represent the powers of the units. For example, a value with a unit of "meter" will have a Church Numeral of one in the length slot of the Quantity type. Multiplying a "meter" by another "meter" will use the + type infix operator to add the two Church Numerals to get a Church Numeral of two in the length slot of the resulting Quantity type, thus representing area (length squared). This means, as Jesper notes in his blog, that the different combinations of units can be checked at compile time, so that you can't, for example, assign a length to a time variable.

I asked on the Scala mailing list for additional examples of using a type infix operator, and got only one response, which was a pointer to a blog posting by Conal Elliot about functional linear maps. Conal is great at explaining things, but my Haskell knowledge and functional programming skills are not quite strong enough for me to breeze through his post. I'll have to spend more time to understand it. But he did use a type infix operator.

I would appreciate it if anyone can provide me with any more examples of type infix operators, especially in Scala.

Update 2009-03-12: Mitch Blevins has a nice use for "or" as a type infix operator in his stuttering-or implicit-conversion polymorphism, an improved implementation of the concept as compared to mine.