Scalaz(32)- Free :lift - Monad生产线

    在前面的讨论里我们提到自由数据结构就是产生某种类型的最简化结构,比如:free monoid, free monad, free category等等。我们也证明了List[A]是个free monoid。我们再看看free monad结构Free的定义:scalaz/Free.scala

/** A free operational monad for some functor `S`. Binding is done using the heap instead of the stack,
  * allowing tail-call elimination. */
sealed abstract class Free[S[_], A] {
...
  /** Return from the computation with the given value. */
  private[scalaz] case class Return[S[_], A](a: A) extends Free[S, A]

  /** Suspend the computation with the given suspension. */
  private[scalaz] case class Suspend[S[_], A](a: S[Free[S, A]]) extends Free[S, A]
...

我们在上一篇里证明过Free就是free monad,因为Free是个Monad而且它的结构是最简单的了:

1、Free[S[_],A]可以代表一个运算

2、case class Return是一个数据结构。Return(a:A)代表运算结束,运算结果a存放在结构中。另一个意义就是Monad.point(a:A),把一个任意A值a升格成Free

3、case class Suspend也是另一个数据结构。Suspend(a: S[Free[S,A]])代表把下一个运算存放在结构中。如果用Monad.join(a: F[F[A]])表示,那么里面的F[A]应该是个Free[S,A],这样我们才可能把运算结束结构Return[S,A](a:A)存放到Suspend中来代表下一步结束运算。

注意,Suspend(a: S[Free[S,A]])是个递归类型,S必须是个Functor,但不是任何Functor,而是map over Free[S,A]的Functor,也就是运算另一个Free[S,A]值。如果这个Free是Return则返回运算结果,如果是Suspend则继续递归运算。

简单来说Free是一个把Functor S[_]升格成Monad的产生器。我们可以用Free.liftF函数来把任何一个Functor升格成Monad。看看Free.liftF的函数款式就知道了:

  /** Suspends a value within a functor in a single step. Monadic unit for a higher-order monad. */
  def liftF[S[_], A](value: => S[A])(implicit S: Functor[S]): Free[S, A] =
    Suspend(S.map(value)(Return[S, A]))

liftF可以把一个S[A]升格成Free[S,A]。我们用个例子来证明:

