Free implementation in scalaz

Question

The Free implementation in Haskell is:

data Free f a =
Pure a
| Free (f (Free f a))

whereas, the implementation in Scalaz is:

sealed abstract class Free[S[_], A]

private case class Return[S[_], A](a: A) extends Free[S, A]
private case class Suspend[S[_], A](a: S[A]) extends Free[S, A]
private case class Gosub[S[_], B, C](a: Free[S, C], f: C => Free[S, B]) extends Free[S, B]

why isn't the scalaz implementation similar to Haskell, like:

sealed trait Free[F[_],A]
case class Return[F[_],A](a: A) extends Free[F,A]
case class GoSub[F[_],A](s: F[Free[F,A]]) extends Free[F,A]

Are these both implementations isomorphic?

Answer 1

The translation of that Haskell code to Scala would be

sealed abstract class Free[S[_], A]

case class Return[S[_], A](a: A) extends Free[S, A]
case class Suspend[S[_], A](a: S[Free[S, A]]) extends Free[S, A]

The Haskell implementation doesn't need the Gosub case thanks to lazy evaluation. This representation would work in Scala as well, but it would lead to stack-overflow problems due to (strict evaluation and) lack of tail-call elimination. To make it stack-safe, we represent flatMap lazily, as Gosub (I think FlatMap would be a better name):

case class Gosub[S[_], B, C](a: Free[S, C], f: C => Free[S, B]) extends Free[S, B]

As a bonus, the introduction of Gosub allows us to simplify Suspend to

case class Suspend[S[_], A](a: S[A]) extends Free[S, A]

because we don't need to do flatMaps by mapping over the content of S[_] anymore—we represent flatMaps explicitly as Gosubs.

As a consequence, this resulting representation, unlike the Haskell representation, allows us to do everything one wants to do with Free without ever requiring Functor[S]. So we don't even need to mess with the "Coyoneda trick" when our S is not a Functor.