在scalaz中免费实现

Question

Haskell中的Free实现是:

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]

这两种实现都是同构的吗？

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]

Gosub由于懒惰的评估,Haskell实现不需要这种情况.这种表示也适用于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到

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

因为我们不需要flatMap通过对内容进行映射来实现S[_]- 我们将flatMaps明确表示为Gosubs.

因此,这导致表示,不像哈斯克尔表示,允许我们做的一切人愿意和做Free而没有要求Functor[S].因此,当我们S不是一个时,我们甚至不需要搞乱"Coyoneda技巧" Functor.