 1 package Exercises
 2 import scalaz._
 3 import Scalaz._
 4 import scala.language.higherKinds
 5 import scala.language.implicitConversions
 6 object freelift {
 7 trait Config[+A] {
 8   def get: A
 9 }
10 object Config {
11   def apply[A](a: A): Config[A] = new Config[A] { def get = a}
12   implicit val configFunctor = new Functor[Config] {
13      def map[A,B](ca: Config[A])(f: A => B) = Config[B](f(ca.get))
14   }
15 }
16 
17 val freeConfig = Free.liftF(Config("hi config"))  //> freeConfig  : scalaz.Free[Exercises.freelift.Config,String] = Suspend(Exercises.freelift$Config$$anon$2@d70c109)

在上面的例子里Config是个运算A值的Functor。我们可以用Free.liftF把Config(String)升格成Free[Config,String]。实际上我们可以把这个必须是Functor的门槛取消,因为用Coyoneda就可以把任何F[A]拆解成Coyoneda[F,A],而Coyoneda天生是个Functor。我们先看个无法实现map函数的F[A]:

1 trait Interact[+A]  //Console交互
2 //println(prompt: String) then readLine 返回String
3 case class Ask(prompt: String) extends Interact[String]
4 //println(msg: String) 不反回任何值
5 case class Tell(msg: String) extends Interact[Unit]

由于Ask和Tell都不会返回泛类值,所以无需或者无法实现map函数,Interact[A]是个不是Functor的高阶类。我们必须把它转成Coyoneda提供给Free产生Monad:

1 Free.liftFC(Tell("hello"))                        //> res0: scalaz.Free.FreeC[Exercises.freelift.Interact,Unit] = Suspend(scalaz.Coyoneda$$anon$22@71423665)
2 Free.liftFC(Ask("how are you"))                   //> res1: scalaz.Free.FreeC[Exercises.freelift.Interact,String] = Suspend(scalaz.Coyoneda$$anon$22@20398b7c)

我们看看liftFC函数定义:

  /** A version of `liftF` that infers the nested type constructor. */
  def liftFU[MA](value: => MA)(implicit MA: Unapply[Functor, MA]): Free[MA.M, MA.A] =
    liftF(MA(value))(MA.TC)

  /** A free monad over a free functor of `S`. */
  def liftFC[S[_], A](s: S[A]): FreeC[S, A] =
    liftFU(Coyoneda lift s)

Coyoneda lift s 返回结果Coyoneda[S,A], liftFU用Unapply可以把Coyoneda[S,A]转化成S[A]并提供给liftF。看看Unapply这段:

  /**Unpack a value of type `M0[A0, B0]` into types `[a]M0[a, B0]` and `A`, given an instance of `TC` */
  implicit def unapplyMAB1[TC[_[_]], M0[_, _], A0, B0](implicit TC0: TC[({type λ[α] = M0[α, B0]})#λ]): Unapply[TC, M0[A0, B0]] {
    type M[X] = M0[X, B0]
    type A = A0
  } = new Unapply[TC, M0[A0, B0]] {
    type M[X] = M0[X, B0]
    type A = A0
    def TC = TC0
    def leibniz = refl
  }

  /**Unpack a value of type `M0[A0, B0]` into types `[b]M0[A0, b]` and `B`, given an instance of `TC` */
  implicit def unapplyMAB2[TC[_[_]], M0[_, _], A0, B0](implicit TC0: TC[({type λ[α] = M0[A0, α]})#λ]): Unapply[TC, M0[A0, B0]] {
    type M[X] = M0[A0, X]
    type A = B0
  } = new Unapply[TC, M0[A0, B0]] {
    type M[X] = M0[A0, X]
    type A = B0
    def TC = TC0
    def leibniz = refl
  }

好了。但是又想了想,一个是Functor的Interact又是怎样的呢?那Ask必须返回一个值,而这个值应该是个Free,实际上是代表下一个运算:

 1 package Exercises
 2 import scalaz._
 3 import Scalaz._
 4 import scala.language.higherKinds
 5 object interact {
 6 trait Interact[+A] 
 7 case class Ask[Next](prompt: String, n: String => Next) extends Interact[Next]
 8 case class Tell[Next](msg: String, n: Next) extends Interact[Next]
 9 
10 object interFunctor extends Functor[Interact] {
11   def map[A,B](ia: Interact[A])(f: A => B): Interact[B] = ia match {
12       case Tell(m,n) => Tell(m, f(n))
13       case g: Ask[A] => Ask[B](g.prompt, g.n andThen f)
14   }
15 }

所以Ask返回Next类型值,应该是个Free,代表下一个运算。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏移动端开发

Swift 实现俄罗斯方块详细思路解析(附完整项目)

    俄罗斯方块,是一款我们小时候都玩过的小游戏,我自己也是看着书上的思路,学着用 Swift 来写这个小游戏,在写这个游戏的过程中,除了一些位置的计算,数据...

1092
来自专栏Modeng的专栏

canvas学习总结四:绘制虚线

版权声明:本文为原创文章发布于公众号:Modeng , 你可以随意转载但请务必注明出处!!! https://blog.csdn.net/qq_32135...

602
来自专栏iOSer成长记录

iOS-圆角、边框、阴影

1265
来自专栏小鄧子的技术博客专栏

【译】图像的旋转与转换

在讲图像转换之前,有一个功能你可能经常用到:图片旋转。Picasso内置了图片旋转的功能。这里有两个选项:简单旋转和复杂旋转。

872
来自专栏数据结构与算法

第二类斯特灵数学习笔记

设$S(n, m)$表示把$n$个不同的球放到$m$个相同的盒子里,且不允许盒子为空的方案数

664
来自专栏mySoul

SVG绘制饼状图

872
来自专栏生信宝典

CIRCOS圈图绘制 - 染色体信息展示和调整

CIRCOS圈图绘制 - 最简单绘图和解释介绍了CIRCOS的安装、基本的配置文件的解释、如何最简单的获得一个CIRCOS图。最主要的部分还是配置文件的位置信息...

2175
来自专栏点滴积累

PhiloGL学习(1)——场景创建及方块欲露还羞出水面

前言 上一篇文章中介绍了我认识PhiloGL框架的机缘以及初步的探讨(见JS前端三维地球渲染——中国各城市航空路线展示),在此文中仅仅对此框架进行了简单介绍并初...

3406
来自专栏函数式编程语言及工具

Cats(2)- Free语法组合,Coproduct-ADT composition

    上篇我们介绍了Free类型可以作为一种嵌入式编程语言DSL在函数式编程中对某种特定功能需求进行描述。一个完整的应用可能会涉及多样的关联功能,但如果我们为...

1995
来自专栏程序员的诗和远方

20180818_ARTS_week08

这道题是要把字符串中的数字变成 int,通常的做法是遍历字符串,然后判断是不是在 0~9 中,如果把 0~9 放数组里每次循环检查感觉不是太好,时间复杂度是个 ...

501

扫码关注云+社区