Shapeless HList type checking

Question

I am using Shapeless and have the following method to compute the difference between two HLists:

  def diff[H <: HList](lst1: H, lst2:H):List[String] = (lst1, lst2) match {
    case (HNil, HNil)                 => List()
    case (h1::t1, h2::t2) if h1 != h2 => s"$h1 -> $h2" :: diff(t1, t2)
    case (h1::t1, h2::t2)             => diff(t1, t2)
    case _                            => throw new RuntimeException("something went very wrong")
  }

Since both parameters to the method take an H, I would expect HLists of different types to not compile here. For example:

diff("a" :: HNil, 1 :: 2 :: HNil)

Shouldn't compile but it does, and it produces a runtime error: java.lang.RuntimeException: something went very wrong. Is there something I can do to the type parameters to make this method only accept two sides with identical types?

Answer 1

One thing the other answers don't really address is the fact that this is entirely a type inference problem, and can be solved by simply breaking the parameter list in two:

def diff[H <: HList](lst1: H)(lst2: H): List[String] = (lst1, lst2) match {
  case (HNil, HNil)                 => List()
  case (h1::t1, h2::t2) if h1 != h2 => s"$h1 -> $h2" :: diff(t1)(t2)
  case (h1::t1, h2::t2)             => diff(t1)(t2)
  case _                            => throw new RuntimeException("bad!")
}

Which gives us what we want:

scala> diff("a" :: HNil)(1 :: 2 :: HNil)
<console>:15: error: type mismatch;
 found   : shapeless.::[Int,shapeless.::[Int,shapeless.HNil]]
 required: shapeless.::[String,shapeless.HNil]
       diff("a" :: HNil)(1 :: 2 :: HNil)
                           ^

This works (i.e. doesn't compile inappropriately and then blow up at runtime) because Scala's type inference for methods works on a per-parameter list basis. If lst1 and lst2 are in the same parameter list, H will be inferred to be their least upper bound, which generally isn't what you want.

If you put lst1 and lst2 in separate parameter lists, then the compiler will decide what H is as soon as it sees lst1. If lst2 doesn't have the same type, it blows up (which is what we're aiming for).

You can still break this by explicitly setting H to HList, but that's on your own head, I'm afraid.

Answer 2

Unfortunately, the base HList trait is unparameterized, and so in your method call H is just resolved to Hlist (which is indeed a supertype of any Hlist irrespective of the concrete element types). To fix this we have to change the definition somewhat, and rely instead on generalized type constraints:

def diff[H1 <: HList, H2 <: HList](lst1: H1, lst2: H2)(implicit e: H1 =:= H2): List[String] = (lst1, lst2) match {
  case (HNil, HNil)                 => List()
  case (h1::t1, h2::t2) if h1 != h2 => s"$h1 -> $h2" :: diff(t1, t2)
  case (h1::t1, h2::t2)             => diff(t1, t2)
  case _                            => throw new RuntimeException("something went very wrong")
}

Let's check:

scala> diff("a" :: HNil, 1 :: 2 :: HNil)
<console>:12: error: Cannot prove that shapeless.::[String,shapeless.HNil] =:= shapeless.::[Int,shapeless.::[Int,shapele
              diff("a" :: HNil, 1 :: 2 :: HNil)
                  ^

scala> diff("a" :: HNil, "b" :: HNil)
res5: List[String] = List(a -> b)

scala> diff("a" :: 1 :: HNil, "b" :: 2 :: HNil)
res6: List[String] = List(a -> b, 1 -> 2)

Now we could still "cheat" and explicitly set H1 and H2 to HList, and we're back to square one.

scala> diff[HList, HList]("a" :: HNil, 1 :: 2 :: HNil)
java.lang.RuntimeException: something went very wrong
  at .diff(<console>:15)
  at .diff(<console>:13)

Unfortunately I don't think this is easily solvable (it certainly is though, but I don't have a quick solution).

Answer 3

I could provide little bit more strict variant, that could not be tricked with explicit type parameters.

object diff {
    class Differ[T <: HList](val diff: (T, T) => List[String])

    def apply[T <: HList](l1: T, l2: T)(implicit differ: Differ[T]): List[String] = differ.diff(l1, l2)

    implicit object NilDiff extends Differ[HNil]((_, _) => Nil)

    implicit def ConsDiff[H, T <: HList : Differ] = new Differ[H :: T]({
      case (h1 :: t1, h2 :: t2) if h1 != h2 => s"$h1 -> $h2" :: diff(t1, t2)
      case (h1 :: t1, h2 :: t2) => diff(t1, t2)
    })
  }

It's definitely much more complex than above one, and i've tried to use Polymorphic function but could not end with proper recursion compiled.