[关闭]
@MiloXia 2015-07-20T10:20:54.000000Z 字数 4508 阅读 1872

Free

函数式编程 scala

Free最大的价值在于Monadic for-comprehension和Interpreter，前者只要描述算法，后者随意解释，可类比为接口和实现。

Free 可以将任意functor F[A]变成monad Free[F[_], A]

毕竟函数式编程解决问题的手段都是从低阶类型lift到高阶类型，再套一层Context来表达低阶类型不可计算的问题，类似于封装了一层。

下面举例说明：
假设你上班前有以下动作：
1. 起床 - getUp
2. 洗漱 - wash
3. 做早饭 - makeBreakfast
4. 吃早饭 - eat
5. 出门 - goOut

在scala里面你会很自然的这么写

  1. def getUp() {...}
  2. def wash() {...}
  3. def makeBreakfast: Breakfast = {...}
  4. def eat(breakfast: Breakfast) {....}
  5. def goOut() {...}
  7. getUp()
  8. wash()
  9. val breakfast = makeBreakfast()
  10. eat(breakfast)
  11. goOut()

这是一个非常简单的算法逻辑，但是这段代码有一个很严重的问题！你看到没？ 哈哈，其实没有问题，只是这段代码是非纯函数式的，方法调用依次往下，满满的副作用，有木有？
像Haskell这种无";"的语言是不能这样写的，所以在没有";"的情况下你该怎么写？
两种选择：CPS 和 Monad
前者直接忽略，除非你非常喜欢回调，用Monad你会这么写：

  1. val doo = for {
  2.     _ <- getUp()
  3.     _ <- wash()
  4.     breakfast = makeBreakfast()
  5.     _ <- eat(breakfast)
  6.     _ <- goOut()
  7. } yield ()

但是，编译不过啊！我们没有给我们这个简单算法逻辑抽象出Monad来啊！怎么办？ 用Free就可以啊，它可以提供Monad啊，怎么用？
1. 先为我们的算法抽象出一个可以表示的结构（数据结构）出来，而不是上面那样定义一串函数：

  1.   case class Breakfast(egg: Int, milk: Int)
  2.   sealed trait GoToWork[A]
  3.   case object GetUp extends GoToWork[Unit]
  4.   case object Wash extends GoToWork[Unit]
  5.   case object MakeBreakfast extends GoToWork[Breakfast]
  6.   case class Eat(breakfast: Breakfast) extends GoToWork[Unit]
  7.   case object GoOut extends GoToWork[Unit]

这里关建的不是把函数变成case class或object, 而是引入了GoToWork[A]，我们要用Free, 必须得有F[A]

1.5 显然上面的case class和object之间没有啥联系，我们得引入表示他们关系的结构：

  1. trait DoFree[F[_], A] {
  2.   def unit(a: A): DoFree[F,A] = Return(a)
  3. }
  4. final case class Return[F[_], A](a: A) extends DoFree[F,A]
  5. final case class Bind[F[_], R, A](command: F[R], cont: R => DoFree[F,A]) extends DoFree[F,A]

引入两种表达关系或者（计算的类型Return和Bind），前者表示计算结束，后者表示延续计算咯，所以我们的算法结构可以这么表示：

  1. Bind(GetUp, (_:Unit) =>
  2.     Bind(Wash, (_:Unit) =>
  3.       Bind(MakeBreakfast, (breakfast: Breakfast) =>
  4.         Bind(Eat(breakfast), (b: Breakfast) =>
  5.           Bind(GoOut, (_:Unit) =>
  6.             Return(())))))) : DoFree[GoToWork,Unit]

