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?

The first signature doesn't tell anything about C. What you described is called map2, not ap. Furthermore, I don't quite get what's going on with reverse. Are you really reversing anything, or is it a typo and you meant "traverse"? — Andrey Tyukin
@AndreyTyukin Take a look at Apply in scalaz. This is defined as ap. I just said that map2 can be gotten from ap. By reversing I meant making F[List[A]] from List[F[A]]. Such order reversing can only be done for application functors, not just functors... — Linda Turasco
@AndreyTyukin Just a note... in scalaz this is apply2, not map2 :) — Linda Turasco
@AndreyTyukin The closest to reverse is the function Applicative.sequence btw. — Linda Turasco
Thanks for looking up the names again, that definitely makes the question clearer. Indeed, it's apply2 in scalaz. A similar function is called map2 in cats , and also in Bjarnason/Chiusano , if I'm not confusing anything. — Andrey Tyukin

Tomas Mikula Tomas Mikula · Accepted Answer · 2018-03-05T23:18:15

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)))

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

1 Answers