Sequencing an HList

Question

Given a Shapeless HList where every list element shares the same type constructor, how can the HList be sequenced?

For example:

def some[A](a: A): Option[A] = Some(a)
def none[A]: Option[A] = None

val x = some(1) :: some("test") :: some(true) :: HNil
val y = sequence(x) // should be some(1 :: "test" :: true :: HNil)

def sequence[L <: HList : *->*[Option]#λ, M <: HList](l: L): Option[M] =
  ???

I tried to implement sequence like this:

object optionFolder extends Poly2 {
  implicit def caseOptionValueHList[A, B <: HList] = at[Option[A], Option[B]] { (a, b) =>
    for { aa <- a; bb <- b } yield aa :: bb
  }
}

def sequence[L <: HList : *->*[Option]#λ, M <: HList](l: L): Option[M] = {
  l.foldRight(some(HNil))(optionFolder)
}

But that does not compile:

could not find implicit value for parameter folder: shapeless.RightFolder[L,Option[shapeless.HNil.type],SequencingHList.optionFolder.type]

Any tips on implementing this for either a specific example like Option or for an arbitrary Applicative?

Answer 1

You were pretty close—you just need to make sure you have the extra bit of evidence that it's asking for:

def sequence[L <: HList : *->*[Option]#λ, M <: HList](l: L)(implicit
  folder: RightFolder[L, Option[HNil], optionFolder.type]
) = l.foldRight(some(HNil: HNil))(optionFolder)

Or, if you want something more general, and have an applicative implementation like this:

trait Applicative[F[_]] {
  def ap[A, B](fa: => F[A])(f: => F[A => B]): F[B]
  def point[A](a: => A): F[A]
  def map[A, B](fa: F[A])(f: A => B): F[B] = ap(fa)(point(f))
}

implicit object optionApplicative extends Applicative[Option] {
  def ap[A, B](fa: => Option[A])(f: => Option[A => B]) = f.flatMap(fa.map)
  def point[A](a: => A) = Option(a)
}

You can write:

object applicativeFolder extends Poly2 {
  implicit def caseApplicative[A, B <: HList, F[_]](implicit
    app: Applicative[F]
  ) = at[F[A], F[B]] {
    (a, b) => app.ap(a)(app.map(b)(bb => (_: A) :: bb))
  }
}

def sequence[F[_]: Applicative, L <: HList: *->*[F]#λ, M <: HList](l: L)(implicit
  folder: RightFolder[L, F[HNil], applicativeFolder.type]
) = l.foldRight(implicitly[Applicative[F]].point(HNil: HNil))(applicativeFolder)

And now you can sequence lists, etc., as well (assuming you have the appropriate instances).

---

Update: Note that I've omitted the return type annotation for sequence in both cases here. If we put it back in, the compiler chokes:

<console>:18: error: type mismatch;
 found   : folder.Out
 required: F[M]

This is because the RightFolder instance carries around its return type as an abstract type member. We know it's F[M] in this case, but the compiler doesn't care about what we know.

If we want to be able to be explicit about the return type, we can use the RightFolderAux instance instead:

def sequence[F[_]: Applicative, L <: HList: *->*[F]#λ, M <: HList](l: L)(implicit
  folder: RightFolderAux[L, F[HNil], applicativeFolder.type, F[M]]
): F[M] =
  l.foldRight(implicitly[Applicative[F]].point(HNil: HNil))(applicativeFolder)

Note that RightFolderAux has an extra type parameter, which indicates the return type.

Answer 2

Now you can use kittens cats.sequence

import cats.implicits._
import cats.sequence._
import shapeless._

val f1 = (_: String).length
val f2 = (_: String).reverse
val f3 = (_: String).toDouble

val f = (f1 :: f2 :: f3 :: HNil).sequence
assert( f("42.0") == 4 :: "0.24" :: 42.0 :: HNil)

The example sequenced against Function but you can use anything that has an cats Applicative instance.