Higher-Kinded existential type

Question

I've been mulling over a design problem in a library I'm working on, and I realized that using existential types may allow me to change my design in a way that simplifies many parts of my library. However, I can't quite seem to get it to work.

It seems to me that myBuilder conforms to the type MultiSignalBuilder[E, R] forSome { type E[+X] >: Element[X] }, where Element[X] is MultiSignalElement[X], but the compiler says it does't. It seems to have to do the fact that E is a higher-kinded type. Why doesn't this work, and is there a way to fix it?

  class MultiSignalElement[+T] {
  }

  abstract class MultiSignal[+T] {
    type Element[+X] <: MultiSignalElement[X]

    val element : Element[T]

    def transform[R[+X] <: MultiSignal[X]](builder : MultiSignalBuilder[E, R] forSome { type E[+X] >: Element[X] }) : R[T] =
      builder.buildNew(element)
  }

  abstract class MultiSignalBuilder[-E[+X] <: MultiSignalElement[X], +R[+X] <: MultiSignal[X]] {
    def buildNew[T](element : E[T]) : R[T]
  }

  object myBuilder extends MultiSignalBuilder[MultiSignalElement, MultiSignal] {
    def buildNew[T](e : MultiSignalElement[T]) = new MultiSignal[T]() {
      type Element[+X] = MultiSignalElement[X]

      val element = e
    }
  }

  val multiSignal = new MultiSignal[Int] {
    type Element[+X] = MultiSignalElement[X]

    val element = new MultiSignalElement()
  }

  multiSignal.transform(myBuilder) //type error on this line
  multiSignal.transform[MultiSignal](myBuilder) //type error on this line

Answer 1

Let do step-by-step analysis.

First we have

def transform[R](builder : MultiSignalBuilder[E, R] forSome { type E[+X] >: Element[X] }) : Unit = { }

Which is equivalent to statement : there exists

type E[+X] >: Element[X]

For which we can define

def transform[E[+X] >: Element[X], R[+_]](builder : MultiSignalBuilder[E, R] ) : Unit = { }

Here we have an error

Error:(7, 18) covariant type X occurs in contravariant position in type [+X] >: MultiSignal.this.Element[X] of type E

This is something. You are expecting your mysterious existential covariant type should be a supertype of another covariant type. I think this is the first thing which is freaking the compiler. Lets change relation to subtyping

def transform[E[+X] <: Element[X], R[+_]](builder : MultiSignalBuilder[E, R] ) : Unit = { }

Now we have

Error:(7, 56) type arguments [E,R] do not conform to class MultiSignalBuilder's type parameter bounds [-E[+X] <: MultiSignalElement[X],+R[+X] <: MultiSignal[X]]

So we forgot to require subtyping of MultiSignal[X] out of R parameter.

Lets change it

 def transform[E[+X] <: Element[X], R[+X] <: MultiSignal[X]](builder : MultiSignalBuilder[E, R] ) : Unit = { }

Now

multiSignal.transform[MultiSignalElement,MultiSignal](myBuilder)

Is succesfully compiled.

Finally we could get back to existential version

def transform[R[+X] <: MultiSignal[X]](builder : MultiSignalBuilder[E, R] forSome {type E[+X] <: Element[X]}) : Unit = { }

With which

multiSignal.transform[MultiSignal](myBuilder)

Is succesfully compiled.

Sadly

multiSignal.transform(myBuilder)

Still is not compiled. I think there is too much type relations to resolve for the compiler.