## Puzzle: the depth of a type

4 03 2008

Here is a little Scala quiz I made up: say we have a type M[T]. Design a function depth which takes an argument of type M and returns its structural depth.

```class M[T]

def depth ...

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]]]))
}```

So with the right definition of depth in place the above code should print

```0
1
2
3```

I’m not sure if this can be done through pattern matching or using instanceOf. My solution does not rely on either of these.

### 14 responses

5 03 2008

Wow. I have to admit that I’m stumped. I thought maybe something like this, but erasure gets in the way:

def depth(a:Any) = 0
def depth[A](p:M[A]):Int = 1 + depth(p.asInstanceOf[A])

5 03 2008

It’s easy to do with pattern matching (or isInstanceOf) in case the type has a constructor parameter T and an extractor as well (but otherwise I don’t know how you would do it with those methods):

case class M[T](t: T)
def depth(o: Any): Int = o match {
case M(x) => 1 + depth(x)
case _ => 0
}

5 03 2008

Hehe… I think it’s a trick question since you didn’t define the interface for depth :)

implicit def m[T](t: M[T]) = 1
implicit def mm[T](t: M[M[T]]) = 2
implicit def mmm[T](t: M[M[M[T]]]) = 3

def depth(o: Int) = o.toString

5 03 2008

Oops… sorry, I missed the fact that indeed the depth function needs to take an argument of type M. In that case, I’m still stumped as well.

5 03 2008

Erkki,

Thanks for the pattern matching solution. I have yet to try it out. It looks definitely better than what I was able to come up with.

Your 2nd post: It is not a trick question. I didn’t define the interface for depth because this would have given away too much information already.

Your approach is a step into the right direction, it is too little general however. You don’t need to define a separate method for each depth.

5 03 2008

Great puzzle! Keep ‘em comming!

8 03 2008

Upon further reflection, I can think of two ways to do this.

Number one (and the “proper” way according to the Scala conventions) would be to use implicit type conversions like so:

def depth(a:Int) = 0
implicit def conv1[A](x:M[A]) = 1
implicit def conv2[A](x:M[M[A]]) = 2

It’s rigid, but the only way to do this is to change the compile-time behavior of a given line based on type parameters such that the runtime value changes. Since Scala doesn’t allow recursive implicit chaining of conversions (which would be nice, but ultimately self-defeating), we have to do it in this fashion. Implicit conversions are the only mechanism I’m aware of which allow changing of compile-time behavior based on a certain type.

The other solution would be to mess around with getGenericSuperclass() and such. I haven’t actually figured out how to swing this one (too late at night for that), but I’m fairly certain it could be done. http://www.artima.com/weblogs/viewpost.jsp?thread=208860

This has the advantage of being more flexible in that it can apply to n depth, but it’s also majorly hacky and anything but statically checked. The implicit solution will actually fail to compile if the conversion cannot take place. Additionally, the implicit solution does not depend upon 2.7.0.

No solution which depends upon pattern matching directly will succeed since type parameter values are not available at runtime, when pattern matching is resolved.

8 03 2008

Correction:

def depth(a:Int) = a

It’s essentially Erkki’s solution. I would be interested to see what the correct answer is.

8 03 2008

Daniel,

Thanks for you detailed analysis. You are quite right about the usage of implicit type conversion. My solution depends heavily on it. However there is a trick to use them recursively such that there is no need to have a method for each depth. I will post my solution sometime after the weekend. In the meanwhile: the solution is somehow buried in my implicit double dispatch articles.

9 03 2008

Your depth function plays nicely with type level Church encodings from the first Higher Kinds paper.

``` type plus[m[s[_], z], n[s[_], z], s[_], z] = n[s, m[s, z]]; type +[m[s[_], z], n[s[_], z]] = plus[m, n, M, Int];```

``` type _0[s[_], z]= z type _1[s[_], z]= s[z] type _2[s[_], z]= s[s[z]] // maybe nulls aren't /always/ evil def nvl[T]=null.asInstanceOf[T]; ```

``` println(depth(nvl[_2+_2])); // 4! ```

I think that’s really cool. It might even be useful for encoding array lengths and such. Hmm, can we do subtraction?

10 03 2008

Henry,

This is awesome! It definitely works. I think this might even be a first, gentle step towards meta programming. After all, the main body of work is done at compile time. The call to depth at runtime does only carry out a chain of function calls which was pre-determined by the compiler/type inferer.

So far I’ve only read the second Higher Kinds paper which does not talk about encoding of Church numerals. I definitely have to take a look at the first paper. Thanks for the link.

12 03 2008

Michid,

What you are doing might be different, though what I have is based on DoubleDispatchRevisited.

The run time hit is O(d) to go down the chain (unless hotspot sees that its a constant)— thats not great but its ok. It generates about 2d classes with long names like: …anonfun\$apply\$5\$\$anonfun\$apply\$6.. thats also ok. But my compilation time is way worse than linear… I can’t practically do chains deeper than 14 or so. Which makes me think the Chuirch encoding is impractical for metaprogramming.

However, it is possible to use the same depth technique with base2 or base10.

``` val b=One[Two[Three[Four[Five[Six[Seven[Eight[Nine[Zero[Stop]]]]]]]]]]; val i:Long=b.asLong; println(i); // 1234567890 ```

That makes representing any Int very practical. I think it might be possible to do addition with these, but I haven’t faced the compiler, yet.

12 03 2008

[…] the depth of a type (solution) 12 03 2008 In my previous post I asked for a function depth, which takes an argument of type M and returns its structural […]

13 08 2008

[…] with Scala Part I: Addition 18 04 2008 In the solution to a puzzle I posted earlier, I mentioned that the taken approach might be a first step towards […]