斯卡拉未能推断出正确的类型参数 [英] Scala fails to infer the right type arguments

问题描述

背景信息：我目前正试图建立一个包含几种不同搜索算法的通用图库（我已经开始使用Dijkstra的）。我已经设置了几个特征来表示可以在某些类型的图表中找到的方法（例如加权，定向）：

 特征GraphOps [V，E] {...} 
 trait WeightedGraphOps [V，E]扩展GraphOps [V，E] {...} 
特性DirectedGraphOps [V，E] V，E] {...} 
对象GraphOps {
 def Dijkstra [V，E，G <：WeightedGraphOps [V，E] with DirectedGraphOps [V，E]]（graph：G， start：V）= {...} 
} 
  

其他地方，我有一堂课作为我想运行Dijkstra算法的加权有向图的具体实现：

  class GraphMap [T]（。 ..）
使用WeightedGraphOps [Position，Edge]与DirectedGraphOps [Position，Edge] {...} 
  c $ c> 

但是当我尝试测试时：



  val graph = new GraphMap [Int]（...）
 val（dist，prev）= GraphOps.Dijkstra（graph，Position（0,0））
  

问题：编译期间出现以下错误： error：推断类型参数[com.dylan.data.Position，Nothing，com.dylan.data.GraphMap [Int]]不符合方法Dijkstra的类型参数边界[V，E，G<：com.dylan.data.WeightedGraphOps [V ，E] with com.dylan.data.DirectedGraphOps [V，E]]

我花了很长时间才注意到它推断出我的边缘（ E ）类型为 Nothing ，但我不明白为什么它没有成功推断它应该是 Edge 。为什么它不能推断这个类型参数，我该如何解决它？

我尝试着做下面的事情，并且让它起作用，但这对于一种应该是一种便利方法的东西来说似乎非常不方便：

 类型有帮助= WeightedGraphOps [位置，边缘]与DirectedGraphOps [位置，边缘] 
 val（dist，prev）= GraphOps.Dijkstra [位置，边缘，有帮助]（图形，位置（0,0））
  

解决方案

Daniel可能是对的，现有的Scala类型推理器需要更直接的找出 E 必须是 Edge 的信息。此外，我的理解是，类型推断有意未被指定，以供将来改进。

无论如何，我认为您可以采取另一种方法来设计您的设计解决类型推断问题：使用类型成员而不是参数。我已经用下面的自包含代码说明了我的意思。关键的想法是类型 E 和 V 成为 GraphOps type，但它们仍然可以通过使用 type refinement 来表现为类型参数，如 Dijkstra 方法。

  trait GraphOps {type E;类型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]（）将DirectedGraphOps扩展为WeightedGraphOps {
 type E = Edge 
类型V =位置
} 
 
对象测试{
 val graph = new GraphMap [Int]（）
 GraphOps.Dijkstra（graph，Position（0,0） ）
} 
  

编辑：这种类型的成员方法是对方法 Dijkstra 中的类型参数 G 施加较少的约束。具体而言，限制 WeightedGraphOps 和 DirectedGraphOps 不限制为具有相同类型成员 E 。我不知道如何解决这个问题，而不会碰到你最初报告的类型推断问题。一种方法是这个问题的模式：为什么这些类型参数不符合类型优化？，但似乎Scala编译器无法处理它。 忽略上面的段落。正如Dylan在评论中提到的，对于这种钻石继承的情况，Scala很好地确保了键入 E 。例如，下面的代码编译得很好：



  trait GraphOps {type E;类型V} 
 trait WeightedGraphOps extends GraphOps {def f（e：E）} 
 trait DirectedGraphOps extends GraphOps {def e：E} 
 object GraphOps {
 def Dijkstra [V0， （DirectedGraphOps {type V = V0}）]（图：G，start：V0）= {
 graph.f（graph.e）$ b $ G } 
  




Background info: I'm currently trying to set up a generic graph library that includes a few different search algorithms (I've started with Dijkstra's). I've set up a few traits to represent methods that would be found in certain types of graphs (e.g. weighted, directed):

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

Elsewhere, I have a class as the concrete implementation of the weighted, directed graph that I want to run Dijkstra's algorithm on:

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

But when I try to test it out:

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

Question: I get the following error during compilation: 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]]
It took me long enough to notice that it's inferring my Edge (E) type as Nothing, but I don't see why it's failing to successfully infer that it's supposed to be Edge. Why is it failing to infer that type parameter, and how can I fix it?

P.S. I tried doing the following, and got it to work, but this seems horribly inconvenient for what was supposed to be a convenience method:

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

解决方案

Daniel is probably right that the existing Scala type inferencer needs more direct information to figure out the that E must be Edge. Also, it is my understanding that type inference is intentionally under-specified to make way for future improvements.

Anyway, I think you can take another approach to your design that will resolve the type inference problem: use type members rather than parameters. I've illustrated what I mean with self-contained code below. The key idea is that types E and V become part of the GraphOps type, but they can still be surfaced as type parameters by using a type refinement, as in the Dijkstra method.

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

Edit: One potential limitation of this type member approach is that puts less constraints on the type parameter G in method Dijkstra. Specifically, the bounds WeightedGraphOps and DirectedGraphOps aren't constrained to have the same type members E. I'm not sure how to resolve this without bumping into the type inference problem you originally reported. One approach would be the pattern in this question: Why do these type arguments not conform to a type refinement? , but it seems the Scala compiler can't handle it.

Edit2 Ignore the above paragraph. As Dylan mentioned in the comments, for this diamond inheritance situation, Scala nicely ensures the consistency of the type E. For example, the following compiles fine:

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

这篇关于斯卡拉未能推断出正确的类型参数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！