每一步计算都表示的很清楚，但是还不能用Monadic for-comprehension ，因为DoFree不是Monad啊，那么得...

  1. 把DoFree变成Monad吧
  1. trait DoFree[F[_],A] {
  2.     def unit(a: A): DoFree[F,A] = Return(a)
  3.     def flatMap[B](k: A => DoFree[F,B]): DoFree[F,B] = this match {
  4.       case Return(a) =>
  5.         k(a)
  6.       case Bind(command, cont) =>
  7.         Bind(command, cont andThen (_ flatMap k))
  8.     }
  9.     def map[B](f: A => B): DoFree[F,B] =
  10.       flatMap(f andThen (Return(_)))

添加了flatMap方法，就可以用for了，flatMap的语义也很明确，把Retrun和Bind这两个结构串联起来。
这样我们就可以用for了：

  1.   object DoFree {
  2.     def lift[F[_],R](command: F[R]): DoFree[F,R] =
  3.       Bind(command, (x:R) => Return(x))
  4.   }
  5.   type FreeGoToWork[A] = DoFree[GoToWork, A]
  6.   implicit def liftGoToWork[A](n: GoToWork[A]): FreeGoToWork[A] = DoFree.lift(n)
  7.   val doo: FreeGoToWork[Unit] = for {
  8.     _ <- GetUp
  9.     _ <- Wash
  10.     breakfast <- MakeBreakfast
  11.     _ <- Eat(breakfast)
  12.     _ <- GoOut
  13.   } yield ()

好了，到此为止，我们的Free结束了，怎么可能呢？目前还没法执行啊！

  1. 添加Interpreter，我们需要解释执行这个结构，确切的说应该是将这个结构翻译成可执行体：
  1.   trait ~>[F[_],G[_]] {
  2.     def apply[A](fa: F[A]): G[A]
  3.   }
  4. //在DoFree中添加方法：
  5.   def foldMap[G[_]: Monad](f: F ~> G): G[A] = {
  6.       val G = implicitly[Monad[G]]
  7.       this match {
  8.         case Return(a) =>
  9.           G.unit(a)
  10.         case Bind(command, cont) =>
  11.           G.flatMap(f(command))(cont andThen (_ foldMap f))
  12.       }
  13.     }

"~>" 表示将F[A]转换为G[A]的函数，而G是个Monad
"foldMap"则是解开Return和Bind表示的计算结构，转化为真正monad G的for-comprehension

前方高能，这个"~>"可以将F[A]转为任意的Monad G[A]，就是说DoFree表示的结构，可以翻译为任意的Monad表示的真正可计算的结构
下面来添加一种最简单的(G[A])标准实现 Id

  1.   sealed case class Id[A](a: A)
  2.   //G必须提供Monad
  3.   implicit val IdMonad: Monad[Id] = new Monad[Id] {
  4.     def unit[A](a: A) = Id(a)
  5.     def flatMap[A,B](m: Id[A])(k: A => Id[B]): Id[B] =
  6.       m match { case Id(a) => k(a) }
  7.   }

3.5 实现一种"~>", 一般都已Console为例：

  1. object ConsoleEffect extends (GoToWork ~> Id) {
  2.     def apply[A](nl: GoToWork[A]): Id[A] = nl match {
  3.       case GetUp =>
  4.         println("get up")
  5.       case Wash =>
  6.         println("wash")
  7.       case MakeBreakfast =>
  8.         Breakfast(2, 1)
  9.       case Eat(b) =>
  10.         println(s"eat $b")
  11.       case GoOut =>
  12.         println(s"go out")
  13.     }
  14.   }

我们的Free完成，你可以随意实现"~>"和G[A], 最后就是执行了：

  1. doo.foldMap(ConsoleEffect)
  2. //打印
  3. get up
  4. wash
  5. eat Breakfast(2,1)
  6. go out

故事到此结束就好了，这里的foldMap是个非尾递归函数，也就是说可能会stackoverflow，所以如果你去看Scalaz的Free会发现它表示计算的结构有三种：

  1. private case class FlatMap[B](a: Free[F,A], f: A => Free[F,B]) extends Free[F,B]
  2. case class Return[F[_],A](a: A) extends Free[F,A]
  3. case class Suspend[F[_],A](ffa: F[Free[F,A]]) extends Free[F,A]

F[Free[F,A]]才是王道啊！这是啥？那是因为它引入了一个resume函数，来表示单步计算：

  1. def resume(implicit F: Functor[F]): Either[F[Free[F,A]],A] = this match {
  2.     case Return(a) => Right(a)
  3.     case Suspend(k) => Left(k)
  4.     case FlatMap(a,f) => a match {
  5.       case Return(b) => f(b).resume
  6.       case Suspend(k) => Left(F.map(k)(_ flatMap f))
  7.       case FlatMap(b,g) => FlatMap(b, g andThen (_ flatMap f)).resume
  8.     }
  9.   }

返回结构里有个F[Free[F,A]]，引入resume的目的是为了TCO, 用堆内存替换栈内存，防止stackoverflow，resume对入参F[A]的要求是它必须是个Functor
详情可参考： [ http://days2012.scala-lang.org/sites/days2012/files/bjarnason_trampolines.pdf ]

但是不是所有东西都可以抽象出函子来的（反正臣妾做不到），比如我们上面的GoToWork[A]

这个时候范畴论又出来了，我们有Coyoneda啊！这是什么鬼？ F[A] 可以变成 Coyoneda[F[], A]，Coyoneda[F[], A]和 Yoneda[F[],A]互转, Coyoneda[F[],A]可转为F[A]，但要提供Functor, Yoneda[F[],A]无需F: Functor可转为F[A], 反正可以转来转去，但是有一点很重要：F[A] 转 Coyoneda 不需要提供Functor，所以就可以抽象出一个FreeC并且是Stackless的去将任何F[A] 变成Free Monad， F[A] => Coyoneda[F[],A] => FreeC[S[_], A]

具体实现可参考： [ https://github.com/MiloXia/parz/blob/master/src/main/scala/com/mx/fp/core/stackless/Free.scala ]

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注