Freie Implementierung in scalaz

Question

Die freie Implementierung in Haskell ist:

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

während der Umsetzung in Scalaz ist:

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] 

warum nicht die scalaz Implementierung ist ähnlich wie Haskell, wie:

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] 

Sind diese beiden Implementierungen isomorph?

Answer 1

Die Übersetzung dieser Haskell Code Scala würde

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] 

Die Umsetzung Haskell sein, die Gosub Fall dank lazy evaluation nicht braucht. Diese Darstellung würde auch in Scala funktionieren, aber es würde zu Stack-Overflow-Problemen aufgrund von (strenger Auswertung und) fehlender Tail-Call-Eliminierung führen. Um es stapeln sicher, wir flatMap träge darstellen, wie Gosub (ich glaube, FlatMap würde einen besseren Namen sein):

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

Als Bonus, die Einführung von Gosub ermöglicht es uns, Suspend zu

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

zu vereinfachen

weil wir keine flatMap s durch Zuordnung über den Inhalt von S[_] mehr — müssen wir flatMap s explizit als Gosub s.

Als Konsequenz erlaubt diese resultierende Darstellung, im Gegensatz zur Haskell-Darstellung, alles, was wir mit Free machen wollen, ohne jemals Functor[S] zu benötigen. Also müssen wir uns nicht einmal mit dem "Coyoneda-Trick" anlegen, wenn unser S kein Functor ist.