Mischtyp Parameter und abstrakte Typen in scala

Question

Ich versuche, die Antwort von a preceding question zu verwenden, um eine kleine Grafikbibliothek zu implementieren. Die Idee besteht darin, Graphen als Ausschnitte zu betrachten, bei denen Eckpunkte Sammlungselemente umhüllen.

Ich möchte abstrakte Typen verwenden, um Vertex- und Edge-Typen darzustellen (wegen Typ Sicherheit) und ich möchte Typ-Parameter verwenden, um den Typ der Auflistungselemente darzustellen (weil ich sie bei Instanziierung einfach definieren möchte).

Wenn ich jedoch das grundlegendste Beispiel versuche, kann ich darüber nachdenken, dass ich mit Kompilierungsfehlern festhalte. Hier ist das Beispiel:

package graph 

abstract class GraphKind[T] { 

    type V <: Vertex[T] 
    type G <: Graph[T] 

    def newGraph(): G 

    abstract class Graph[T] extends Collection[T]{ 
    self: G => 
    def vertices(): List[V] 
    def add(t: T): Unit 
    def size(): Int 
    def elements(): Iterator[T] 
    } 

    trait Vertex[T] { 
    self: V => 
     def graph(): G 
     def value(): T 
    } 

} 

Und hier ist die grundlegende Implementierungen:

class SimpleGraphKind[T] extends GraphKind[T] { 

    type G = GraphImpl[T] 
    type V = VertexImpl[T] 

    def newGraph() = new GraphImpl[T] 

    class GraphImpl[T] extends Graph[T] { 
    private var vertices_ = List[V]() 
    def vertices = vertices_ 
    def add(t: T) { vertices_ ::= new VertexImpl[T](t,this) } 
    def size() = vertices_.size 
    def elements() = vertices.map(_.value).elements 
    } 

    class VertexImpl[T](val value: T, val graph: GraphImpl[T]) extends Vertex[T] { 
    override lazy val toString = "Vertex(" + value.toString + ")" 
    } 

} 

Wenn zu kompilieren versuchen, erhalte ich:

