在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实施哈斯克尔，如：

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] 

Haskell的实现并不需要Gosub情况下，由于懒惰的评估。这种表示方式也可以在Scala中使用，但由于（严格评估和缺少尾部消除消除），它会导致堆栈溢出问题。为了使IT架构安全的，我们代表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] 

因为我们不需要通过映射S[_]的内容来做flatMap s —我们将flatMap明确地表示为Gosub s。

因此，与Haskell表示形式不同，此结果表示允许我们做任何想做的事情，而不需要Functor[S]。所以当我们的S不是Functor时，我们甚至不需要混淆“Coyoneda技巧”。