Composing Free monads in Scala

Question

I think I understand what Free monad is. I hope I understand also that functors compose but monads do not, i.e. if M1 and M2 are monads then M1[M2] is not necessarily a monad.

My questions are:

• Do Free monads compose ?
• Suppose we have functors F1 and F2 and their composition F1[F2]. Suppose also we have Free1 and Free2 -- Free monads for F1 and F2. Can we define a Free monad for F1[F2] with just Free1 and Free2 ?

Answer 1

Hopefully I can answer your question:

Do Free monads compose?

No. For the same reasons as "normal" monads don't. To write monadic bind we need to know something about the underlying monad, or about the underlying functor in a free monad case.

Hopefully the Haskell syntax doesn't scare you too much:

type X f g a = Free f (Free g a)

bind :: X f g a -> (a -> X f g b) -> X f g b
bind (Pure (Pure x)) k = k x
bind (Pure (Free f)) k = error "not implemented"
bind _ = error "we don't even consider other cases"

In the second case we have f :: g (Free g a) and k :: a -> Free f (Free g b). We could fmap, as it's the only thing we can do:

bind (Pure (Free f)) k = let kf = fmap (fmap k) f -- fmapping inside g ∘ Free g
                         in = error "not implement"

The type of kf will be: g (Free g (Free f (Free g b))), when we'd need Free f (Free g b). You'll arrive at the same problem as when writing a monad instance for any Compose m1 m2, we'd need to reorder "bind layers" from g-g-f-g to f-g-g-g, and to do that commutation we need to know more about f and g.

Please comment, if you want to see the Scala version of above. It will be much more obscure though :(

Can we define a Free monad for F1[F2] with just Free1 and Free2

In other words given:

type Free1[A] = Free[F1, A]
type Free2[A] = Free[F2, B]

type FreeDist[A] = Free1[Free2[A]] = Free[F1, Free[F2, A]]
type FreeComp[A] = Free[F1[F2[_]], A]

Could we write a monad homomorphism (a good mapping) from FreeDist[A] to FreeComp[A]? We can't, for the same reasons as in a previous part.

---

Scala version

Scalaz has private definitions of subclasses of Free, so I have to implement Free myself to have an "runnable" example. Some of the code scrapped from http://eed3si9n.com/learning-scalaz/Free+Monad.html

First simplest definition of Free in Scala:

import scala.language.higherKinds

trait Functor[F[_]] {
  def map[A, B](x: F[A])(f: A => B): F[B]
}

sealed trait Free[F[_], A] {
  def map[B](f: A => B)(implicit functor: Functor[F]): Free[F, B]
  def flatMap[B](f: A => Free[F, B])(implicit functor: Functor[F]): Free[F, B]
}
case class Pure[F[_], A](x: A) extends Free[F, A] {
  def map[B](f: A => B)(implicit functor: Functor[F]): Free[F, B] = Pure[F, B](f(x))
  def flatMap[B](f: A => Free[F, B])(implicit functor: Functor[F]): Free[F, B] = f(x)
}
case class Bind[F[_], A](x: F[Free[F, A]]) extends Free[F, A]  {
  def map[B](f: A => B)(implicit functor: Functor[F]): Free[F, B] = Bind {
    functor.map[Free[F,A], Free[F,B]](x) { y => y.map(f) }
  }
  // omitted 
  def flatMap[B](f: A => Free[F, B])(implicit functor: Functor[F]): Free[F, B] = ???
}

Using that we can translate the Haskell example into Scala:

type X[F[_], G[_], A] = Free[F, Free[G, A]]

// bind :: X f g a -> (a -> X f g b) -> X f g b
def xFlatMap[F[_], G[_], A, B](x: X[F, G, A], k: A => X[F, G, B])(implicit functorG: Functor[G]): X[F, G, B] =
  x match {
    case Pure(Pure(y)) => k(y)
    case Pure(Bind(f)) => {
      // kf :: g (Free g (Free f (Free g b)))
      val kf: G[Free[G, Free[F, Free[G, B]]]] = functorG.map(f) { y => y.map(k) }
      // But we need Free[F, Free[G, B]]
      ???
    }
    // we don't consider other cases
    case _ => ???
  }

The result is the same, we can't make types match, We'd need transform Free[G, Free[F, A]] into Free[F, Free[G, A]] somehow.