CODEWITHSUNDEEP
scala
jts
jts

Reputation: 715

How to enforce types for a graph between nodes

I am trying to enforce a type relationship in a graph between a node and its parent. I have the following that does not compile on child.parents ::= this. Any comment would be welcomed

  trait TGraphNode {
    type NodeType <: TGraphNode
    var id = -1
    var parents = List[NodeType]()
    var children = List[TGraphNode]()

    def addChild(child: NodeType) {
      children ::= child
      child.parents ::= this
    }

    override def toString = "node-"+id+"->"+children
  }

Sorry - will add the compilation error next time. I am trying to achieve the following: imagine I have 2 nodes of type F and C - I want to enforce that C by construction can only have F as parent, however, the other way around I do not care. F could have C, D.. as children. So I want to capture that the ParentType can be overridden in a class implementing the trait.

class F extends TGraphNode ...
class B extends TGraphNode {
  type ParentType = F
}

Thanks

Upvotes: 3

Views: 118

Answers (2)

Didier Dupont
Didier Dupont

Reputation: 29528

The error message is

error: Type mismatch 
 found   : TGraphNode.this.type (with underlying type TGraphNode)
 required: child.NodeType
             child.parents ::= this

(please do not ommit that in your questions)

Your code states that a node may select the type it requires for its parents, with type variable NodeType. This type must conform to TGraphNode, but it may be much more restricted than that.

Given that, it is possible that the child added in addChild requires a type more restricted than this as its parent. It is proper that the compiler rejects that.

This is what the error message says : You put this in the parents list of child. this has type TGraphNode. But the parents list is a list of the NodeType of the child (child.NodeType) There is no guarantee than the type match.

I cannot comment further if you don't explain what you are trying to achieve.

After your edit :

You have to state that you will accept in addChild only a child that would accept this as a parent. It may be a little tricky, here is a possible way : 

def addChild[N](child: TGraphNode{type NodeType = N})
               (implicit thisAsParentOfChild : this.type <:< N) {
  children ::= child
  child.parents ::= thisAsParentOfChild(this)
}

Having done that, you may now do

class F extends TGraphNode {type NodeType = TGraphNode }
class C extends TGraphNode {type NodeType = F }
class X extends TGraphNode {type NodeType = TGraphNode } 

val f = new F
val c = new C
val x = new X

f.addChild(c) // ok 
x.addChild(f) // ok

x.addChild(c) // error: Cannot prove that x.type <:< F

If you don't know what the implicit parameter with type <:< does, have a look at What do <:<, <%<, and =:= mean in Scala 2.8, and where are they documented?

On second thought and reading bluenote suggestion, writing addParent is way simpler than addChild in your context (I believe this is the proper way to reverse chidren and parents) : 

def addParent(parent: NodeType) {
  parents ::= parent
  parent.children ::= this
}

Upvotes: 2

bluenote10
bluenote10

Reputation: 26530

My guess is, you just confused the types NodeType and TGraphNode. If I understood you correctly, the children could be of a subtype of TGraphNode. At least this is what the addChild function signature indicates and is maybe the more likely use case. So, the children must be of type NodeType but the parents can have the more general TGraphNode type, i.e.:

trait TGraphNode {
  type NodeType <: TGraphNode
  var id = -1
  var children = List[NodeType]()
  var parents = List[TGraphNode]()

  def addChild(child: NodeType) {
    children ::= child
    child.parents ::= this
  }

  override def toString = "node-"+id+"->"+children
}

Edit:

Ok, you really want it the other way around. Since the above mentioned version compiles, you could just reverse the definitions of children and parents to get what you want.

Upvotes: 1

Related Questions