How to properly define existential for a f-bound polymorphic type

Question

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?

Federico Pellegatta Federico Pellegatta · Accepted Answer · 2017-03-18T17:32:32

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]] { ... }

How to properly define existential for a f-bound polymorphic type

1 Answers