scalafunctional-programmingmonadsscala-catsfree-monad

Where is that functor which free monad is supposed to be based on

I'm trying to comprehend the idea of free monad, and I'm stumped on the first sentence of cats's docs stating that

A free monad is a construction which allows you to build a monad from any Functor

My confusion is mainly related to the fact that there is no any functor used\created in the process of "freeing" ADT for KVStoreA. There is no implementation of functor for ADT or something like that. However, documentation for Free[S[_],A] says that S must me a functor:

A free operational monad for some functor S.

Where is that functor that free monad is supposed to be based on?

Solution

  • Thing is, Free monad can be used in a few different ways. In order to use one of them you assume that you have some functor S[_], it will have some Functor[S] defined and you will lift that S[*] to Free[S, *] by allowing some sort of extension to the original S:

    Free[S, A] = S[A] or A

    This is not valid Scala! They way it is actually implemented is using ADT. This only serves as an explanation of the idea.

    This way if you have S[A] and you map it with f: A => B, you would use Functor[S] and receive S[B]. But if you flatMap it with f: A => Free[S, B]... you would still be able to calculate that using Functor[S] and receive S[Free[S, B]]. That's what this code would be be underneath. Remembering that Free[S, A] = S[A] or A you could see that this would turn into S[S[S[...]]] and it could go infinitely nested if not for or A part of Free[S, A] which would let us stop at some point.

    Of course we don't calculate it all at once, Free usually uses trampoline to calculate only one thing at a time, so we aren't gonna end with tons of nesting at once.

    sealed abstract class Free[S[_], A] extends Product with Serializable {
  // ...
}
object Free extends FreeInstances {

  /**
   * Return from the computation with the given value.
   */
  final private[free] case class Pure[S[_], A](a: A) extends Free[S, A]

  /** Suspend the computation with the given suspension. */
  final private[free] case class Suspend[S[_], A](a: S[A]) extends Free[S, A]

  /** Call a subroutine and continue with the given function. */
  final private[free] case class FlatMapped[S[_], B, C](c: Free[S, C], f: C => Free[S, B]) extends Free[S, B]

  ...
}

    This trampoline representation implements the same idea as S[A] or A but it allows running computations one step at a time. It also shows that Free[S, *] is S[*] algebra extended by pure and flatMap operations (that assume nothing about S), which justifies calling Free a free algebra.

    Actually, until we decide to run the computations we only have lazily evaluated data structure. One way of running it is to call free.run that you have defined for Free in cats - it will use trampoline to evaluate each of this nestings, one at a time, but then it will use Comonad[S] to extract the value - as a result we will get rid of nestings as we go. Comonad[S] is also Functor[S] which is why we don't have to provide it separately to do all these maps.

    But that is one way of running things. Another way of running things is just assuming that we are recording the map, flatMap and pure operations using Free. For that we don't have to have Functor[S] at all. We might decide to run things using Comonad[S], but we might also decide something else. What if we translated S[_] to some M[_], but that we knew that this M[_] had a Monad[M]? In this case, we wouldn't have to use Functor[S] at all! We would run translation S ~> M, then, map or flatMap on it, and the S inside of it would be translated using the same S ~> M mechanism. This is what foldMap does - it requires us to provide a natural transformation S ~> M and instance of Monad[M] and Functor[S] is completely unnecessary. While conceptually we can still consider that S as a functor we don't need to rely on any of functors properties, not in the form of Functor[S].

    So to finally answer your question - with Free when we are still at the stage of "recording operations" we don't have to assume that S is a functor, so we don't need Functor[S]. When we want to interpret Free[S, A] into something - this is where functor might be actually needed, e.g. if we want to run Free[S, A] into A. But for some interpretations like e.g. foldMap (which is IMHO one of the most popular ones) this is not needed because we treat S as a plain data.