[phischu]

The linked page links to a set of slides: http://www.slideshare.net/Odersky/compilers-are-databases

I have a question regarding slides 29 to 31.

The author says an untyped tree is represented as Tree[Nothing]. This leads to undesired variance behavior which is in turn overriden.

But there cannot be any instances of type Tree[Nothing] because there are no instances of type Nothing. Wouldn't an untyped tree be better represented as Tree[Unit]?

[modersky]

There can be instances of Tree[Nothing], just like there can be instances of List[Nothing]. It just means that in a scenario like this:

    class Tree[T] { def elem: T }

if t is a Tree[Nothing] then t.elem will not return normally (it might throw an exception instead).

[wereHamster]

Ok, so there are instances, which throw exceptions, fine, we're in Java land after all, where anything can happen. But why is Tree[Nothing] more useful than Tree[Unit]? Both contain the same amount of information (both Nothing and Unit convey zero bits of information), but one throws an exception while the other is safe at runtime.

[duhace]

Tree[Nothing] is a subtype of all Tree[_] types. This is similar to Nil in scala, which is really a singleton implementation of List[Nothing] or None, which is a singleton implementation of Option[Nothing]. Unit does not have this property, it is just a subtype of AnyVal/Any.

Basically, Tree[Nothing] allows you to indicate that a Tree is empty via the type system while still allowing you to use that same type to build an actual tree from. If Nil was List[Unit] instead of List[Nothing], 1 :: Nil would be a compile time error instead of a List[Int].

Oh, and Unit does have an implementation in scala called "()", so if you had a Tree[Unit] you would not be able to tell if it was actually empty or not. You can see this in scala with () :: Nil. It produces a non-empty List[Unit]. Nothing has no such implementation. As for the exceptions, there's not much you can do wrt that. What should happen if you call head on an empty List? That's a straight-out error. headOption or a match block is the safe way to deal with lists if you don't want to have exceptions ever.

[phischu]

Thank you.