Sequencing an HList

scala, shapeless

Solution

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.

Problem

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?

Original source