[Scala 2] Sequencer: Implicit complexity explodes when there is no common functor

[nigredo-tori]

Consider this example:

implicitly[Sequencer[
  Either[Nothing, Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    Option[Int] ::
    HNil
]]

The functors here don't align, which leads to a compilation error. But on my machine, it took the compiler 21 seconds to arrive to that conclusion. This gets exponentially worse the more elements the list has, which makes sequence, sequenceGeneric etc. a pain to use for large structures.

This might be caused by the overly general derivation for Sequencer that has cases for Invariant and InvariantMonoidal typeclasses in addition to the obvious Apply. In comparison, with this stripped-down version of Sequencer the example takes less than a second to (fail to) compile:

trait Sequencer[-L <: HList] {
  type F[_]
  type LOut <: HList
  type Out = F[LOut]

  def apply(hl: L): Out
}

object Sequencer {

  type Aux[L <: HList, F0[_], LOut0 <: HList] = Sequencer[L] {
    type F[A] = F0[A]
    type LOut = LOut0
  }

  implicit def hNil[F0[_]](implicit F0: Applicative[F0]): Aux[HNil, F0, HNil] = new Sequencer[HNil] {
    override type F[A] = F0[A]
    override type LOut = HNil

    override def apply(hl: HNil): Out = F0.pure(HNil)
  }

  implicit def hCons[F0[_], H, FT <: HList, T <: HList](
      implicit F0: Applicative[F0],
      tailSequencer: Sequencer.Aux[FT, F0, T]
  ): Aux[F0[H] :: FT, F0, H :: T] = new Sequencer[F0[H] :: FT] {
    override type F[A] = F0[A]
    override type LOut = H :: T

    override def apply(in: F0[H] :: FT): Out =
      F0.map2(in.head, tailSequencer(in.tail): F0[T])(_ :: _)
  }
}

[joroKr21]

Maybe we could keep the invariant versions and do a pattern match on the type class for the applicative ones.
The only reason to have both is optimization. Edit - I mean runtime optimization.