8

我想我明白Freemonad 是什么。我希望我也理解函子组成但单子不组成，即如果M1和M2是单子，那么不一定M1[M2]是单子。

我的问题是：

  • Free单子组成吗？
  • 假设我们有函子F1和F2它们的组合F1[F2]。假设我们也有Free1and Free2--用于andFree的单子。我们可以用 just和定义一个monad吗？ F1F2FreeF1[F2]Free1Free2
4

1 回答 1

8

希望我能回答你的问题：

Free 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)。您将遇到与为 any 编写 monad 实例时相同的问题Compose m1 m2，我们需要从 to 重新排序“绑定层” g-g-f-g，f-g-g-g并且要进行这种交换，我们需要更多地了解fand 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]

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

斯卡拉版本

Scalaz 对 的子类有私有定义Free，所以我必须Free自己实现一个“可运行”的例子。从http://eed3si9n.com/learning-scalaz/Free+Monad.html废弃的一些代码

FreeScala中第一个最简单的定义：

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]]某种方式。

于 2015-01-28T08:45:29.390 回答