erip erip - 26 days ago 6
Scala Question

How can I specialize a trait with a None-type constraint?

First, let me apologize if my question is unclear. I haven't quite picked up the Scala parlance yet, so I'm probably conflating terms. I think my example will be more clear, though.

I'm trying to create a trait

Hierarchical
which describes basically vertices in a graph -- any object which can have a list parents and a list of children.

More specifically:


  • 1) A
    Hierarchical
    may or may not have parents.

  • 2) If it does, the parents are
    Hierarchical
    .

  • 3) A
    Hierarchical
    will have children, which are also
    Hierarchical
    .



Here's my generic trait:

/*
Hierarchical takes two type parameters: Parent and Child.
These should be Hierarchicals with parameters Parent and Child as well.
*/
trait Hierarchical[Parent <: Hierarchical[Parent, Child],
Child <: Hierarchical[Parent, Child]] {

// parents must be passed by constructor lest they are treated as None.
// (Requirement 1, 2)
val parents: Option[List[Hierarchical[Parent, Child]]] = None

// children can be added, so mutability needed (Requirement 3)
var children: List[Hierarchical[Parent, Child]] = List()

def addChild(child: Child) = children ++= List(child)
}


A specialization to this is a "root" vertex, whose parents will not exist, so the type shouldn't be specified at all -- thusly, it is
None
. Here's my attempt to specialize the
Hierarchical
trait:

/*
A RootHierarchical has no parents. It does, however, have
children whose parents are RootHierarchicals and whose children
are Child.
A parent can be none (Requirement 1)
*/
trait RootHierarchical[Child <: Hierarchical[RootHierarchical, Child]]
extends Hierarchical[None.type, Child] {
override val parents = None
}


IntelliJ is happy with this, but the test I wrote is not compiling:

import org.scalatest.FlatSpec

class TestHierarchy extends FlatSpec {

"A Hierarchical object" should "be constructable" in {

/*
Create a dummy
*/
class DummyHierarchical(override val parents: List[DummyParentHierarchical])
extends Hierarchical[DummyParentHierarchical, DummyHierarchical]

class DummyParentHierarchical extends RootHierarchical[DummyHierarchical]

val dummyParent = new DummyParentHierarchical
val dummyChild = new DummyHierarchical(List(dummyParent))
dummyParent.addChild(dummyChild)

assert(dummyParent.parents.isEmpty)
assert(dummyParent.children.nonEmpty)
}
}


The error is here:

Error:(14, 11) type arguments [None.type,Child] do not conform to trait Hierarchical's type parameter bounds [Parent <: Hierarchical[Parent,Child],Child <: Hierarchical[Parent,Child]]
extends Hierarchical[None.type, Child] {


My question is this: how can I create this specialization? I know that
None.type
isn't a
Hierarchical
type, but how can I specialize for this?

Answer

After doing some brainstorming, I found that the types of the parents don't need to be specified -- they can be some arbitrary Hierarchical type and will have a default Nil.

Here's my implementation:

// T is the type of children -- they should be Hierarchicals.
trait Hierarchical[T <: Hierarchical[T]] {
  // The parents will be a list of some arbitrary Hierarchical
  val parents: List[Hierarchical[_]] = Nil
  var children: List[Hierarchical[T]] = List()
}

// Nodes that aren't root nodes will have parents specified by ctor
class NonRootNode(override val parents: List[Hierarchical[_]]) 
  extends Hierarchical[NonRootNode] {}

// Roots will have no way to update their parents.
class Root extends Hierarchical[NonRootNode] {
  final override val parents = Nil
}

Here's a small driver with some tests: Ideone it

Comments