Covariant type occurs in invariant position
Lars Hupel
(almost) minimal code:
trait KList[+M[_]] {
type Transformed[N[_]] <: KList[N]
type Appended[N[X] >: M[X], T <: KList[N]] <: KList[N]
}
case class KCons[+M[_], +T <: KList[M]](tail: T) extends KList[M] {
type Transformed[N[_]] = KCons[N, T#Transformed[N]]
type Appended[N[X] >: M[X], L <: KList[N]] = KCons[N, T#Appended[N, L]]
}
Error messages:
<console>:20: error: covariant type T occurs in invariant position in
type [N[_]]KCons[N,T#Transformed[N]] of type Transformed
type Transformed[N[_]] = KCons[N, T#Transformed[N]]
<console>:21: error: covariant type T occurs in invariant position in
type [N[X] >: M[X], L <: KList[N]]KCons[N,T#Appended[N,L]] of type Appended
type Appended[N[X] >: M[X], L <: KList[N]] = KCons[N,
T#Appended[N, L]]
<console>:21: error: covariant type M occurs in invariant position in
type [X]>: M[X] <: Any of type N
type Appended[N[X] >: M[X], L <: KList[N]] = KCons[N,
T#Appended[N, L]]
The first two messages can be avoided when using "tail." instead of
"T#". I couldn't find any fix for the third one, though. I don't even
know what "in type [X]>: M[X] <: Any of type N" is supposed to mean.
Sébastien Bocq
This compiles:
trait KList[+M[_]] {
type Transformed[N[_]] <: KList[N]
}
type Transformed[N[_]] = KCons[A, N, T#Transformed[N]]
}
I'm not sure what appended is supposed to do but if you're still stuck you can search here for inspiration:
http://apocalisp.wordpress.com/2010/11/03/type-level-programming-in-scala-part-8b-klist%C2%A0basics/
Cheers,
Sébastien
Lars Hupel
thanks for your remarks.
> trait KList[+M[_]] {
> type Transformed[N[_]] <: KList[N]
> }
>
> case class KCons[A, +M[_], T <: KList[M]](head:M[A], tail: T) extends
> KList[M] {
> type Transformed[N[_]] = KCons[A, N, T#Transformed[N]]
> }
Indeed. This compiles because T is not covariant anymore. Unfortunately,
I rely on a covariant T at some places.
> I'm not sure what appended is supposed to do [...]
`KList[M]#Appended[N, T]` should be the type level computation of the
result type when appending a `KList[N]` at the end of a `KList[M]`
(where `N >: M`).
There is always the possibility to write those operations using external
proofs, but this is rather tedious which is why I want then to be
included in the class itself.
Regards
Lars
Sébastien Bocq
Sorry, I can't explain that compile error. I tried to bypass the variance but without much luck either. At least, it makes the problem more apparent. Here it seems to come from a limitation with the type inference.
trait KList[M[_]] {
type Transformed[N[_]] <: KList[N]
type Coerced[N[_] >: M[_]] <: KList[N]
def coerce[N[_] >: M[_]]:Coerced[N]
}
case class KCons[A, M[_], T <: KList[M]](head:M[A], tail: T) extends KList[M] {
type Transformed[N[_]] = KCons[A, N, T#Transformed[N]]
type Coerced[N[_] >: M[_]] = KCons[A, N, T#Coerced[N]]
def coerce[N[_] >: M[_]] = this.asInstanceOf[KCons[A, N, T#Coerced[N]]]
}
case class KNil[M[_]] extends KList[M] {
type Transformed[N[_]] = KNil[N]
type Appended[N[_] >: M[_], L <: KList[N]] = L
type Coerced[N[_] >: M[_]] = KNil[N]
def coerce[N[_] >: M[_]] = this.asInstanceOf[Coerced[N]]
}
trait Foo[A]
trait Bar[A] extends Foo[A]
type X = KCons[Int, Foo, KNil[Bar]#Coerced[Foo]] // Succeeds
type Y = KNil[Bar]#Coerced[Foo] // Fails
// type arguments [Foo] do not conform to type Coerced's type parameter bounds [N[_] >: M[_]]
--
Sébastien
HamsterofDeath
advanced type magic and the code below screams "just use a list, it
offers map and ++ methods" to me.
is the trait supposed to "drag a type along" as more elements are
appended? maybe i would see what this is good for if i knew the context
it's supposed to be used in?
HamsterofDeath
http://www.slideshare.net/djspiewak/high-wizardry-in-the-land-of-scala
slide 40
Lars Hupel
how you'd like to see it) which has a global type constructor `M` (like
`List` or `Option`) where all elements must be types produced by `M`.
For example, an `HList` would allow a list of `String`, `Option[Int]`,
... whereas a `KList[Option]` would not. See [1] for a motivation to do
that.
Lars Hupel
>
> type Y = KNil[Bar]#Coerced[Foo] // Fails
> // type arguments [Foo] do not conform to type Coerced's type parameter
> bounds [N[_] >: M[_]]
That's strange.
By the way, I tried implementing `append` by using implicit conversion,
but everything bites me again.
scala> class Foo[M[_]]
defined trait Foo
scala> implicit def enrichFoo[M[_], T <: Foo[M]](foo: T) = new { def
flyingDog = "swoosh" }
enrichFoo: [M[_], T <: Foo[M]](foo: T)java.lang.Object{def flyingDog:
java.lang.String}
scala> new Foo[Option]
res4: Foo[Option] = Foo@4f1d0f91
scala> res4.flyingDog
<console>:14: error: value flyingDog is not a member of Foo[Option]
res4.flyingDog
^
scala> enrichFoo(res4).flyingDog
<console>:14: error: inferred type arguments [Nothing,Foo[Option]] do
not conform to method enrichFoo's type parameter bounds [M[_],T <: Foo[M]]
enrichFoo(res4).flyingDog
Lars Hupel
import scala.annotation.unchecked._
trait KList[@uncheckedVariance +M[_]] {
type Appended[N[X] >: M[X], T <: KList[N]] <: KList[N]
}
case class KCons[@uncheckedVariance +M[_], +T <: KList[M]](tail: T)
extends KList[M] {
type Appended[N[X] >: M[X], L <: KList[N]] =
KCons[N, tail.Appended[N, L]]
}
This still gives me "covariant type M occurs in invariant position".