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?

Coauthor

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"? – Airboat

@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... – Coauthor

@AndreyTyukin Just a note... in scalaz this is apply2, not map2 :) – Coauthor

@AndreyTyukin The closest to reverse is the function Applicative.sequence btw. – Coauthor

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. – Airboat

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

Nil

Thanks for your response, but I still cannot prove that the second precondition of the naturality law you linked is hold :(. I found that the FreeInstance contains the Monad[Free] definition with bind implemented as flatMap. So ap is also expressed as Free.flatMap. But how does it make _.foldMap(nt) satisfy the second naturality precondition? Thanks :) – Coauthor

The two extra conditions are the definition of what it means for a natural transformation to be an applicative homomorphism. OTOH, by definition of what it means to be a free monad, _.foldMap(nt) is required to be a monad homomorphism for any nt: F ~> M with M a monad (h: N ~> M is a monad homomorphism if h(na.flatMap(f)) = h(na).flatMap(a => h(f(a))), plus the same condition for point as for applicative homomorphism), so it better hold for scalaz.Free (otherwise it's not a free monad). It is easy to show that every monad homomorphism is an applicative homomorphism. – Nil