Mencampur parameter tipe dan tipe abstrak dalam skala

Saya mencoba menggunakan jawaban pertanyaan sebelumnya untuk mengimplementasikan grafik kecil perpustakaan. Idenya adalah untuk menganggap grafik sebagai koleksi, di mana simpul membungkus elemen koleksi.

Saya ingin menggunakan tipe abstrak untuk mewakili tipe Vertex dan Edge (karena keamanan tipe) dan saya ingin menggunakan parameter tipe untuk mewakili tipe elemen koleksi (karena saya ingin mendefinisikannya saat instantiasi dengan mudah).

Namun, ketika mencoba contoh paling dasar yang dapat saya pikirkan, saya mengalami kesalahan kompilasi. Berikut ini contohnya:

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
  }

}

Dan inilah implementasi dasarnya:

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

}

Saat mencoba mengkompilasi, saya mendapatkan:

/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

Saya sama sekali tidak tahu arti dari kesalahan ini... Namun, jika saya mengkhususkan tipe T dalam implementasinya (class SimpleGraphKind extends GraphKind[Int] saya hanya mendapatkan kesalahan pertama.

Apakah Anda punya ide?


types generics scala abstract-type
person paradigmatic    schedule 14.01.2010    source sumber
comment
Bisakah Anda menjelaskan mengapa Anda ingin grafik menjadi kumpulan?   -  person Randall Schulz    schedule 14.01.2010
comment
Salah satu penerapan perpustakaan ini adalah mengimplementasikan sejenis automata seluler pada grafik (yang lainnya adalah penelitian jaringan kompleks). Mungkin menyenangkan untuk mengakses secara langsung objek Sel yang ada di dalam simpul... Tetapi jika Anda memiliki ide solusi tanpa grafik sebagai fitur kumpulan, saya juga tertarik.   -  person paradigmatic    schedule 14.01.2010
comment
Saya masih tidak yakin saya melihat hubungannya. Bagaimana Anda melihat perpustakaan grafik Anda dibedakan dari, katakanlah, JGraphT? Apakah ini pendekatan fungsional terhadap grafik?   -  person Randall Schulz    schedule 14.01.2010
comment
JGraphT (atau Jung) tidak mengikat tipe simpul dan tepi. Jadi, Anda harus mengandalkan objek grafik untuk melakukan operasi grafik. Sebaliknya, menurut saya lebih alami memanipulasi objek tepi dan titik secara langsung (misalnya saya lebih suka vertex1.connectTo(vertex2) atau vertex1 -> vertex2 daripada graph.connect( vertex1, vertex2). Vertex dapat berisi logika atau hanya menjadi proksi ke objek grafik, bergantung pada implementasinya.   -  person paradigmatic    schedule 15.01.2010

Jawaban (2)


arrow_upward
11
arrow_downward

Kompilasi ini dengan -explaintypes menghasilkan:

<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

Sekarang, saya hendak menulis Saya tidak mengerti bagaimana T <: T bisa salah -- sepertinya T didefinisikan dua kali, dan tentu saja itulah masalahnya. Di Sini:

abstract class GraphKind[T] { 

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

  def newGraph(): G 

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

Oke, kelas GraphKind diparameterisasi dengan T dan tipe G harus berupa Graph[T]. Sekarang, kelas Graph juga diparameterisasi, dan parameternya juga disebut T. Agar tidak membingungkan, mari kita tulis ulang:

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

Perhatikan bahwa ini PERSIS SAMA dengan apa yang Anda tulis. Saya hanya menggunakan nama yang berbeda untuk parameter tipe, agar tidak tertukar dengan T yang menjadi parameterisasi GraphKind.

Jadi, inilah logikanya:

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

yang menyiratkan hal itu

Graph[T2] <: Graph[T]

Dan, karena Graph meluas Collection:

Collection[T2] <: Collection[T]

Namun tidak ada jaminan bahwa ini benar. Saya kurang paham kenapa masalah tidak muncul padahal warisan tidak ada. Memperbaiki:

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

Karena Vertex dan Graph akan diikat ke satu instance dari GraphKind, maka T akan ditetapkan ke apa pun yang telah ditentukan untuk instance tersebut. Misalnya:

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")
                ^
person Daniel C. Sobral    schedule 14.01.2010
comment
Terima kasih banyak. Harus saya akui saya malu karena saya melakukan kesalahan serupa ketika mempelajari obat generik di java 5 tahun yang lalu... - person paradigmatic; 15.01.2010
comment
Tidak perlu malu. Saya melakukannya juga, dan kemudian membenci diri saya sendiri karena melakukannya. Bukannya saya tidak tahu cara kerjanya, hanya saja menulis D[T] extends C[T] adalah hal yang wajar. - person Daniel C. Sobral; 15.01.2010
comment
Di sisi lain, -explaintypes adalah teman Anda. Diperlukan waktu untuk membiasakan diri, terutama karena tipenya berubah ketika berpindah dari posisi kovarian ke posisi kontra-varian. Namun, tidak ada yang seperti itu untuk kesalahan tipe yang rumit. - person Daniel C. Sobral; 17.01.2010

arrow_upward
1
arrow_downward

Tampaknya Vertex termasuk dalam graf tertentu dan hanya graf tersebut yang dapat direpresentasikan paling baik dalam sistem tipe dengan sifat Vertex yang bersarang di Graf tersebut. Apakah yang ingin Anda capai sesuai dengan struktur berikut?

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]
}
person Mitch Blevins    schedule 14.01.2010