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):
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 specifierclass Foo() { def ++:(n:Int) = println(2*n) } val foo = new Foo() 123 ++: foo

`Pair[String,Int]`

can be written as `String Pair Int`

.
The following two lines are both valid and define equivalent vals:
This syntax looks odd when written this way for theval t1:String Pair Int = ("abc",123) val t2:Pair[String Int] = ("abc",123)

`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:
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.type +[A,B] = Pair[A,B] val pairlist:List[String + Int]

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.

## 6 comments:

I found an example of this being used in the wild. The Play! Framework's Anorm JDBC result set parsing library uses it in its SQL Parser.

Erem: I saw plenty of infix operators defined with "def" in that class, but I did not see a type infix operator, which would be defined with a "type" statement similar to the "+" infix operator in my blog post. If I missed it, please point out the specific type infix operator that you saw.

Shapeless uses type operators in several places.

See: https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/typeoperators.scala

Another example: https://github.com/djspiewak/parser-workshop/blob/master/src/main/scala/parser.scala

See the definition of

case class ~[+A, +B](a: A, b: B)

https://github.com/zzorn/ScalaQuantity also uses infix type operators for church numerals. This appears to be very similar to Jesper's approach.

See this:

https://github.com/pathikrit/scalgos/blob/master/src/main/scala/com/github/pathikrit/scalgos/Memo.scala#L21

and this:

https://github.com/pathikrit/scalgos/blob/master/src/main/scala/com/github/pathikrit/scalgos/Combinatorics.scala#L84-L91

It's the most beautiful I've seen.

Post a Comment