Бесплатная реализация в scalaz

Бесплатная реализация на 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 не похожа на 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]

Являются ли эти обе реализации изоморфными?


scala scalaz free-monad
person adefor    schedule 10.06.2016    source источник
comment
Как бы вы создали Free[F, A] с учетом F[A], используя вторую реализацию Scala?   -  person Peter Neyens    schedule 10.06.2016
comment
@PeterNeyens это вполне возможно, когда F является Functor. Проблема с таким представлением заключается в том, что оно приводит к проблемам с безопасностью стека.   -  person Tomas Mikula    schedule 10.06.2016
comment
@Томас Микула. Хорошо, я вижу GoSub[F, A](F.map(fa)(Return[F, A](_))), спасибо!   -  person Peter Neyens    schedule 10.06.2016

Ответы (1)


arrow_upward
7
arrow_downward

Перевод этого кода 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, но приведет к проблемам с переполнением стека из-за (строгой оценки и) отсутствия исключения хвостовых вызовов. Чтобы сделать его безопасным для стека, мы лениво представляем 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]

потому что нам больше не нужно делать flatMaps, отображая содержимое S[_], мы представляем flatMaps явно как Gosubs.

Как следствие, это результирующее представление, в отличие от представления Haskell, позволяет нам делать все, что угодно, с Free, даже не требуя Functor[S]. Так что нам даже не нужно возиться с «трюком с Койонедой», когда наш S не Functor.

person Tomas Mikula    schedule 10.06.2016