Using union for subtracting HLists (i.e. filtering first one using second as the reference of unwanted types). See also https://gist.github.com/laughedelic/6808000 for the union construction.

HListSubtract.scala

object HListSubtract {

  // We use here this construction: https://gist.github.com/laughedelic/6808000
  import UnionHList._

  // Filters an HList `L`, trowing away any elements, that are in the given union `U`
  trait Filter[L <: HList, U] {
    type Out <: HList
    def apply(l: L): Out
  }

  object Filter extends LowPriorityFilter {
    implicit def fHNil[U] = new Filter[HNil, U] {
      type Out = HNil
      def apply(l: HNil) = l
    }

    // This is the case when the head is a subtype of the union
    implicit def fHConsWithoutHead[U, H : SubtypeOf[U]#is, T <: HList]
      (implicit t: Filter[T, U]) = new Filter[H :: T, U] {
        type Out = t.Out
        def apply(l: H :: T) = t(l.tail)
      }
  }

  trait LowPriorityFilter {
    implicit def fHConsAny[H, T <: HList, U]
      (implicit t: Filter[T, U]) = new Filter[H :: T, U] {
        type Out = H :: t.Out
        def apply(l: H :: T) = l.head :: t(l.tail)
      }
  }


  // L\M — subtraction of HLists
  trait Sub[L <: HList, M <: HList] {
    type Out <: HList
    def apply(l: L, m: M): Out
  }

  object Sub {
    // This is the key point:
    // First we construct a union type for the second list as it's footprint,
    // and then we use it in `Filter[L, U]` as a reference.
    // So we traverse `M` only once, and then traverse `L`.
    implicit def s[L <: HList, M <: HList, U : UnionOf[M]#is]
      (implicit f: Filter[L, U]) = new Sub[L, M] {
        type Out = f.Out
        def apply(l: L, m: M) = f(l)
      }
  }

  def sub[L <: HList, M <: HList](l: L, m: M)(implicit s: Sub[L, M]) = s(l, m)

}