[modersky]

Yes, Tree[Top] would have been another way to model this. I wanted Tree[Nothing] to make clear that getting the type of an untyped Tree gives a Nothing, i.e. a run-time error. Getting a Top is not quite the same, but it is almost as good, since only a view things can be done with type Any in Scala.

EDIT: There's one thing I did not stress in the talk and that makes Nothing a more attractive choice than Top: We want to do copy on write on these trees. I.e. if we transform an untyped tree to a typed one using "withType", we want to be able to reuse the untyped tree and just set the type (unless somebody else had already added another type). If the tree is of type Tree[Nothing], we can do that safely, even if there are still shared references to the same node as an untyped Tree. Getting the type of the shared untyped tree will give a Nothing, and nothing can be done with it. But if the type would be a Top, we would be able to apply some operations on it, so the copy on write would be unsafe.