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.为什么它无法推断出该类型参数,我该如何解决？

PS我尝试了以下操作,并让它工作,但这似乎非常不方便本来应该是一个方便的方法:

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.此外,据我了解,类型推断是故意不明确的,以便为将来的改进让路.

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

编辑:此类型成员方法的一个潜在限制是对G方法中的类型参数设置较少的约束Dijkstra.具体地,边界WeightedGraphOps和DirectedGraphOps不限制为具有相同的类型成员E.我不知道如何解决这个问题,而不会遇到您最初报告的类型推断问题.一种方法是这个问题中的模式:为什么这些类型的参数不符合类型细化？,但似乎Scala编译器无法处理它.

Edit2忽略上面的段落.正如Dylan在评论中提到的,对于这种钻石继承情况,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)
  }
}