在 scalaz 中免费实现 [英] Free implementation in scalaz

问题描述

Haskell 中的 Free 实现是:

The Free implementation in Haskell is:

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

然而，Scalaz 中的实现是:

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]

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

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?

推荐答案

Haskell 代码到 Scala 的翻译将是

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]

由于惰性求值，Haskell 实现不需要 Gosub 案例.这种表示也适用于 Scala，但由于(严格评估和)缺乏尾调用消除，它会导致堆栈溢出问题.为了使其堆栈安全，我们将 flatMap 懒惰地表示为 Gosub(我认为 FlatMap 会是一个更好的名称):

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]

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

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]

因为我们不再需要通过映射S[_]的内容来做flatMaps—我们表示flatMaps明确作为 Gosubs.

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

因此，与 Haskell 表示不同，这种结果表示允许我们用 Free 做任何想做的事情，而无需 Functor[S].因此，当我们的 S 不是 Functor 时，我们甚至不需要搞乱Coyoneda 技巧".

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.

这篇关于在 scalaz 中免费实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！