How to create object/singleton of generic type in Scala?

Question

In the code shown below, 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.}}

I don't see what this has to do with templates? Are you using some kind of template preprocessor to generate the code? In Scala, the only use of "template" I know of is as a hypernym for "class" and "trait". — Jörg W Mittag
– Jörg W Mittag, Commented Jun 8, 2015 at 9:53
Scala Generics and C++ Templates are very different. Plus, template already has a well-defined meaning in Scala, which has nothing to do with generics. Also, the tag wiki for template clearly says that applies only to either C++ or templating engines. — Jörg W Mittag
– Jörg W Mittag, Commented Jun 8, 2015 at 10:10

jjmerelo · Accepted Answer · 2015-10-24 09:12:09Z

7

Let me detalize Alexey's answer. Here is full implementation with some code style improvements:

First define your trait with aknowledgment 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 subtype-of-all-trees object

  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 your general case implementation:

  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 could be a little bit frustrated since I replaced your Ordered with Ordering, but you should know that view bounds are deprecated

edited Oct 24, 2015 at 9:12

jjmerelo

23.6k8 gold badges44 silver badges98 bronze badges

answered Jun 8, 2015 at 10:18

Odomontois

16.4k2 gold badges39 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

SunnyShah Over a year ago

Thanks a lot for your answer! Can you please help, Which book explains generics in Scala?

Odomontois Over a year ago

@SunnyShah the first one at official books list - in this chapter

yǝsʞǝla Over a year ago

Thanks, that's much more clear than what I was trying to write

yǝsʞǝla · Accepted Answer · 2015-06-08 09:56:38Z

1

You have to fix the generic argument because that's 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 of T, so instead of defining A[SOMETYPE] for each type just use bottom type Nothing:

scala> object B extends A[Nothing]
defined object B

This object can be used with any tree.

That's exactly how Option[T] is implemented in Scala. Here is how None is defined:

case object None extends Option[Nothing]

answered Jun 8, 2015 at 9:56

yǝsʞǝla

16.4k2 gold badges49 silver badges68 bronze badges

4 Comments

Jörg W Mittag Over a year ago

Unfortunately, DataTree is not covariant in T.

SunnyShah Over a year ago

I tried what you said, Here is an error I am getting. pastebin.com/GqBpJ81v

yǝsʞǝla Over a year ago

@JörgWMittag true, it's invariant. I don't see it as a problem unless he wants to allow subclasses as tree values. Then define it as trait tree[+T], it will work as well.

Jörg W Mittag Over a year ago

Well, if you just implement your solution, compilation of the OP's code fails with a variance error, that's why I mentioned it.

Ivan Klass · Accepted Answer · 2015-06-08 10:13:36Z

1

If keeping generics, also there is an option to add empty factory - like it's done for Map and Vector. Off course, with such an implementation it will not be a unique instance object for every creation, but when using inc method, it will not produce new objects, it will just reference 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 as following:

val t = new DataTree(20, DataTree.empty[Int], DataTree.empty[Int])

edited Jun 8, 2015 at 10:13

answered Jun 8, 2015 at 10:08

Ivan Klass

6,6223 gold badges32 silver badges28 bronze badges

1 Comment

SunnyShah Over a year ago

Thanks for your answer, Isn't is possible to have only one EmptyTree object?

Collectives™ on Stack Overflow

How to create object/singleton of generic type in Scala?

3 Answers 3

3 Comments

4 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related