Tuesday, September 8, 2009

Encoding functional dependencies in Scala

Update: Nevermind, I don't think this is useful. There's no advantage that I can see to this over using plain old abstract type members. Also, nothing stops us from defining two classes with the same type parameters in the same scope, but with different type constructors for converting to the dependent types. Original post follows.

Here is a way you can encode functional dependencies in Scala. I'm not sure if this technique has been described elsewhere, but I hadn't seen it so I thought I'd write it up.

Sometimes you will have a type Foo[X,Y], in which the choice of X uniquely determines Y (or more generally, in which the choice of one or more type parameters uniquely determines other type parameters). The example given on the Haskell page for fundeps is a multiplication typeclass: if both items being multiplied are matrices, the result is also a matrix; if both are scalars, the result is a scalar, if one is a matrix and the other is a scalar, the result is a matrix, etc. The types of the two things being multiplied uniquely determines the result type.

The basic idea for encoding this in Scala is to make the dependent type paramters into concrete type members of the class, dependent on an abstract type constructor that converts the supplied type parameters to the dependent type. An example:
object Fundep {
trait I[X] {
type XToZ[Q]
type Z = XToZ[X]
def z: Z
class J[X] extends I[X] {
type XToZ[Q] = String
def z = "hello"
class K[X] extends I[X] {
type XToZ[Q] = Int
def z = 42
def getZ[T<:I[_]](t: T): T#Z = t.z
The function getZ shows how users of the type can access the types that are derived from the supplied type parameters. We can call this with getZ(new K[Blah]) and it will return an Int; call it with getZ(new J[Blah]) and we get back a String!

The nice thing about this is that clients do not need to have knowledge of the type constructors for converting the known type parameters to those that are dependent. In contrast, consider the situation if we made the type constructor for doing the conversion into a type parameter of the class, like so: trait Foo[X,XToZ[_]] { type Z = XToZ[X] }. If we do this, all clients of the class are forced to know about the type constructor for converting X to Z, which they don't really care about - they just need to know what Z is, not how it is generated from X.

Note: this only actually works in 2.8. In 2.7.4, the example above crashes the compiler.

1 comment:

Unknown said...

Still, interesting idea...