Trying to make a binary search tree.

In order for Node[Nothing] to be subtype of Tree[T], T has to be covariant which in turn puts constraints on the type of addValue

   sealed abstract class Tree[+T <% Ordered[T]] {
     def addValue[X >: T <% Ordered[X]](x: X): Tree[X]
   }

   case class Node[+T <% Ordered[T]](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
     override def addValue[X >: T <% Ordered[X]](x: X) = if (x < value) Node(value, left.addValue(x), right)
                                   else Node(value, left, right.addValue(x))
   }

   case object End extends Tree[Nothing] {
     def addValue[X <% Ordered[X]](x: X) = Node(x, End, End)
   }

On Mon, Mar 30, 2009 at 7:01 AM, Phil! Gold <phil_g@pobox.com> wrote:

I'm learning Scala, and I thought I might like to play with a binary
search tree.  I was thinking I'd do something analogous to this Haskell
code:

   data Tree a = End | Node a (Tree a) (Tree a)

   addValue :: (Ord a) => Tree a -> a -> Tree a
   addValue  End         x             = Node x End End
   addValue (Node y l r) x | x < y     = Node y (addValue l x) r
                           | otherwise = Node y l (addValue r x)

I figured I'd make End an object, somewhat analogous to Nil for List[T].
Unfortunately, that doesn't seem to work; the compiler complains that it's
not the right type.  Here's my code:

   sealed abstract class Tree[T <% Ordered[T]] {
     def addValue(x: T): Tree[T]
   }

   case class Node[T <% Ordered[T]](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
     override def addValue(x: T) = if (x < value) Node(value, left.addValue(x), right)
                                   else Node(value, left, right.addValue(x))
   }

   case object End extends Tree[Nothing] {
     def addValue[T <% Ordered[T]](x: T) = Node(x, End, End)
   }

And here's what the compiler tells me:

   tree.scala:11: error: type mismatch;
    found   : End.type (with underlying type object End)
    required: Tree[T]
       def addValue[T <% Ordered[T]](x: T) = Node(x, End, End)
                                                     ^
   tree.scala:11: error: type mismatch;
    found   : End.type (with underlying type object End)
    required: Tree[T]
       def addValue[T <% Ordered[T]](x: T) = Node(x, End, End)
                                                          ^
   two errors found

Changing `Node(x, End, End)` to `Node(x, End: Tree[T], End: Tree[T])`
doesn't help.

I'm using Scala 2.7.3.

What do I need to do to make this work?

--
...computer contrarian of the first order... / http://aperiodic.net/phil/
PGP: 026A27F2  print: D200 5BDB FC4B B24A 9248  9F7A 4322 2D22 026A 27F2

* James Iry [2009-03-30 07:08 -0700]:
> In order for Node[Nothing] to be subtype of Tree[T], T has to be covariant
> which in turn puts constraints on the type of addValue

That seems obvious in retrospect. I'd originally tried to make it
covariant, but ran into problems with addValue (as you observed) and
couldn't figure out how to fix those. (`X >: T` does it, which also seems
obvious in retrospect.)

Sorry for taking up people's time with such a simple question.