Interpreting a list of free monads vs. interpreting a free monad of a list

Question

I'm learning functional programming and have some (maybe obvious, but not for me :) ) question about monad. Every monad is an applicative functor. Applicative functor in turn can be defined as a higher-kinded type as follows (pure method omitted):

trait ApplicativeFunctor[F[_]]{
   def ap[A](fa: F[A])(f: F[A => B]): F[B]
}

As far as I understand this typeclass means that we can take two values of F[A], F[B] and a function (A, B) => C and construct F[C].

This property enables us to construct the list reversing function:

def reverseApList[F[_]: ApplicativeFunctor, A](lst: List[F[A]]): F[List[A]] 

Let we have

trait SomeType[A]

Now consider

type MyFree[A] = Free[SomeType, A] 
val nt: NaturalTransformation[SomeType, Id]
val lst: List[MyFree[Int]]

QUESTION: Why are lst.map(_.foldMap(nt)) and reverseApList(lst).foldMap(nt) the same? Is it following from applicative functor laws or there is another reason? Can you please explain?

Answer 1

It follows from the laws of Traversable functors.

First, realize that _.foldMap(nt) is itself a natural transformation from MyFree to Id. Moreover, by the very definition of what it means to be a free monad, it is required to be a monad homomorphism¹ (for any nt).

Let's start from your

reverseApList(lst).foldMap(nt)

which can also be written as

lst.sequence.foldMap(nt)

Now we are going to apply the naturality law of Traversable functors, with _.foldMap(nt) as the natural transformation nat. For it to be applicable, our natural transformation has to be an applicative homomorphism, which is expressed by the two extra conditions. But we already know that our natural transformation is a monad homomorphism, which is even stronger (preserves more structure) than an applicative homomorphism. We may therefore proceed to apply this law and obtain

lst.map(_.foldMap(nt)).sequence : Id[List[Int]]

Now using just the laws in the linked scalaz file it is provable (although in a roundabout way) that this last sequence through Id is actually a no-op. We get

lst.map(_.foldMap(nt))          : List[Id[Int]]

which is what we wanted to show.

---

¹ : A natural transformation h: M ~> N is a monad homomorphism if it preserves the monadic structure, i.e. if it satisfies

• for any a: A:
  h(Monad[M].point[A](a)) = Monad[N].point[A](a)
• for any ma: M[A] and f: A => M[B]:
  h(ma.flatMap(f)) = h(ma).flatMap(a => h(f(a)))