Scala fails to infer the right type arguments

Question

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

Answer 1

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

Answer 2

Why is it supposed to be Edge? If you look at the declaration of Dijkstra, you'll see that none of the parameters make reference to E: (graph:G, start:V). So Scala has a clue what G is supposed to be, and what V is supposed to be. There's no parameter making reference to E.