How do I create an object / singleton of a generic type in Scala?
In the below code, how can I convert EmptyTree
to object (Singleton)?
trait Tree[T] {
def contains(num: T): Boolean
def inc( num: T ): Tree[T]
}
class EmptyTree[T <% Ordered[T] ] extends Tree[T] {
def contains(num:T):Boolean = false
def inc(num:T):Tree[T] = {
new DataTree(num, new EmptyTree, new EmptyTree)
}
override def toString = "."
}
class DataTree[T <% Ordered[T] ](val x:T, val left:Tree[T], val right:Tree[T]) extends Tree[T] {
def contains(num:T):Boolean = {
if( num < x ) left.contains(x)
else if ( num > x ) right.contains(x)
else true
}
def inc(num:T):Tree[T] = {
if(num < x ) new DataTree(x, left.inc(num), right)
else if ( num > x ) new DataTree(x, left, right.inc(num))
else this
}
override def toString = "{" + left + x + right + "}"
}
val t = new DataTree(20, new EmptyTree[Int], new EmptyTree[Int])
//> t : greeting.Test.DataTree[Int] = {.20.}
val p = t.inc(10) //> p : greeting.Test.Tree[Int] = {{.10.}20.}
val a = p.inc(30) //> a : greeting.Test.Tree[Int] = {{.10.}20{.30.}}
val s = a.inc(5) //> s : greeting.Test.Tree[Int] = {{{.5.}10.}20{.30.}}
val m = s.inc(11) //> m : greeting.Test.Tree[Int] = {{{.5.}10{.11.}}20{.30.}}
source to share
Let me postpone the answer to Alexey. Here is the complete implementation with some code style improvements:
First, define your trait with confirmation of its covariance:
trait Tree[+T] {
def contains[U >: T : Ordering](num: U): Boolean
def inc[U >: T : Ordering](num: U): Tree[U]
}
Next define your object of subtype of all trees
case object EmptyTree extends Tree[Nothing] {
def contains[U >: Nothing : Ordering](num: U): Boolean = false
def inc[U >: Nothing : Ordering](num: U): Tree[U] =
DataTree(num, EmptyTree, EmptyTree)
override def toString = "."
}
Now change the implementation of your general case:
case class DataTree[T: Ordering](x: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
import Ordering.Implicits._
def contains[U >: T : Ordering](num: U): Boolean =
if (num < x) left.contains(x)
else if (num > x) right.contains(x)
else true
def inc[U >: T : Ordering](num: U): Tree[U] =
if (num < x) DataTree(x, left.inc(num), right)
else if (num > x) DataTree(x, left, right.inc(num))
else this
override def toString = "{" + left + x + right + "}"
}
You may be a little upset since I replaced yours Ordered
with Ordering
, but you should be aware that view limits are deprecated
source to share
You have to correct the generic argument because this is the only time you can provide it:
scala> trait A[T]
defined trait A
scala> object B extends A[Int]
defined object B
Obviously you want to reuse EmptyTree
for all types T
, so instead of defining A[SOMETYPE]
for each type, just use the lower type Nothing
:
scala> object B extends A[Nothing]
defined object B
This object can be used with any tree.
Exactly as Option[T]
implemented in Scala. This is how it is determined None
:
case object None extends Option[Nothing]
source to share
When saving generics, it is also possible to add an empty factory - as is done for Map and Vector. Of course, with such an implementation, it won't be a unique object instance for every creation, but when using the method, inc
it won't create new objects, it will just refer to itself.
object DataTree {
def empty[T <% Ordered[T]] = new Tree[T] {
def contains(num: T):Boolean = false
def inc(num: T): Tree[T] = {
new DataTree(num, this, this)
}
override def toString = "."
}
}
So, you can instantiate it like this:
val t = new DataTree(20, DataTree.empty[Int], DataTree.empty[Int])
source to share