type parametrization or structural subtyping or

Question

Good day! I'm quite new to scala, so during development the following question was raised:

I want to describe class Tree[T], where T is type parameter. But T should be constrainted - it should have 2 methods: def key(): A, where A is some type, derived from method's implementation (!) and def union(x: T): T, where T is the same as type parameter. I suppose this constraint can be expressed in several ways:

1. defining two traits one with method key and other with method union (two traits is because of independent nature of these methods)
2. using structural subtyping
3. something else...

So how can I do it in each way? and do other ways exist?

Also it'll be good if it'll be easy to add these methods for simple types (like String, Int, etc).

Answer 1

You could define a structural type for key, but not for union. A structural type may not refer to abstract types defined outside itself. So this won't work:

trait Tree[T <: { def union(x: T): T }]

You may define a trait that elements of Tree must make available, though:

trait TreeVal[T] {
    type A
    def key: A
    def union(x: T): T
}

This can be used two ways. First, the classes must implement that interface, which puts a serious constrain on what classes can be used as keys. This would be like this:

trait Tree[T <: TreeVal[T]]

It could also be offered as an implicit conversion, like this:

class IntVal(v: Int) extends TreeVal[Int] {
    type A = Int
    def key: A = v
    def union(x: Int): Int = x + v
}
implicit def IntIsVal(v: Int): IntVal = new IntVal(v)

class Tree[T <% TreeVal[T]] // must be class, so it can receive parameters

This used what is called a view bound. Look that up for more information, but suffice to say you'll be able to treat anything that has an implicit conversion defined and in scope as if it were a TreeVal. For example:

class Tree[T <% TreeVal[T]](node: T, left: Option[Tree[T]], right: Option[Tree[T]]) {
    override def toString = "(%s < %s > %s)" format (left.getOrElse("o"), node.key, right.getOrElse("o"))
}

Alternatively, you can use it with the type class pattern, with a few changes:

trait TreeVal[T] {
    type A
    def key(v: T): A
    def union(x: T, y: T): T
}
class Tree[T : TreeVal]  // must be class, so it can receive parameters

The type class pattern uses context bounds. Look that up for more information. This style is generally preferred over the former style nowadays, because it is more flexible in a number of ways. Nevertheless, both will work.

In this case, one would use it like this:

implicit object IntVal extends TreeVal[Int] {
    type A = Int
    def key(v: Int) = v
    def union(x: Int, y: Int) = x + y
}

class Tree[T: TreeVal](node: T, left: Option[Tree[T]], right: Option[Tree[T]]) {
    val treeVal = implicitly[TreeVal[T]]
    import treeVal._

    override def toString = "(%s < %s > %s)" format (left.getOrElse("o"), key(node), right.getOrElse("o"))
}

Answer 2

If you want to be able to “add” these methods to simple types, maybe you'd be better off using type classes. Read more about type classes in this question, and look at Kevin Wright's answer, which shows how to “add” a zero and an append method to Int and String.