Parameter fails to capture path-dependent type

Question
1

Hello,

Could some one explain why this does not work and how to make it work? Thanks!

Welcome to Scala 2.12.4 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_45).
Type in expressions for evaluation. Or try :help.

scala> trait Graph { type Node; def nodes: Seq[Set[Node]] }
defined trait Graph

scala> case class GraphWrap[G <: Graph](graph: G) { def nodesReversed: Seq[Set[G#Node]] = graph.nodes.reverse }
<console>:12: error: type mismatch;
 found   : Seq[Set[GraphWrap.this.graph.Node]]
 required: Seq[Set[G#Node]]
       case class GraphWrap[G <: Graph](graph: G) { def nodesReversed: Seq[Set[G#Node]] = graph.nodes.reverse }
                                                                                                      ^

scala>

Thanks!

Best, Oliver

2

Since G is not known to be a singleton type, the second bullet point of §3.5.1 “Equivalence” does not apply:

If a path p has a singleton type q.type, then p.type ≡ q.type.

Because this cannot be satisfied, graph.type ≢ G, and so graph.type#Node ≢ G#Node, graph.type#Node meaning graph.Node.

While it is true that graph.Node <: G#Node, since it occurs within the invariant position λ[α] = Seq[Set[α]], that conformance is insufficient to satisfy the expected type.

As for fixing it? One way would be

case class GraphWrap[G <: Graph, N](graph: G {type Node = N}) { def nodesReversed: Seq[Set[N]] = graph.nodes.reverse }
// tested with your example in 2.12.4

See also my Typelevel posts

1 Like
3

I see. Thanks for the detailed explanation.

Your solution compiles fine, but confuses IntelliJ, at least in the real
(not quite so simple) code.

I instead chose to cast the Set by casting all members, i.e.

def nodesReversed: Seq[Set[N]] =
graph.nodes.reverse.map(.map(.asInstanceOf[D#Node]))

Super ugly, but works.

4

Because graph.Node <: G#Node, you can write (going back to your original example’s variables)

case class GraphWrap[G <: Graph](graph: G) {
  def nodesReversed: Seq[Set[G#Node]] = graph.nodes.reverse.map(_.map(identity[G#Node]))
}

This does the same thing without the cast, works at least as well as your cast, but without the un-safety.

Generally you should never use asInstanceOf to implement an upcast. That’s what : is for.

Depending on your situation you might also write

  def nodesReversed: Seq[Set[graph.Node]] = graph.nodes.reverse

That works if graph is a public val in your original code, just as it is in your example. Its interface equivalence to what you originally declared is described in “Relatable variables” in one of the aforementioned posts. In other words, it works out when the caller knows that G is a singleton type, which is common.

This also works, but, you know, meh.

  def nodesReversed: Seq[Set[_ <: G#Node]] = graph.nodes.reverse

More broadly, I don’t think safety is worth sacrificing to placate a buggy IDE. Especially one that is so easily confused.