implementazione libera in scalaz

Question

L'implementazione libera in Haskell è:

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

, mentre, l'implementazione in 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] 

perché non è l'implementazione scalaz simile a Haskell, come:

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] 

Queste due implementazioni sono isomorfe?

Answer 1

La traduzione di tale codice Haskell a Scala sarebbe

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] 

L'implementazione Haskell non ha bisogno del Gosub caso grazie alla valutazione pigra. Questa rappresentazione funzionerebbe anche in Scala, ma porterebbe a problemi di overflow dello stack dovuti alla (rigorosa valutazione e alla mancanza di un'eliminazione taille call). Per rendere impilare-safe, rappresentiamo flatMap pigramente, come Gosub (penso FlatMap sarebbe un nome migliore):

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

Come bonus, l'introduzione di Gosub ci permette di semplificare Suspend a

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

perché non abbiamo bisogno di fare flatMap s dalla mappatura sul contenuto di S[_] più — che rappresentano flatMap s esplicitamente come Gosub s.

Di conseguenza, questa rappresentazione risultante, a differenza della rappresentazione Haskell, ci consente di fare tutto ciò che si vuole fare con Free senza mai richiedere Functor[S]. Quindi non abbiamo nemmeno bisogno di scherzare con il "trucco Coyoneda" quando il nostro S non è un Functor.