在 scalaz 中免费实施

Haskell 中的免费实现是：

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

而 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]

为什么 scalaz 实现与 Haskell 不相似，例如：

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]

这两个实现是同构的吗？

该 Haskell 代码到 Scala 的翻译是

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]

Haskell 实现不需要Gosub案例归功于懒惰的评估。这种表示法在 Scala 中也适用，但由于（严格评估和）缺乏尾部调用消除，它会导致堆栈溢出问题。为了使其堆栈安全，我们表示flatMap懒洋洋地，如Gosub（我认为FlatMap会是一个更好的名字）：

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

作为奖励，引入Gosub使我们能够简化Suspend to

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

因为我们不需要做flatMaps 通过映射内容S[_]不再——我们代表flatMap明确地为Gosubs.

因此，与 Haskell 表示不同，这种结果表示允许我们做任何我们想做的事情Free无需Functor[S]。因此，当我们的S不是一个Functor.