generics - Scala 无法推断出正确的类型参数

Question

背景信息:我目前正在尝试建立一个通用图形库，其中包括一些不同的搜索算法(我从 Dijkstra 开始)。我设置了一些特征来表示在某些类型的图中可以找到的方法(例如加权、有向):

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) = { ... }
}

在其他地方，我有一个类作为加权有向图的具体实现，我想在其上运行 Dijkstra 算法:

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

但是当我尝试测试它时:

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

问题:我在编译期间收到以下错误: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]]
我花了足够长的时间才注意到它正在将我的 Edge ( E ) 类型推断为 Nothing ，但我不明白为什么它无法成功推断它应该是 Edge 。为什么无法推断该类型参数，如何修复它？

附注我尝试执行以下操作，并使其正常工作，但这对于本应是一种方便的方法来说似乎非常不方便:

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

Answer 1

Daniel 可能是对的，现有的 Scala 类型推断器需要更多直接信息来确定 E 必须是 Edge。另外，据我了解，类型推断是故意未指定的，以便为 future 的改进让路。

无论如何，我认为您可以采用另一种设计方法来解决类型推断问题:使用类型成员而不是参数。我已经用下面的独立代码说明了我的意思。关键思想是类型 E 和 V 成为 GraphOps 类型的一部分，但它们仍然可以通过使用 < em>类型细化，如 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))
}

编辑: 这种类型成员方法的一个潜在限制是对方法 Dijkstra 中的类型参数 G 施加的限制较少。具体来说，边界 WeightedGraphOps 和 DirectedGraphOps 不限于具有相同类型成员 E。我不确定如何在不遇到您最初报告的类型推断问题的情况下解决此问题。一种方法是这个问题中的模式:Why do these type arguments not conform to a type refinement? ，但 Scala 编译器似乎无法处理它。

Edit2 忽略上面的段落。正如迪伦在评论中提到的，对于这个 diamond inheritance在这种情况下，Scala 很好地保证了类型 E 的一致性。例如，以下代码可以正常编译:

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