Scalaz 中的免费实现

Question

免费的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]

这两个实现是否同构？

- adefor

---

如果使用第二个Scala实现，您将如何创建一个Free[F, A]，给定一个F[A]？ - Peter Neyens

@PeterNeyens 如果 F 是一个 Functor，那么这是完全可能的。但是这种表示方式存在堆栈安全问题。 - Tomas Mikula

@TomasMikula。好的，我明白了 GoSub[F, A](F.map(fa)(Return[F, A](_)))，谢谢！ - Peter Neyens

Answer 1

那段 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]

作为额外的加分项，引入使我们能够简化为。

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

因为我们不再需要通过映射S[_]的内容来执行flatMap，而是将flatMap显式表示为Gosub，所以我们不需要Functor[S]就可以做到使用Free要做的一切事情。因此，即使我们的S不是一个Functor，我们也不需要使用“Coyoneda技巧”。

- Tomas Mikula