There are couple of similar questions here, I read them and found no answer that could get my code work. I suppose I hit a corner case that requires more precise type specification than normal.
My case in two words. I'd like to build very simple heterogeneous list example to deepen my understanding of scala language. There is limitation that I set to myself: no implicits in any form, just plain scala type system. Implicits could make many thing easier, but I'd like to try hard way.
I have already working code, but I'd like to improve it. Here it is:
sealed trait HList {
type Self <: HList
def self : Self
def prepend[H](head : H) = HCons[H, Self](head, self)
def ::[H](head : H) = prepend(head)
type Merge[X <: HList] <: HList
def merge[X <: HList](other : X) : Merge[X]
def :::[X <: HList](other : X) = other.merge[Self](self)
}
sealed trait HNil extends HList {
override type Self = HNil
override def self = this
override type Merge[X <: HList] = X
override def merge[X <: HList](other : X) : Merge[X] = other
}
case object HNil extends HNil
final case class HCons[H, T <: HList](head : H, tail : T) extends HList {
override type Self = HCons[H,T]
override def self = this
override type Merge[X <: HList] = HCons[H, T#Merge[X]]
override def merge[X <: HList](other : X) : Merge[X] = HCons(head, tail.merge(other))
}
The Merge
type constructors denotes the type result of appending two lists. It is needed to keep track of all nested types. Here is the result:
val x = "str" :: true :: HNil
val s : String = x.head
val b : Boolean = x.tail.head
val y = 0.5 :: 12 :: HNil
val d : Double = y.head
val i : Int = y.tail.head
val l = x ::: y
val r = y.merge(x)
val sl : String = l.head
val sb : Boolean = l.tail.head
val sd : Double = l.tail.tail.head
val si : Int = l.tail.tail.tail.head
val rd : Double = r.head
val ri : Int = r.tail.head
val rl : String = r.tail.tail.head
val rb : Boolean = r.tail.tail.tail.head
Now I've done with boring introductions. I afraid I had lost half of readers to that point. I wish I could make the code collapsed to single line.
So the real problem is the Self
type and self
method. They looks ugly, and I want to get rid of them. I believe f-bounded polymorphism could help me with it in natural way. I get the following code:
type HAny = X forSome {type X <: HList[X]}
sealed trait HList[Self <: HList[Self]] {this : Self =>
def prepend[H](head : H) = HCons[H, Self](head, this)
def ::[H](head : H) = prepend(head)
type Merge[X <: HList[X]] <: HAny
def merge[X <: HList[X]](other : X) : Merge[X]
def :::[X <: HList[X]](other : X) = other.merge[Self](this)
}
sealed trait HNil extends HList[HNil] {
override type Merge[X <: HList[X]] = X
override def merge[X <: HList[X]](other : X) : Merge[X] = other
}
case object HNil extends HNil
final case class HCons[H, T <: HList[T]](head : H, tail : T) extends HList[HCons[H,T]] {
override type Merge[X <: HList[X]] = HCons[H, T#Merge[X]]
override def merge[X <: HList[X]](other : X) : Merge[X] = HCons[H, T#Merge[X]](head, tail.merge(other))
}
The scala compiler produces error that give me very little insight:
[error] App.scala:23: type arguments [H,T#Merge[X]] do not conform to method apply's type parameter bounds [H,T <: SelApp1.this.HList[T]]
[error] override def merge[X <: HList[X]](other : X) : Merge[X] = HCons[H, T#Merge[X]](head, tail.merge(other))
[error] ^
[error] one error found
The prepend part transformed to f-bound polymorphism smoothly. The merge part produced error. I need to abstract over Merge
type, so I bounded it with HAny
existential type just like in the early example I've used HList
without any additional type specifications.
But in the latter case some type information is lost since the compiler complains about inappropriate types. So how could I define existential type to hold all type information required for building HCons
? Maybe I need more complex adjustments to transfer abstract types solution to f-bound variant?
You have to just rewrite HCons
, replacing T <: HList[T]
with T <: HAny
:
final case class HCons[H, T <: HAny](head : H, tail : T) extends HList[HCons[H,T]] { ... }