Encoding complex hierarchy rules in Scala types

Question

Say I have a complicated hierarchy of nodes in a tree structure, where certain types of nodes can only have children of certain (possibly many, possibly even including its own type) types.

Say we have a tree of employees and want to encode which types of employees can be bosses which other types.

One way is to define our Employee types, President, CTO, Manager, and their corresponding "Subordinate" types, PresidentSubordinate, CTOSubordinate, ManagerSubordinate. Then you could just extend *Subordinate on any Employee that they can be bosses of. Then you could do something like this:

sealed trait Employee

sealed trait PresidentSubordinate extends Employee
sealed trait VicePresidentSubordinate extends Employee
sealed trait CTOSubordinate extends Employee
sealed trait ManagerSubordinate extends Employee
sealed trait DeveloperSubordinate extends Employee

case class President(subordinates: Seq[PresidentSubordinate])

case class VicePresident(subordinates: Seq[VicePresidentSubordinates])
extends PresidentSubordinate

case class CTO(subordinates: Seq[CTOSubordinate]) 
extends PresidentSubordinate 
with VicePresidentSubordinate

case class Manager(subordinates: Seq[ManagerSubordinate]) 
extends VicePresidentSubordinate

case class Developer(subordinates: Seq[DeveloperSubordinate]) 
extends CTOSubordinate 
with ManagerSubordinate 
with VicePresidentSubordinate
with DeveloperSubordinate // Devs can be bosses of other devs

// Note, not all employees have subordinates, no need for corresponding type
case class DeveloperIntern() 
extends ManagerSubordinate 
with DeveloperSubordinate

This approach has worked out well for my half-dozen or so tree node types, but I don't know if this is the best approach as the number of types grows to 10, or 50 types. Maybe there is a much simpler solution, possibly it would be appropriate to use the pattern shown here. Something like

class VicePresidentSubordinate[T <: Employee]
object VicePresidentSubordinate {
  implicit object CTOWitness extends VicePresidentSubordinate[CTO]
  implicit object ManagerWitness extends VicePresidentSubordinate[Manager]
  implicit object DeveloperWitness extends VicePresidentSubordinate[Developer]
}

But then I'm not sure what the resulting case classes would look like, as this obviously doesn't compile:

case class VicePresident(subordinates: Seq[VicePresidentSubordinate]) extends Employee

Thanks for the help!

I have had this case once. It works well from the POV of the type system, but yes you get many artificial super-traits. Perhaps this becomes much simpler with union types in Dotty... — 0__, Dec 10 '15 at 22:07

Daniel Langdon · Accepted Answer · 2015-12-11T16:09:28.697

I'm not completely sure what properties you are looking for when you say "it works, but can I do something else?".

In the past I've done some thing like this and it may become useful to not do all of it in the type system. For instance, if your roles change dynamically you might want to have a single Employee class (with a "title" attribute and "subordinates") attributes and validate titles and dependencies at runtime, for instance, based on a config file.

If your structure is not dynamic then you can keep it in code. I would use abstract types to have fewer traits and represent the relationships you want. For example:

  // An employee has a name
  trait Employee {
    val name: String
  }

  // A subordinate has a manager
  trait Subordinate[M <: Manager[M]] {
    val manager: M
    manager.subordinates += this
  }

  // A manager has subordinates
  trait Manager[M <: Manager[M]] {
    val subordinates = mutable.Set[Subordinate[M]]()
  }

  // A middle level can both have a manager and manage others.
  trait Middle[M <: Manager[M], S <: Manager[S]] extends Manager[M] with Subordinate[S]

  // President does not have a manager, it manages only.
  case class President(name: String) extends Manager[President]

  // Some traits that report to the president.
  case class VicePresident(name: String, manager: President) extends Middle[VicePresident, President]
  case class CTO(name: String, manager: President) extends Middle[CTO, President]

  // An intern can't manage
  case class Intern(name: String, manager: CTO) extends Subordinate[CTO]

  // A simple test
  def main(args: Array[String]): Unit = {
    val bob = President("Bob")
    val alice = VicePresident("Alice", bob)
    val lucas = CTO("Lucas", bob)
    val sam = Intern("Sam", lucas)

    println(alice.manager)        // President(Bob)
    println(bob.subordinates)     // Set(CTO(Lucas,President(Bob)), VicePresident(Alice,President(Bob)))
    sam.subordinates              // Compiler error
  }

Note how keeping subordinates and manager pointers is done completely by the base traits. Objects get linked immediately for any new class you add!

Thanks, and then to allow classes to be subordinates of multiple types, just extend multiple subordinate traits? `case class Intern( /*... */) extends Subordinate[CTO] with Subordinate[VicePresident]` — Josh Lemer, Dec 11 '15 at 17:39
BTW, if this answered you, tried marked your question as answered to keep the site clean. — Daniel Langdon, Dec 11 '15 at 19:29

Encoding complex hierarchy rules in Scala types

1 Answers1