/prg/ScalaGraph/study/Graph.scala:10: error: illegal inheritance; 
self-type GraphKind.this.G does not conform to Collection[T]'s selftype Collection[T] 
    abstract class Graph[T] extends Collection[T]{ 
          ^
/prg/ScalaGraph/study/Graph.scala:33: error: illegal inheritance; 
self-type SimpleGraphKind.this.GraphImpl[T] does not conform to SimpleGraphKind.this.Graph[T]'s selftype SimpleGraphKind.this.G 
    class GraphImpl[T] extends Graph[T] { 
         ^
/prg/ScalaGraph/study/Graph.scala:36: error: type mismatch; 
found : SimpleGraphKind.this.VertexImpl[T] 
required: SimpleGraphKind.this.V 
    def add(t: T) { vertices_ ::= new VertexImpl[T](t,this) } 
           ^
/prg/ScalaGraph/study/Graph.scala:38: error: type mismatch; 
found : Iterator[T(in class SimpleGraphKind)] 
required: Iterator[T(in class GraphImpl)] 
    def elements() = vertices.map(_.value).elements 
             ^
/prg/ScalaGraph/study/Graph.scala:41: error: illegal inheritance; 
self-type SimpleGraphKind.this.VertexImpl[T] does not conform to SimpleGraphKind.this.Vertex[T]'s selftype SimpleGraphKind.this.V 
    class VertexImpl[T](val value: T, val graph: GraphImpl[T]) extends Vertex[T] { 
                   ^
5 errors found 

Ich habe absolut keine Ahnung von der Bedeutung des diese Fehler ... Wenn ich jedoch den Typ T in der Implementierung spezialisiere (bekomme ich nur den ersten Fehler.

Haben Sie Ideen?

Answer 1

Kompilieren dies mit -explaintypes ergibt:

<console>:11: error: illegal inheritance; 
self-type GraphKind.this.G does not conform to Collection[T]'s selftype Collection[T] 
     abstract class Graph[T] extends Collection[T]{ 
             ^
    GraphKind.this.G <: Collection[T]? 
     Iterable[T] <: Iterable[T]? 
     T <: T? 
      T <: Nothing? 
      <notype> <: Nothing? 
      false 
      Any <: Nothing? 
       <notype> <: Nothing? 
       false 
      false 
      false 
      Any <: T? 
      Any <: Nothing? 
       <notype> <: Nothing? 
       false 
      false 
      false 
     false 
     false 
     GraphKind.this.Graph[T] <: Iterable[T]? 
     Iterable[T] <: Iterable[T]? 
      T <: T? 
      T <: Nothing? 
       <notype> <: Nothing? 
       false 
       Any <: Nothing? 
       <notype> <: Nothing? 
       false 
       false 
      false 
      Any <: T? 
       Any <: Nothing? 
       <notype> <: Nothing? 
       false 
       false 
      false 
      false 
     false 
     false 
    false 

Nun, ich war über schreiben Ich verstehe nicht, wie T <: T falsch sein kann - es ist fast wie T ist zweimal definiert, Das ist natürlich das ganze Problem. Hier:

abstract class GraphKind[T] { 

    type V <: Vertex[T] 
    type G <: Graph[T] 

    def newGraph(): G 

    abstract class Graph[T] extends Collection[T]{ 

Ok, Klasse GraphKind mit T parametriert und geben G muss ein Graph[T] sein. Jetzt ist auch die Klasse Graph parametrisiert und ihr Parameter wird auch T genannt. Um Verwechslungen zu vermeiden, lassen Sie uns es umschreiben:

abstract class Graph[T2] extends Collection[T2]{ 
    self: G => 
    def vertices(): List[V] 
    def add(t: T2): Unit 
    def size(): Int 
    def elements(): Iterator[T2] 
    } 

Beachten Sie, dass dies genau das ist, was Sie geschrieben haben. Ich verwende nur einen anderen Namen für den Typparameter, damit er nicht mit der T verwechselt wird, die GraphKind parametrisiert.

So, hier ist die Logik:

G <: Graph[T] 
Graph[T2] <: Collection[T2] 
Graph[T2] <: G // self type 

, die das

Graph[T2] <: Graph[T] 

Und weil Graph erstreckt Collection bedeutet:

Collection[T2] <: Collection[T] 

Aber es gibt keine Garantie, dass dies wahr.Ich verstehe nicht, warum das Problem nicht auftritt, wenn die Vererbung nicht vorhanden ist. Fix:

abstract class GraphKind[T] { 

    type V <: Vertex 
    type G <: Graph 

    def newGraph(): G 

    abstract class Graph extends Collection[T]{ 
    self: G => 
    def vertices(): List[V] 
    def add(t: T): Unit 
    def size(): Int 
    def elements(): Iterator[T] 
    } 

    trait Vertex { 
    self: V => 
     def graph(): G 
     def value(): T 
    } 

} 

class SimpleGraphKind[T] extends GraphKind[T] { 

    type G = GraphImpl 
    type V = VertexImpl 

    def newGraph() = new GraphImpl 

    class GraphImpl extends Graph { 
    private var vertices_ = List[V]() 
    def vertices = vertices_ 
    def add(t: T) { vertices_ ::= new VertexImpl(t,this) } 
    override def size() = vertices_.size 
    override def elements() = vertices.map(_.value).elements 
    } 

    class VertexImpl(val value: T, val graph: GraphImpl) extends Vertex { 
    override lazy val toString = "Vertex(" + value.toString + ")" 
    } 
} 

Da Vertex und Graph wird auf eine Instanz von GraphKind gebunden werden, dann T wird festgelegt werden, was auch immer es war für diese Instanz definiert. Zum Beispiel:

scala> new SimpleGraphKind[Int] 
res0: SimpleGraphKind[Int] = SimpleGraphKind@1dd0fe7 

scala> new res0.GraphImpl 
res1: res0.GraphImpl = line10() 

scala> res1.add(10) 

scala> res1.add("abc") 
<console>:9: error: type mismatch; 
found : java.lang.String("abc") 
required: Int 
     res1.add("abc") 
       ^

Answer 2

Es scheint, dass Vertex's, die zu einem bestimmten Graphen gehören, und nur dieser Graph am besten im Typsystem mit einer verschachtelten Vertex-Eigenschaft im Graph dargestellt werden kann. Ist das, was Sie zu erreichen versuchen, mit der folgenden Struktur erfüllt?

abstract class Graph[T] extends Collection[T] { 
    thisGraph: Graph[T] => 

    def newGraph: Graph[T] 
    def vertices: List[Vertex[T]] 
    def add(t: T): Unit 
    def size: Int 
    def elements: Iterator[T] 

    trait Vertex[T] { 
     def graph = thisGraph 
     def value: T 
    } 
} 

class SimpleGraph[T] extends Graph[T] { 
    private[this] var verts = List[Vertex[T]]() 

    def newGraph = new SimpleGraph[T] 
    def vertices = verts 
    def add(t: T) { verts ::= SimpleVertex(t) } 
    override def size = verts.size 
    override def elements = verts.map(_.value).elements 
    def iterator = elements // the "new" elements in 2.8 

    case class SimpleVertex[T](value: T) extends Vertex[T] 
}