Extending existing data structure in Scala.

Question

I have a normal tree defined in Scala.

sealed abstract class Tree
object Tree {
  case class Node (...) extends Tree
  case class Leaf (...) extends Tree
}

Now I want to add a member variable to all nodes and leaves in the tree. Is it possible with extend keyword or do I have to modify the tree classes by adding [T]?

Update:
It seems that my question was misunderstood. Example should clear it up:

I need this Tree structure (actually something more complicated) have two Doubles in one context. In another context I need it to have one string. And yet in another context I need pure tree without any (additional) members. And I would like first two variants to be the third variant. Pseudocode:

DTree extends Tree with Touple2[Double, Double]
object DTree {
  case class Node (...) extends Tree.Node with Touple2[Double, Double]
  case class Leaf (...) extends Tree.Leaf with Touple2[Double, Double]
}

STree extends Tree with String
object DTree {
  case class Node (...) extends Tree.Node with String
  case class Leaf (...) extends Tree.Leaf with String
}

...

def f (t : Tree) { ... }

I want f to be able to handle all the trees.

Answer 1

You don't have to modify the tree class, since you could always create an intermediary subclass between tree and Node/Leaf:

abstract class ExtraMember[T](member:T) extends Tree

However, you can't achieve this by mixing in a trait to Node and Leaf if you want the extra member to be passed as a parameter.

Answer 2

Abstract classes may have constructors (traits may not), so you can just put the common elements in the abstract class Tree:

abstract
class Tree(te1: String, te2: Int)

case
class Node(...)
extends Tree(te1Arg, te2Arg)

and so on. Note that you have to supply the base class constructor parameters in the extends clause of the subclass definition.

Answer 3

If the member(s) you're adding are valid for all Tree objects (and subclasses) then the logical place is to put them in the Tree object itself.

You have two techniques available two you here. As mentioned by others, you can make these constructor params on the abstract class:

sealed abstract class Tree(prop1: String, prop2: Int)

case class Node(prop1: String, prop2: Int) extends Tree(prop1, prop2)

You can also make them regular vals/vars and specialise in the subclasses. This is arguably a better solution as it makes it easier to calculate these properties instead of simply daisy-chaining them via constructors:

sealed abstract class Tree {
  def prop1 : String
  def prop2 : Int
}

case class Node(a:String, b:Int) extends Tree {
  lazy val prop1 = "[" + a + "]"
  lazy val prop2 = b + 42
}

Using lazy vals here makes it easier to reason about the initialisation order of your object, it also avoids any computational overhead if the property is never used. This also shows nicely how methods in Scala can be implemented by properties, the so-called uniform access principle.

If you take this approach, then it's also possible to introduce the properties via a trait:

sealed abstract class Tree

trait TreeExtras {
  def prop1 : String
  def prop2 : Int
}

case class Node(a:String, b:Int) extends Tree with TreeExtras {
  lazy val prop1 = "[" + a + "]"
  lazy val prop2 = b + 42
}

You should also feel free to use self-types, etc. as appropriate.

Answer 4

If I understand you correctly, you want some of your tree nodes to have a type with a field of that type. I think an abstract type is what you're looking for. They're like generics, but better suited to sub-classing. Something like this.

sealed abstract class Tree

trait TypedTree {
  type T
  val value:T
}

Then which, when I modify your example, results in:

trait DTree extends TypedTree {
  type T = Touple2[Double, Double]
}
object DTree {
  case class Node (...) extends Tree.Node with DTree 
  case class Leaf (...) extends Tree.Leaf with DTree 
}

trait STree extends TypedTree {
  type T = String
}
object DTree {
  case class Node (...) extends Tree.Node with STree
  case class Leaf (...) extends Tree.Leaf with STree
}

This adds a level of indirection. But I get the feeling that you're conceptualizing something in one step where two are necessary.