How to define HList properly

Question
1

I had encountered problem while defining HTree. I could not express type properly so they could be deduced by compiler.

The HList definition is short and straightforward (I removed all extra functionality):

package object hlist {
  object Imports {
    import hlist.{HNil => HN}
    val HNil : HN = HN // use HNil trait as type instead of HNil.type
    type HNil = HN
    type HList = HAny
    type ::[H, T <: HList] = HCons[H, T]
  }

  type HAny = X forSome {type X <: HList[X]}
  sealed trait HList[Self <: HList[Self]] { this : Self =>
    type Merge[X <: HAny] <: HAny
    def merge[X <: HAny](other : X) : Merge[X]

    final type Cons[H] = HCons[H, Self]
    final def prepend[H](hd : H) : Cons[H] = HCons[H, Self](hd, this)
    final def ::[H](hd : H) : Cons[H] = HCons[H, Self](hd, this)
    final def :::[X <: HAny](other : X) = other.merge[Self](this)
  }

  sealed trait HNil extends HList[HNil] {
    override type Merge[X <: HAny] = X
    override def merge[X <: HAny](other : X) : Merge[X] = other
  }
  case object HNil extends HNil

  // hd instead head & tl instead tail to avoid global implicit conversion
  final case class HCons[H, T <: HAny](hd : H, tl : T) extends HList[HCons[H,T]] {
    override type Merge[X <: HAny] = HCons[H, tl.Merge[X]]
    override def merge[X <: HAny](other : X) : Merge[X] = HCons(hd, tl.merge(other))
  }
}

import hlist.Imports._

It works nice with objects when they are not annotated with types:

val a = 1 :: false :: HNil
val b = 0.2 :: "hi" :: HNil
val c = a ::: b
val s : String = c.tl.tl.tl.hd

But it works worse when types are not knows beforehand:

  def dup1[A, B](p : A :: B :: HNil) : A :: A :: B :: HNil =
    p.hd :: p.hd :: p.tl

  def dup2[A, T <: HList](p : A :: T) : A :: A :: T =
    p.hd :: p.hd :: p.tl

The first form compiles nicely, but the seconds fails with the following error:

[error] Proxy.scala:47: type mismatch;
[error]  found   : hlist.HCons[A,hlist.HCons[A,X]]
[error]  required: hlist.Imports.::[A,hlist.Imports.::[A,T]]
[error]     (which expands to)  hlist.HCons[A,hlist.HCons[A,T]]
[error]     p.hd :: p.hd :: p.tl
[error]          ^
[error] one error found

The X type used as erasure somehow make troubles.

I tried another way to define the :: type, but got errors on both dups:

type ::[H, T <: HList] = T#Cons[H]

[error] Proxy.scala:44: type mismatch;
[error]  found   : hlist.package.HCons[A,hlist.package.HCons[A,X]]
[error]  required: hlist.Imports.::[A,hlist.Imports.::[A,hlist.Imports.::[B,hlist.Imports.HNil]]]
[error]     (which expands to)  hlist.HCons[A,X]
[error]     p.hd :: p.hd :: p.tl
[error]          ^
[error] Proxy.scala:47: type mismatch;
[error]  found   : hlist.package.HCons[A,hlist.package.HCons[A,X]]
[error]  required: hlist.Imports.::[A,hlist.Imports.::[A,T]]
[error]     (which expands to)  hlist.HCons[A,X]
[error]     p.hd :: p.hd :: p.tl
[error]          ^

How it is supposed to by used correctly? Why type projection loses type info?

2

Just from taking a quick look I guess this can’t work the way you want it to:

type HAny = X forSome {type X <: HList[X]}

With HAny being just an existential it doesn’t make much sense to use T <: HAny to refer to an arbitrary HList. It is only a T <: X forSome { type X <: HList[X] } but what you want to express is (using the same verbose definition) T <: X forSome { type X <: HList[T] }.

Since the Self type is not needed from the outside it is easier to keep it internal to the HList as in https://github.com/szeiger/ErasedTypes/blob/master/src/main/scala/com/novocode/erased/HList.scala#L11

3

I tried the way you suggested. I relocated F-bound from type parameter to an abstract type:

sealed trait HList {
    type Self >: this.type <: HList

    type Merge[X <: HList] <: HList
    def merge[X <: HList](other : X) : Merge[X]

    final type Cons[H] = HCons[H, Self]
    final def prepend[H](hd : H) : Cons[H] = HCons[H, Self](hd, this)
    final def ::[H](hd : H) : Cons[H] = HCons[H, Self](hd, this)
    final def :::[X <: HList](other : X) = other.merge[Self](this)
  }

  sealed trait HNil extends HList {
    override type Self = HNil
    override type Merge[X <: HList] = X
    override def merge[X <: HList](other : X) : Merge[X] = other
  }
  case object HNil extends HNil

  // hd instead head & tl instead tail to avoid global implicit conversion
  final case class HCons[H, T <: HList](hd : H, tl : T) extends HList {
    override type Self = HCons[H, T]
    override type Merge[X <: HList] = HCons[H, tl.Merge[X]]
    override def merge[X <: HList](other : X) : Merge[X] = HCons(hd, tl.merge(other))
  }

  def dup2[A, T <: HList](p : A :: T) : A :: A :: T =
    p.hd :: p.hd :: p.tl

But dup2 still produces error:

[error] Proxy.scala:86: type mismatch;
[error]  found   : hlist2.HCons[A,hlist2.HCons[A,p.tl.Self]]
[error]  required: hlist2.Imports.::[A,hlist2.Imports.::[A,T]]
[error]     (which expands to)  hlist2.HCons[A,hlist2.HCons[A,T]]
[error]     p.hd :: p.hd :: p.tl
[error]          ^

Compare it with old error:

[error] Proxy.scala:86: type mismatch;
[error]  found   : hlist.HCons[A,hlist.HCons[A,X]]
[error]  required: hlist.Imports.::[A,hlist.Imports.::[A,T]]
[error]     (which expands to)  hlist.HCons[A,hlist.HCons[A,T]]
[error]     p.hd :: p.hd :: p.tl
[error]          ^

The problem remains the same despite redefining types.

There should be another way to define types coherently.