generics - parameter - Scala no puede inferir los argumentos del tipo correcto

scala type

Question

Información de fondo: actualmente estoy tratando de configurar una biblioteca de gráficos genéricos que incluye algunos algoritmos de búsqueda diferentes (comencé con Dijkstra). Establecí algunos rasgos para representar los métodos que se encontrarían en ciertos tipos de gráficos (p. Ej., Ponderados, dirigidos):

trait GraphOps[V,E] { ... }
trait WeightedGraphOps[V,E] extends GraphOps[V,E] { ... }
trait DirectedGraphOps[V,E] extends GraphOps[V,E] { ... }
object GraphOps{
  def Dijkstra[V,E,G <: WeightedGraphOps[V,E] with DirectedGraphOps[V,E]](graph:G, start:V) = { ... }
}

En otro lugar, tengo una clase como la implementación concreta del gráfico dirigido y ponderado en el que quiero ejecutar el algoritmo de Dijkstra:

class GraphMap[T](...)
extends scala.collection.mutable.Map[Position,T]
with WeightedGraphOps[Position,Edge] with DirectedGraphOps[Position,Edge] { ... }

Pero cuando trato de probarlo:

val graph = new GraphMap[Int](...)
val (dist, prev) = GraphOps.Dijkstra(graph, Position(0,0))

Pregunta: Recibo el siguiente error durante la compilación: error: inferred type arguments [com.dylan.data.Position,Nothing,com.dylan.data.GraphMap[Int]] do not conform to method Dijkstra''s type parameter bounds [V,E,G <: com.dylan.data.WeightedGraphOps[V,E] with com.dylan.data.DirectedGraphOps[V,E]]
Me tomó suficiente tiempo darme cuenta de que está infiriendo que mi Edge ( E ) mecanografía como Nothing , pero no veo por qué no está logrando inferir correctamente que se supone que es Edge . ¿Por qué no se puede deducir ese parámetro de tipo y cómo puedo solucionarlo?

PD: Intenté hacer lo siguiente, y lo hice funcionar, pero esto parece terriblemente inconveniente para lo que se suponía que era un método de conveniencia:

type Helpful = WeightedGraphOps[Position,Edge] with DirectedGraphOps[Position,Edge]
val (dist, prev) = GraphOps.Dijkstra[Position,Edge,Helpful](graph, Position(0,0))

Answer 1

¿Por qué se supone que es Edge ? Si miras la declaración de Dijkstra , verás que ninguno de los parámetros hace referencia a E : (graph:G, start:V) . Entonces Scala tiene una pista de lo que se supone que es G , y de lo que se supone que es V No hay ningún parámetro que haga referencia a E

Answer 2

Es probable que Daniel tenga razón en que el invocador de tipo Scala existente necesita información más directa para descubrir que E debe ser Edge . Además, tengo entendido que la inferencia de tipo está intencionalmente infraespecificada para dar paso a futuras mejoras.

De todos modos, creo que puede adoptar otro enfoque para su diseño que resuelva el problema de inferencia tipo: use miembros de tipo en lugar de parámetros. He ilustrado lo que quiero decir con el código autónomo a continuación. La idea clave es que los tipos E y V GraphOps formar parte del tipo GraphOps , pero aún pueden aparecer como parámetros de tipo utilizando un refinamiento de tipo , como en el método Dijkstra .

trait GraphOps { type E; type V }
trait WeightedGraphOps extends GraphOps { }
trait DirectedGraphOps extends GraphOps { }
object GraphOps{
  def Dijkstra[V0, G <: (WeightedGraphOps{type V = V0})
                         with (DirectedGraphOps{type V = V0})]
      (graph:G, start:V0) = { }
}

case class Position(x: Int, y: Int)
case class Edge()

case class GraphMap[T]() extends WeightedGraphOps with DirectedGraphOps {
  type E = Edge
  type V = Position
}

object Test {
  val graph = new GraphMap[Int]( )
  GraphOps.Dijkstra(graph, Position(0,0))
}

Editar : Una posible limitación de este enfoque de miembro de tipo es que pone menos restricciones en el parámetro de tipo G en el método Dijkstra . Específicamente, los límites WeightedGraphOps y DirectedGraphOps no están obligados a tener el mismo tipo de miembros E No estoy seguro de cómo resolver esto sin tropezar con el problema de inferencia tipo que informaste originalmente. Un enfoque sería el patrón en esta pregunta: ¿Por qué estos tipos de argumentos no se ajustan a un refinamiento de tipo? , pero parece que el compilador de Scala no puede manejarlo.

Edit2 Ignora el párrafo anterior. Como Dylan mencionó en los comentarios, para esta situación de herencia de diamantes , Scala garantiza la consistencia del tipo E Por ejemplo, lo siguiente compila bien:

trait GraphOps { type E; type V }
trait WeightedGraphOps extends GraphOps { def f(e: E) }
trait DirectedGraphOps extends GraphOps { def e: E }
object GraphOps{
  def Dijkstra[V0, G <: (WeightedGraphOps{type V = V0}) with (DirectedGraphOps{type V = V0})] (graph:G, start:V0) = {
    graph.f(graph.e)
  }
}