在Scala中组成免费monad

Question

我想我明白Freemonad是什么.我希望我的理解也是仿函数构成,但单子没有如果,即M1和M2的单子,然后M1[M2]是不是一定是单子.

我的问题是:

• 不要Free单子组成？
• 假设我们有仿函数F1和F2及其组成F1[F2].假设我们也有- Free1和monad for 和.我们可以用just 和？定义一个monad 吗？ Free2FreeF1F2FreeF1[F2]Free1Free2

Answer 1

希望我能回答你的问题:

自由单子组成吗？

不.出于与"普通"monad相同的原因没有.要编写monadic 绑定,我们需要了解有关底层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,我们就需要从重新排序"绑定层" g-g-f-g来f-g-g-g,要做到这一点减刑,我们需要更多地了解f和g.

如果你想看到上面的Scala版本,请发表评论.但它会更加模糊:(

我们可以用Free1和Free2定义F1 [F2]的免费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]到FreeComp[A]？我们不能,出于与前一部分相同的原因.

Scala版本

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