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:

Still, interesting idea...

Post a Comment