I'd like to enrich a 'graph for scala' graph. For this purpose i've created an implicit value class:
import scalax.collection.mutable
import scalax.collection.edge.DiEdge
...
type Graph = mutable.Graph[Int, DiEdge]
implicit class EnrichGraph(val G: Graph) extends AnyVal {
def roots = G.nodes.filter(!_.hasPredecessors)
...
}
...
The problem lies with the return type of its methods, e.g.:
import ....EnrichGraph
val H: Graph = mutable.Graph[Int,DiEdge]()
val roots1 = H.nodes.filter(!_.hasPredecessors) // type Iterable[H.NodeT]
val roots2 = H.roots // type Iterable[RichGraph#G.NodeT] !!
val subgraph1 = H.filter(H.having(roots1)) // works!
val subgraph2 = H.filter(H.having(roots2)) // type mismatch!
Does the cause lie with fact that 'Graph' has dependent subtypes, e.g. NodeT? Is there a way to make this enrichment work?
What usually works is propagating the singleton type as a type parameter to EnrichGraph
. That means a little bit of extra boilerplate since you have to split the implicit class
into a class
and an implicit def
.
class EnrichGraph[G <: Graph](val G: G) extends AnyVal {
def roots: Iterable[G#NodeT] = G.nodes.filter(!_.hasPredecessors)
//...
}
implicit def EnrichGraph(g: Graph): EnrichGraph[g.type] = new EnrichGraph[g.type](g)
The gist here being that G#NodeT =:= H.NodeT
if G =:= H.type
, or in other words (H.type)#NodeT =:= H.NodeT
. (=:=
is the type equality operator)
The reason you got that weird type, is that roots
has a path type dependent type. And that path contains the value G
. So then the type of val roots2
in your program would need to contain a path to G
. But since G
is bound to an instance of EnrichGraph
which is not referenced by any variable, the compiler cannot construct such a path. The "best" thing the compiler can do is construct a type with that part of the path left out: Set[_1.G.NodeT] forSome { val _1: EnrichGraph }
. This is the type I actually got with your code; I assume you're using Intellij which is printing this type differently.
As pointed out by @DmytroMitin a version which might work better for you is:
import scala.collection.mutable.Set
class EnrichGraph[G <: Graph](val G: G) extends AnyVal {
def roots: Set[G.NodeT] = G.nodes.filter(!_.hasPredecessors)
//...
}
implicit def EnrichGraph(g: Graph): EnrichGraph[g.type] = new EnrichGraph[g.type](g)
Since the rest of your code actually requires a Set
instead of an Iterable
.
The reason why this still works despite reintroducing the path dependent type is quite tricky. Actually now roots2
will receive the type Set[_1.G.NodeT] forSome { val _1: EnrichGraph[H.type] }
which looks pretty complex. But the important part is that this type still contains the knowledge that the G
in _1.G.NodeT
has type H.type
because that information is stored in val _1: EnrichGraph[H.type]
.
With Set
you can't use G#NodeT
to give you the simpler type signatures, because G.NodeT
is a subtype of G#NodeT
and Set
is unfortunately invariant. In our usage those type will actually always be equivalent (as I explained above), but the compiler cannot know that.