Scalaz(42)- Free :FreeAp-Applicative Style Programming Language

  我们在前面花了几期时间讨论Free Monad,那是因为FP既是Monadic programming,Free Monad是FP模式编程的主要方式。对我们来说,Free Monad代表着fp从学术探讨到实际应用的转变,因为我们已经示范了如何用Free Monad的算式算法关注分离模式来实现真正的软件编程。但是美中不足的是用Free Monad只能编写流程式的程序;我们只能一步一步编译这种程序而无法实现并行运算以及在编译之前对程序结果进行分析或转换等。这种特性可以从Monad的运算函数flatMap的函数款式里看出:def flatMap(fa: F[A])(f: A=>F[B]):F[B]。如果F[A]代表当前程序、F[B]就是下一个程序,而下一个程序的产生依赖于F[A]运算结果,一个runtime值。在没有完成F[A]的运算之前我们无法得知F[B]的任何信息。所以又说Monadic程序结构是动态的。我们看到Free Monad功能十分强大:可以用Free Monad来实现任何程序,只不过这些程序结构都是动态的。动态结构程序对解决某些类型的问题在效率上可能不如静态结构的程序。我们可以用Applicative来产生静态结构的程序,这个从Applicative的运算函数ap可以看得出来:def ap(f: F[A=>B])(F[A]):F[B]。我们可以这样看ap:F[A=>B]是第一段程序,F[A]是下一段程序,而F[B]是结果程序。 第一第二段程序都不依赖任何运算值,所以我们可以先构建这些程序然后在任何时候对这些程序进行编译。由于所有程序都是固定预知而互不影响的,所以非常适合并行运算。

与Free Monad相似,Free Applicative Functor也是Applicative的结构化。下面是scalaz对FreeAp的定义:scalaz/FreeAp.scala

sealed abstract class FreeAp[F[_],A] {
...
  private [scalaz] case class Pure[F[_],A](a: A) extends FreeAp[F,A]
  private abstract case class Ap[F[_],A]() extends FreeAp[F,A] {
    type I
    val v: () => F[I]
    val k: () => FreeAp[F, I => A]
  }

FreeAp是一种有两种状态的数据类型:case class Pure(a: A)和 case class Ap(){v: ()=>F[I], k: ()=> FreeAp[F, I=>A]},其中Pure既是Return,包嵌一个运算结果值A,Ap结构内的k代表了下一个FreeAp,实现一个以Pure为终结的FreeAp结构链条。

实现了Applicative的结构化后我们就可以沿袭Free Monad的算式算法关注分离模式先编写描述功能的程序然后再对程序进行编译,只不过FreeAp程序不再是在Monadic for-comprehension内的行令编程,而是一连串的ap类函数了。与Free Monad一致,我们同样用ADT来模拟applicative编程语法,然后用ap函数把ADT链接起来成为程序。我们借用scalaz.example/FreeApUsage.scala来解译:

1、定义ADT: 这里是个解析(parse)数据类型的代数语法

  // An algebra of primitive operations in parsing types from Map[String, Any]
  sealed trait ParseOp[A]
  case class ParseInt(key: String) extends ParseOp[Int]
  case class ParseString(key: String) extends ParseOp[String]
  case class ParseBool(key: String) extends ParseOp[Boolean]

2、升格:Lift to FreeAp

  // Free applicative over Parse.
  type Parse[A] = FreeAp[ParseOp, A]

  // Smart constructors for Parse[A]
  def parseInt(key: String) = FreeAp.lift(ParseInt(key))
  def parseString(key: String) = FreeAp.lift(ParseString(key))
  def parseBool(key: String) = FreeAp.lift(ParseBool(key))

FreeAp.lift 可以把任何F[A]升格成FreeAp[F,A]:

  /** Lift a value in `F` into the free applicative functor on `F` */
  def lift[F[_],A](x: => F[A]): FreeAp[F, A] = FreeAp(x, Pure((a: A) => a))

3、AST: Applicative编程

  // An example that returns a tuple of (String, Int, Boolean) parsed from Map[String, Any]
  val successfulProg: Parse[(String, Int, Boolean)] =
    (parseString("string") |@| parseInt("int") |@| parseBool("bool"))((_, _, _))

