Pattern match on a generic type

Question

Why can't I pattern match against Node[T] ?

object Visitor {
  def inorder[T](root: Node[T]) : Unit = {
    root match {
    case End => return;
    case Node[T] => {
      if( root.left != null )
          inorder( root.left )

      println( root.toString );
      inorder( root.right );
    }
    case _ => return;
    }
  }
}

UPDATE:

The code is a verbatim copy from 99 scala problems

I'm getting this compile-time error:

BinaryTree.scala:25: '=>' expected but '[' found.
[error]         case Node[T] => {
[error]                  ^
[error] one error found

Line 25 points to the line

case Node[T] => {

Answer 1

You can bind the type parameter in some circumstances. Binding such type parameters can be used for typechecking the body of the pattern matching clause -- due to erasure, these bindings get erased and that means you cannot distinguish between them at runtime (such stuff is possible in the .NET CLR).

Your code does not seem to make use of the type though - one would need to see the definitions of Node, End. The simple way to achieve what you want is probably to just ignore what the type argument of Node[T] is. Below is an example that does this, with the correct syntax.

Note that if you want to write a pattern that matches on a type (generic or not), it always has the form v : T. If on the other hand, you match on case classes, then the pattern has the shapes C(p1...,pN). The language spec has all the details.

Instead of binding the type to a type variable a, we could also bind it to _, in order to stress that we do not make use of this type.

trait Tree[+T]
abstract class Node[+T] extends Tree[T] {
   def left: Tree[T]
   def right: Tree[T]
}
object End extends Tree[Nothing]

object Visitor {
  def inorder[T](root: Tree[T]) : Unit = {
    root match {
      case End => return;
      case node:Node[a] => {
        inorder( node.left ) // node.left has the type Tree[a]
        println( node.toString );
        inorder( node.right );
      }
      case _ => return;
    }
  }
}

Answer 2

Well, I run your code through the interpreter and I think it has nothing to do with type erasure. May be just some syntax error. Try this:

object Visitor {
  def inorder[T](root: Node[T]): Unit = {
    root match {
    case End => return;
    case n:Node[_] => {
      if( root.left != null )
          inorder( root.left )

      println( root.toString );
      inorder( root.right );
    }
    case _ => return;
    }
  }
}

You need to indicate the variable name that will be bound to the match, like n:Node[T]. That would give you a warning about type erasure, which you can remove by using n:Node[_]. The compiler can infer the type of root.left and root.right based on the type of root so type erasure doesn't really come into play here...

Note: I just checked the spec, the syntax for a type pattern is:

varid ':' TypePat
'_' ':' TypePat

It would help if you provide the actual error message from the compiler, and the definition of Node and End as otherwise we need to infer all those things.

---

Edit:

Assuming you're compiling http://aperiodic.net/phil/scala/s-99/tree.scala, there is indeed a syntax error in your code. Use n:Node[_]. Then you'll get some type errors. Here is what works for me:

import binarytree._
object Visitor {
  def inorder[T](root: Tree[T]) : Unit = {
    root match {
    case End => return;
    case n:Node[_] => {
      if( n.left != null )
          inorder( n.left )
      println( n.toString );
      inorder( n.right );
    }
    case _ => return;
    }
  }
}

Answer 3

In order to match the reified type at runtime for a generic in Scala, you need to use Manifests (q.v.) The way you wrote the code, the type is erased.

Answer 4

This behaviour is called type erasure. With Manifests you can make a workaround. See this question for more information.