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.
Michid's Weblog 
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])
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
}
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
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.
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.
Great puzzle! Keep ’em comming!
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.
Correction:
def depth(a:Int) = a
It’s essentially Erkki’s solution. I would be interested to see what the correct answer is.
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.
The link to the Reflecting generics article came just at the right time. I remembered having read about this being possible but forgot when and where.
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?
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.
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.
[…] 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 […]
[…] 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 […]