  // An example that returns a tuple of (Boolean, String, Int) parsed from Map[String, Any]
  val failedProg: Parse[(Boolean, String, Int)] =
    (parseBool("string") |@| parseString("list") |@| parseInt("bool"))((_, _, _))

可以看到上面的Applicative编程就是用|@|把FreeAp结构链接起来,然后跟着把FreeAp之间的运算函数提供进去。我们知道F[A]|@|F[B]还是返回FreeAp[F,C]。也就是说这个程序的结果可以和其它FreeAp进行组合。我们可以看看下面的示范:

 object algebra {
    sealed trait ConfigF[A]

    case class ConfigInt   [A](field: String, value: Int     => A) extends ConfigF[A]
    case class ConfigFlag  [A](field: String, value: Boolean => A) extends ConfigF[A]
    case class ConfigPort  [A](field: String, value: Int     => A) extends ConfigF[A]
    case class ConfigServer[A](field: String, value: String  => A) extends ConfigF[A]
    case class ConfigFile  [A](field: String, value: String  => A) extends ConfigF[A]
    case class ConfigSub   [A](field: String, value: FreeAp[ConfigF, A])   extends ConfigF[A]
  }

  object dsl {
    import algebra._

    type Dsl[A] = FreeAp[ConfigF, A]

    private def lift[A](value: ConfigF[A]): Dsl[A] = FreeAp.lift[ConfigF, A](value)

    def int   (field: String): Dsl[Int]     = lift(ConfigInt   (field, identity))
    def flag  (field: String): Dsl[Boolean] = lift(ConfigFlag  (field, identity))
    def port  (field: String): Dsl[Int]     = lift(ConfigPort  (field, identity))
    def server(field: String): Dsl[String]  = lift(ConfigServer(field, identity))
    def file  (field: String): Dsl[String]  = lift(ConfigFile  (field, identity))
    def sub[A](field: String) 
              (value: Dsl[A])               = lift(ConfigSub   (field, value))
  }

上面定义了ADT及升格函数int,flag,port...

  case class AuthConfig(port: Int, host: String)
    case class ServerConfig(logging: Boolean, auth: AuthConfig)

    val authConfig   = (int("port") |@| server("host"))(AuthConfig)
    val serverConfig = (flag("logging") |@| sub("auth")(authConfig))(ServerConfig)

以上的serverConfig就用了authConfig进行了再组合。

4、Interpret: 翻译,把描述的功能对应到具体的实现方法上,还是用NaturalTransformation的方式把F[A]对应到G[A]:

  def parseOpt[A: ClassTag](a: Any): Option[A] =
    a match {
      case a: A => Some(a)
      case _ => None
    }

  // Natural transformation to Option[A]
  def toOption(input: Map[String, Any]): ParseOp ~> Option =
    new (ParseOp ~> Option) {
      def apply[A](fa: ParseOp[A]) = fa match {
        case ParseInt(key) =>
          input.get(key).flatMap(parseOpt[java.lang.Integer](_).map(x => (x: Int)))
        case ParseString(key) => input.get(key).flatMap(parseOpt[String])
        case ParseBool(key) =>
          input.get(key).flatMap(parseOpt[java.lang.Boolean](_).map(x => (x: Boolean)))
      }
    }

  // Natural transformation to ValidationNel[String, A]
  type ValidatedParse[A] = ValidationNel[String, A]
  def toValidation(input: Map[String, Any]): ParseOp ~> ValidatedParse =
    new (ParseOp ~> ValidatedParse) {
      def apply[A](fa: ParseOp[A]) = fa match {
        case s@ParseInt(_) => toOption(input)(s)
                                   .toSuccessNel(s"${s.key} not found with type Int")
        case s@ParseString(_) => toOption(input)(s)
                                   .toSuccessNel(s"${s.key} not found with type String")
        case i@ParseBool(_) => toOption(input)(i)
                                .toSuccessNel(s"${i.key} not found with type Boolean")
      }
    }

以上展示了两种程序翻译方法,对同样的程序可以用两种运算方式:

ParseOp ~> Option:翻译成Option类型。注意:input.get(key)返回Option,parseOpt同样返回Option

ParseOp ~> ValidatedPase:翻译成Validation类型。注意:无论如何,运算过程是不会中断的,ValidationNel中会记录所有错误信息

5、运算:runner,用折叠式来对一串FreeAp结构的每一个单元进行运算,还是叫做foldMap:

