Scala: value class X is added to the return type of its methods as X#

Question

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?

Answer 1

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.