In my previous post I asked for a function *depth*, which takes an argument of type *M* and returns its structural depth.

Here is my solution:

object Puzzle {

class M[T]

abstract class Rep[T] {

def eval: int

}

implicit def toRep0[T](k: T) = new Rep[T] {

def eval = 0

}

implicit def toRepN[T](k: M[T])(implicit f: T => Rep[T]) = new Rep[M[T]] {

def eval = f(null.asInstanceOf[T]).eval + 1

}

def depth[T <% Rep[T]](m: T) = m.eval
def main(args: Array[String]) {
println(depth(0))
println(depth(new M[int]))
println(depth(new M[M[int]]))
println(depth(new M[M[M[int]]]))
}
}
[/sourcecode]
This is the same technique as discussed in my articles on implicit double dispatch. The function *depth* is applicable to any argument of type *T* which is implicitly convertible to type *Rep[T]*. *Rep[T]* instances implement a function *eval*, which returns the depth of the type this instance is representing. There are two function for implicit conversions: *toRep0* and *toRepN*. The *toRep0* function is responsible for the base case where the structural depth of the type of its argument is 0. The eval function thus returns 0 in this case. The *toRepN* function is responsible for the other cases where a *M*^{n + 1}[T] has to be converted into a *Rep[M*^{n + 1}[T]] (*M*^{k}[T] stands for *M[M[…[T]]]* having structural depth k). *toRepN* takes an implicit parameter *f* itself. This parameter is a conversion function for converting a *M*^{n}[T] into a *Rep[M*^{n}[T]] which is used for constructing *Rep[M*^{n + 1}[T]]. Since we can convert types of structural depths 0 and types of structural depth n + 1 when given a *Rep[T]* for *T* having structural depths n, we can – by induction – convert types of any structural depth.

The implementation of *eval* in *toRepN* is implemented in terms of the *eval* method of *Rep[T]*. However to access *Rep[T]* we need to apply *f* to a *T*. Since we don’t have an instance of *T* and since the actual instance does not matter, we simply pass *null* casted to *T*.

The technique employed here is a special case of the Code Follows Type pattern. The general idea is not to re-implement the structure of types in code, but to re-use the inherent information carried by types. While in Java this is only possible to a limited degree, Scala’s implicit conversions enable this technique even for recursive structures.

Credits are due to Henry Ware for pointing me to this paper about Scala’s higher kinds. Towards the end of the paper the authors show how to encode the church numerals as Scala types. The encoding plays nicely with the *depth* function. So – as I mentioned before in a comment – this might be a first, gentle step towards meta-programming with Scala. However, there are certain limitations I guess. I will write more about this later.