Free implementation in scalaz

Question

Free implementation in Haskell:

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

whereas the implementation in Scalaz:

 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 scalaz implementation is not like Haskell, for example:

 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 both of these implementations isomorphic?

Answer 1

The translation of this Haskell code into Scala will 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 does not need a Gosub case thanks to a lazy evaluation. This view will work in Scala, but it will lead to problems with stack overflow due to (strict assessment and) lack of elimination of the tail call. To make it stack-safe, we introduce flatMap lazily since 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, introducing Gosub simplifies Suspend to

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

because we don’t need to do flatMap by matching the contents of S[_] anymore - we present flatMap explicitly as Gosub s.

As a result, this resulting view, unlike the Haskell view, allows us to do everything we need to do with Free , without requiring Functor[S] . Therefore, we don’t even need to bother with the Coyoneda trick when our S not a Functor .