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

Retentive

You do realize there's a graph library already, don't you? – Manion

Since I'm doing this for hobby, and since a few minutes of searching around didn't lead to a definitive answer, I figured I might as well put my own together. – Retentive

I'm curious what term did you exactly google? I tried 'scala graph library' and got this: code.google.com/p/scala-graphs doesn't it this for you? – Disavow

That project has no downloads and no source code. I searched for that exact term and did find that, along with the StackOverflow question mentioning that it was dead. – Retentive

The graph library linked below is being actively developed with hopes to be included in the Scala collections library. The release notes and roadmap looks promising. assembla.com/spaces/scala-graph/wiki – Kalman

Thanks for the link- I'll keep that on my radar – Retentive

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

Kalman

This helped me out, thanks! I'm not sure whether I should be worried about the lack of edge type constraint- I'm probably missing something, but I'm failing to create an object that mixes in both Ops types but with different E types. Is it even possible? – Retentive

Interesting. It sounds like the diamond problem ( en.wikipedia.org/wiki/Diamond_problem ) for types. For values, Scala's resolution to the diamond problem is that one value overrides the other, based on a linearization scheme. For types, I'm not surprised this is disallowed to avoid inconsistencies. – Kalman

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.

Manion

But couldn't a sufficiently clever Scala compiler figure it out at this call site? Knowing that graph has type WeightedGraphOps[Position, Edge] with ... basically fixes what E has to be to make the types work. – Kalman

It's supposed to be Edge because that's the type of the edges in the GraphMap. The implementation of Dijkstra's needs the type so I can't just leave it out. – Retentive

@Retentive I understand that you have a problem, I'm just trying to get you to understand type inference constrains better, so you'll write code more easily. The problem here is this: types are inferred from parameters. G is inferred from graph. What is the parameter E is supposed to be inferred from? It won't be inferred from the type constraints -- that is just what it is checked against, to what it is inferred from. – Manion

I see, so let's say my method signature was (graph:G, start:V, edgesToExclude:E*); so long as I call the method with some list of Edges, the inference should succeed, but if I called it with no edges excluded, I would still have the same problem as before, correct? – Retentive

@Retentive See this question for a way around the problem -- basically, parameterizing G so that E and V can be attached to the parameter. – Manion