Type of parameterization or structural subtyping or

Question

Good afternoon! I am new to scala, so the following question was raised during development:

I want to describe the Tree [T] class , where T is a type parameter. But T should be limited - it should have 2 methods: def key (): A , where A is a type obtained from the implementation of the method (!) And def union (x: T): T , where T matches the type parameter . I believe this restriction can be expressed in several ways:

• definition of two features using the key method and the other using the union method (two features are related to the independent nature of these methods)
• using structural subtyping
• something else...

So how can I do this in each case? and are there other ways?

It will also be nice if it is easy to add these methods for simple types (e.g. String, Int, etc.).

Answer 1

You can define a structural type for key , but not for union . A structural type may not be an abstract type defined outside itself. So this will not work:

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

You can define the trait that Tree elements should do, though:

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

This can be used in two ways. First, classes must implement this interface, which severely limits which classes can be used as keys. It will look like this:

 trait Tree[T <: TreeVal[T]] 

It can also be suggested as an implicit conversion, for example:

 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 the so-called view binding. Look at that for more information, but suffice it to say that you can handle everything that has an implicit conversion defined in scope, as if it were TreeVal . For instance:

 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 a template of type type 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 

A type type template uses context boundaries. See that for more information. This style, as a rule, is preferable to the previous style today, because it is more flexible in many respects. However, both will work.

In this case, you can use it as follows:

 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 “add” these methods to simple types, you might be better off using type classes. Read more about class types in this question and look at Kevin Wright's answer, which shows how to "add" the zero and append method to Int and String .

Answer 3

Structural types are implemented with Java reflection, so they will decrease performance. This is normal for script-like short programs or for initialization, but any heavy use can bring the program to your knees ...

So, I will choose the first option. You will need at least two type parameters. But you can use only one feature if you do not need finer granularity:

 trait Tree[T,A] { def key(): A def union( x: T ): T }