Mezclando parámetros de tipo y tipos abstractos en scala

Question

Estoy tratando de usar la respuesta de a preceding question para implementar una pequeña biblioteca de gráficos. La idea es considerar los gráficos como colecciones, donde los vértices envuelven los elementos de la colección.

Me gustaría utilizar tipos abstractos para representar los tipos Vertex y Edge (debido a la seguridad del tipo) y usar parámetros de tipo para representar el tipo de elementos de colección (porque quiero definirlos fácilmente en la creación de instancias).

Sin embargo, al intentar el ejemplo más básico en el que puedo pensar, estoy atascado con errores de compilación. Aquí está el ejemplo:

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 
    } 

} 

y aquí está el implementaciones básicas:

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 + ")" 
    } 

} 

Al intentar compilar, obtengo:

/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 

no tengo absolutamente ninguna idea del significado de estos errores ... Sin embargo, si especializo el tipo T en la implementación (class SimpleGraphKind extends GraphKind[Int] obtengo solo el primer error.

¿Tiene algunas ideas?

Answer 1

Compilación esto con -explaintypes rendimientos:

<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 

Ahora, yo estaba a punto de escribir No entiendo cómo puede haber T <: T falsa - es casi como T se definió dos veces, que, por supuesto, es todo el problema. Aquí:

abstract class GraphKind[T] { 

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

    def newGraph(): G 

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

Ok, clase GraphKind está parametrizado con T y escriba G debe ser un Graph[T]. Ahora, la clase Graph también está parametrizada, y su parámetro también se llama T. Para evitar confusiones, reescribámoslo:

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] 
    } 

Tenga en cuenta que esto es EXACTAMENTE IGUAL a lo que escribió. Solo estoy usando un nombre diferente para el parámetro de tipo, para que no se confunda con el T que está parametrizando GraphKind.

lo tanto, aquí está la lógica:

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

lo que implica que

Graph[T2] <: Graph[T] 

Y, debido a Graph extiende Collection:

Collection[T2] <: Collection[T] 

pero no hay ninguna garantía de que esto es cierto.No entiendo por qué el problema no aparece cuando la herencia no está presente. REVISIÓN:

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 + ")" 
    } 
} 

Desde Vertex y Graph se atado a una instancia de GraphKind, entonces T se fijará a lo que se definió para esa instancia. Por ejemplo:

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

Parece que la pertenencia de Vertex a un gráfico particular y solo a ese gráfico se puede representar mejor en el sistema de tipo con un rasgo de Vértice anidado en el Gráfico. ¿Lo que estás tratando de lograr se reunió con la siguiente estructura?

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] 
}