Composing F-Algebra[F, A] to F-Algebra[F, Seq[A]]

Question

I'm trying to compose F-Algebras like in this page. The difference is that, instead of composing with a tuple, like this:

type FAlgebra[F[_], A] = F[A] => A

def algebraZip[F[_], A, B](fa: FAlgebra[F, A], fb: FAlgebra[F, B])
                      (implicit F: Functor[F]): FAlgebra[F, (A, B)] =
  fab => {
    val a = fa(fab.map(_._1))
    val b = fb(fab.map(_._2))
    (a, b)
  }

I would like to use a Seq, like this:

def algebraSeq[F[_], A](fa: FAlgebra[F, A])
                       (implicit F: Functor[F]): FAlgebra[F, Seq[A]] = ???

Is it possible? What would I need? Or would using shapeless HList help?

Answer 1

If I can make some slight alterations to your constraints, I can find an implementation:

def algebraSeq[F[_]: Traverse, A](fa: FAlgebra[F, A]): FAlgebra[F, Seq[A]] = 
  fseq => fseq.sequence.map(f => fa(f))

I needed the Traverse instance to be able to sequence a F[Seq[A]] to a Seq[F[A]].

In the past you had to write this function for List instead of Seq because there was no Applicative[Seq] instance. But since cats 2.3.0 instances for immutable.Seq (which is the default scala.Seq in Scala 2.13) were added.