scala - 在 Scala 中编写 Free monad

Question

我想我明白了Free莫纳德群岛我希望我也理解仿函数组成但单子(monad)do not ，即如果 M1和 M2那么是单子(monad)M1[M2]不一定是单子(monad)。

我的问题是:

做Free单子(monad)组成？

假设我们有仿函数 F1和 F2及其组成F1[F2] .假设我们还有 Free1和 Free2 -- Free F1 的单子(monad)和 F2 .我们可以定义一个 Free F1[F2] 的单子(monad)只需 Free1和 Free2 ?

Answer 1

希望我能回答你的问题:

Free monad 可以组成吗？

不。出于与“正常” monad 相同的原因。要编写 monadic bind，我们需要了解底层 monad 或自由 monad 案例中的底层仿函数。

希望 Haskell 语法不会吓到你太多:

type X f g a = Free f (Free g a)

bind :: X f g a -> (a -> X f g b) -> X f g b
bind (Pure (Pure x)) k = k x
bind (Pure (Free f)) k = error "not implemented"
bind _ = error "we don't even consider other cases"

在第二种情况下，我们有 f :: g (Free g a)和 k :: a -> Free f (Free g b) .我们可以 fmap ，因为这是我们唯一能做的:

bind (Pure (Free f)) k = let kf = fmap (fmap k) f -- fmapping inside g ∘ Free g
                         in = error "not implement"

kf的类型将是: g (Free g (Free f (Free g b))) , 当我们需要 Free f (Free g b) .您将遇到与为任何 Compose m1 m2 编写 monad 实例时相同的问题。 ，我们需要从 g-g-f-g 重新排序“绑定(bind)层”至 f-g-g-g ，并且要进行换向，我们需要了解更多关于 f 的信息。和 g .

如果您想查看上面的 Scala 版本，请发表评论。不过会更加晦涩难懂:(

我们可以用 Free1 和 Free2 为 F1[F2] 定义一个 Free monad

换句话说，给定:

type Free1[A] = Free[F1, A]
type Free2[A] = Free[F2, B]

type FreeDist[A] = Free1[Free2[A]] = Free[F1, Free[F2, A]]
type FreeComp[A] = Free[F1[F2[_]], A]

我们可以从 FreeDist[A] 写一个单子(monad)同态(一个好的映射)吗？至 FreeComp[A] ?我们不能，原因与前一部分相同。

斯卡拉版本

Scalaz 对 Free 的子类有私有(private)定义。 ，所以我必须执行 Free我自己有一个“可运行”的例子。一些从 http://eed3si9n.com/learning-scalaz/Free+Monad.html 中废弃的代码
Free 的第一个最简单的定义在斯卡拉:

import scala.language.higherKinds

trait Functor[F[_]] {
  def map[A, B](x: F[A])(f: A => B): F[B]
}

sealed trait Free[F[_], A] {
  def map[B](f: A => B)(implicit functor: Functor[F]): Free[F, B]
  def flatMap[B](f: A => Free[F, B])(implicit functor: Functor[F]): Free[F, B]
}
case class Pure[F[_], A](x: A) extends Free[F, A] {
  def map[B](f: A => B)(implicit functor: Functor[F]): Free[F, B] = Pure[F, B](f(x))
  def flatMap[B](f: A => Free[F, B])(implicit functor: Functor[F]): Free[F, B] = f(x)
}
case class Bind[F[_], A](x: F[Free[F, A]]) extends Free[F, A]  {
  def map[B](f: A => B)(implicit functor: Functor[F]): Free[F, B] = Bind {
    functor.map[Free[F,A], Free[F,B]](x) { y => y.map(f) }
  }
  // omitted 
  def flatMap[B](f: A => Free[F, B])(implicit functor: Functor[F]): Free[F, B] = ???
}

使用它，我们可以将 Haskell 示例翻译成 Scala:

type X[F[_], G[_], A] = Free[F, Free[G, A]]

// bind :: X f g a -> (a -> X f g b) -> X f g b
def xFlatMap[F[_], G[_], A, B](x: X[F, G, A], k: A => X[F, G, B])(implicit functorG: Functor[G]): X[F, G, B] =
  x match {
    case Pure(Pure(y)) => k(y)
    case Pure(Bind(f)) => {
      // kf :: g (Free g (Free f (Free g b)))
      val kf: G[Free[G, Free[F, Free[G, B]]]] = functorG.map(f) { y => y.map(k) }
      // But we need Free[F, Free[G, B]]
      ???
    }
    // we don't consider other cases
    case _ => ???
  }

结果是一样的，我们不能让类型匹配，我们需要转换 Free[G, Free[F, A]]进入 Free[F, Free[G, A]]不知何故。