  /**
   * The canonical natural transformation that interprets this free
   * program by giving it the semantics of the applicative functor `G`.
   * Not tail-recursive unless `G` is a free monad.
   */
  def foldMap[G[_]:Applicative](f: F ~> G): G[A] =
    this match {
      case Pure(x) => Applicative[G].pure(x)
      case x@Ap() => Applicative[G].ap(f(x.v()))(x.k() foldMap f)
    }

运算原理很简单:如果是Pure就返回包嵌的值;如果是Ap对下一个FreeAp k()进行递归运算。

我们用测试数据来运行一下:

 // An example that returns a tuple of (String, Int, Boolean) parsed from Map[String, Any]
  val successfulProg: Parse[(String, Int, Boolean)] =
    (parseString("string") |@| parseInt("int") |@| parseBool("bool"))((_, _, _))

  // An example that returns a tuple of (Boolean, String, Int) parsed from Map[String, Any]
  val failedProg: Parse[(Boolean, String, Int)] =
    (parseBool("string") |@| parseString("list") |@| parseInt("bool"))((_, _, _))

  // Test input for programs
  val testInput: Map[String, Any] =
    Map("string" -> "foobar", "bool" -> true, "int" -> 4, "list" -> List(1, 2))

  // Run that baby
  println(successfulProg.foldMap(toOption(testInput)))
  println(successfulProg.foldMap(toValidation(testInput)))
  println(failedProg.foldMap(toOption(testInput)))
  println(failedProg.foldMap(toValidation(testInput)))

下面是运算结果:

Some((foobar,4,true))
Success((foobar,4,true))
None
Failure(NonEmpty[bool not found with type Int,list not found with type String,string not found with type Boolean])

我们得到了期望的结果。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员宝库

关于 Java 你不知道的 10 件事

作为 Java 书呆子,比起实用技能,我们会对介绍 Java 和 JVM 的概念细节更感兴趣。因此我想推荐 Lukas Eder 在 jooq.org 发表的原...

3496
来自专栏Ryan Miao

Java8学习(4)-Stream流

Stream和Collection的区别是什么 流和集合的区别是什么? 粗略地说, 集合和流之间的差异就在于什么时候进行计算。集合是一个内存中的数据结构,它包...

4487
来自专栏MasiMaro 的技术博文

IRP的同步

以WriteFile为例,一般的同步操作是调用WriteFile完成后,并不会返回,应用程序会在此处暂停,一直等到函数将数据写入文件中并正常返回,而异步操作则是...

1344
来自专栏刘君君

JDK8的CAS实现学习笔记

1886
来自专栏葡萄城控件技术团队

值得 .NET 开发者了解的15个特性

本文列举了 15 个值得了解的 C# 特性,旨在让 .NET 开发人员更好的使用 C# 语言进行开发工作。 1. ObsoleteAttribute Obsol...

3429
来自专栏一个会写诗的程序员的博客

《Kotlin 极简教程 》第5章 集合类(1)

本章将介绍Kotlin标准库中的集合类,我们将了解到它是如何扩展的Java集合库,使得写代码更加简单容易。如果您熟悉Scala的集合库,您会发现Kotlin跟S...

762
来自专栏Java架构沉思录

谈谈Java中常见的线程安全模型

多线程编程一直是老生常谈的问题,在Java中,随着JDK的逐渐发展,JDK提供给我们的并发模型也越来越多,本文摘取三例使用不同原理的模型,分析其大致原理。

1022
来自专栏菩提树下的杨过

利用java8对设计模式的重构

java8中提供的很多新特性可以用来重构传统设计模式中的写法,下面是一些示例: 一、策略模式 ? 上图是策略模式的类图,假设我们现在要保存订单,OrderSer...

35712
来自专栏微信公众号:Java团长

Java开发中如何正确踩坑

之前在这个手册刚发布的时候看过一遍,当时感觉真是每个开发者都应该必读的一本手册,期间还写过一篇关于日志规约的文章:《下一个项目为什么要用 SLF4J》,最近由于...

744
来自专栏葡萄城控件技术团队

Top 15 不起眼却有大作用的 .NET功能集

目录 1. ObsoleteAttribute 2. 设置默认值属性: DefaultValueAttribute 3. DebuggerBrowsableAt...

20410

扫码关注云+社区