泛函编程(30)-泛函IO:Free Monad-Monad生产线

    在上节我们介绍了Trampoline。它主要是为了解决堆栈溢出(StackOverflow)错误而设计的。Trampoline类型是一种数据结构,它的设计思路是以heap换stack:对应传统递归算法运行时在堆栈上寄存程序状态,用Trampoline进行递归算法时程序状态是保存在Trampoline的数据结构里的。数据结构是在heap上的,所以可以实现以heap换stack的效果。这种以数据结构代替函数调用来解决问题的方式又为泛函编程提供了更广阔的发展空间。

    我们知道,任何涉及IO的运算都会面临堆栈溢出问题。这是因为IO通常针对无法预计的数据量以及重复循环操作。所以IO算法设计也会采用与Trampoline一样的数据结构。或者我们应该沿用Trampoline数据结构和算法来设计IO组件库。如此思考那么我们就必须对Trampoline进行深度抽象了。Free Monad就是Trampline的延伸。在介绍Free Monad之前我们先从一个现实的例子来展开讨论:

假设我们要编写一个银行转账的函数,我们可能先把这个函数的款式(function signature)推导出来:

1 def transfer(amount: Double, from: Account, to: Account, user: User, 
2   context: Authorization with Logger with ErrorHandler with Storage): Unit

首先我们在这里采用了参数注入(parameter injection)方式:在transfer函数输入参数中注入context object。这个context object里包括了身份验证、操作跟踪、错误处理、数据存取等等。这算是传统OOP编程模式吧。对于一个泛函编程人员来讲:通过这个context object 可以进行一系列的操作。包括IO操作,也就是说可以进行一些含有副作用(side effect)的操作。那么这个函数是无法实现函数组合(function composition)。transfer函数就不是一个泛函编程人员该使用的函数了。

也许我们应该从泛函编程角度来尝试设计这个函数:用泛函编程提倡的不可蜕变(immutability)方式来设计,也就是向函数调用方返回一些东西。

比如我们可以向函数调用方返回一个描述操作的程序:一串命令(instruction):

1 def transfer(amount: Double, from: Account, to: Account, user: User): List[Instruction]

这个版本肯定是个泛函版本了。不过假如Instruction类型包括了互动操作的话就不足够了。我们先看看简单的交互的数据类型:

1 trait Interact[A] //交互数据类型
2 //提问,等待返回String类型答案
3 case class Ask(prompt: String) extends Interact[String] 
4 //告知,没有返回结果
5 case class Tell(msg: String) extends Interact[Unit]

如果我们按照上面的思路返回一串命令的话:

1  val prg = List(Ask("What's your first name?"),
2                  Ask("What's your last name?"),
3                  Tell("Hello ??? ???"))

这个程序prg是有缺陷的:无法实现交互。好像如果能把Ask指令存放到一个临时变量里就可以达到目的了。那么如果我们把这个prg改写成下面这样:

1 for {
2     x <- Ask("What's your first name?")
3     y <- Ask("What's your last name?")
4     _ <- Tell(s"Hello $y $x!")
5 } yield () 

这不就是Monad款式吗?原来解决方法就是把交互类型trait Interact[A]变成Monad就行了。

不过要把Interact变成Monad就必须实现unit和flatMap两个函数,检查Interact trait,明显这是不可能的。

那我们把下面的努力都应该放在如何转变成Monad这方面了。既然我们在本篇命题里提到Free Monad是Monad生产线。那么用Free Monad能不能把Interact变成Monad呢?

我们先看看这个Free Monad类型结构:

1 trait Free[F[_],A] 
2 case class Return[F[_],A](a: A) extends Free[F,A]
3 case class Bind[F[_],I,A](a: F[I], f: I => Free[F,A]) extends Free[F,A]

这个Free结果跟Trampoline简直是太相似了。如果Free是个Monad,那么我们应该必须实现它的flatMap函数:

 1 trait Free[F[_],A] {
 2  def unit(a: A) = Return(a)
 3  def flatMap[B](f: A => Free[F,B]): Free[F,B] = this match {
 4        case Return(a) => f(a)
 5 //还记得Trampoline  FlatMap(FlatMap(b,g),f) == FlatMap(b, (x: Any) => FlatMap(g(x),f))       
 6        case Bind(fa,g) => Bind(fa, (x: Any) => g(x) flatMap f)
 7 //下面采用了函数组合方式。具备同样功能 
 8 //   case Bind(fa,g) => Bind(fa, g andThen (_ flatMap f))
 9  }
10  def map[B](f: A => B): Free[F,B] = flatMap(a => Return(f(a)))
11 
12 }
13 case class Return[F[_],A](a: A) extends Free[F,A]
14 case class Bind[F[_],I,A](a: F[I], f: I => Free[F,A]) extends Free[F,A]

我们可以用下面的lift函数来把Interact[A]升格成Free[F,A] :

1 implicit def lift[F[_],A](fa: F[A]): Free[F,A] = Bind(fa, (a: A) => Return(a))
2                                                   //> lift: [F[_], A](fa: F[A])ch13.ex6.Free[F,A]

有了lift我们可以吧prg升格成Monad:

 1 trait Interact[A] //交互数据类型
 2 //提问,等待返回String类型答案
 3 case class Ask(prompt: String) extends Interact[String]
 4 //告知,没有返回结果
 5 case class Tell(msg: String) extends Interact[Unit]
 6 
 7 implicit def lift[F[_],A](fa: F[A]): Free[F,A] = Bind(fa, (a: A) => Return(a))
 8                                                   //> lift: [F[_], A](fa: F[A])ch13.ex6.Free[F,A]
 9 for {
10     x <- Ask("What's your first name?")
11     y <- Ask("What's your last name?")
12     _ <- Tell(s"Hello $y $x!")
13 } yield ()                                        //> res0: ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first nam
14                                                   //| e?),<function1>)

这是因为implicit scope里的类型转换使Interact升格为Free,而Free是个Monad,所以我们可以使用for-comprehension。

好了,这个程序描述完成后应该如何运算呢?Free Monad包括了两部分功能,相互之间无关联,可以分开单独考虑。这就是所谓的关注分离(separation of concern)。Free Monad的两项功能分别是Monad,和Interpreter(解译器)。我们用Monad描述程序算法,用Interpreter解译程序形成针对特定运行环境的可运行代码。

Free Monad的Interpreter实现了算法和运算的分离考虑。Interpreter程序运算是通过一个转换函数实现的。这个函数把F[_]这样一个算法解译成G[_]这样一个针对可运行环境的Monad运行代码。这种转换就是自然转换(Natural Transformation),它的函数款式如下:

1 trait ~>[F[_],G[_]] {
2     def apply[A](fa: F[A]): G[A]
3 }

很明显,这个构建函数(constructor)把传入的F[A]解译成G[A]。

现在Interpreter运行一段算法就是对算法F[_]中的表达式进行一对一的G[_]转换。就像对List结构中元素进行处理的方式一样,我们可以用折叠算法来实现F[_]结构中表达式的转换:

1 def foldMap[G[_]: Monad](f: F ~> G): G[A] = this match {
2           case Return(a) => Monad[G].unit(a)
3           case Bind(b,g) => Monad[G].flatMap(f(b))(a => g(a).foldMap(f))
4  }

我们看到,foldMap把Free Monad F[_]中的表达式与Monad G状态进行了对应。注意Bind状态是循环递归的。

现在我们可以试试最简单的解译:F,Id转换:

 1 ype Id[A] = A
 2 implicit val idMonad: Monad[Id] = new Monad[Id] {
 3     def unit[A](a: A) = a
 4     def flatMap[A,B](fa: A)(f: A => B): B = f(fa)
 5 }                                                 //> idMonad  : ch13.ex6.Monad[ch13.ex6.Id] = ch13.ex6$$anonfun$main$1$$anon$1@2
 6                                                   //| 530c12
 7 object Console extends (Interact ~> Id) {
 8     def apply[A](i: Interact[A]): A = i match {
 9         case Ask(prompt) => {
10           println(prompt)
11           readLine
12         }
13         case Tell(msg) => println(msg)
14     }
15 }

运算上面那段Interact程序:由于Id不产生任何效果,Interact到Id转换即是直接运算Interact表达式:

1 val prg = for {
2     x <- Ask("What's your first name?")
3     y <- Ask("What's your last name?")
4     _ <- Tell(s"Hello $y $x!")
5 } yield ()                                        //> prg  : ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first n
6                                                   //| ame?),<function1>)
7 
8 prg.foldMap(Console)

或者我们可以试试再复杂一点的解译:

 1 type Tester[A] = Map[String, String] => (List[String], A)
 2 implicit val testerMonad = new Monad[Tester] {
 3     def unit[A](a: A) = (_ => (List(),a))
 4     def flatMap[A,B](ta: Tester[A])(f: A => Tester[B]): Tester[B] = {
 5         m => {
 6             val (l1,a) = ta(m)
 7             val (l2,b) = f(a)(m)
 8             (l1 ++ l2,b)
 9         }
10     }
11 }                                                 //> testerMonad  : ch13.ex6.Monad[ch13.ex6.Tester]{def unit[A](a: A): Map[Strin
12                                                   //| g,String] => (List[Nothing], A)} = ch13.ex6$$anonfun$main$1$$anon$2@5b464ce
13                                                   //| 8
14 object TestConsole extends (Interact ~> Tester) {
15     def apply[A](i: Interact[A]): Tester[A] = i match {
16       case Ask(prompt) => m => (List(), m(prompt))
17       case Tell(msg) => _ => (List(msg),())
18     }
19 }

以上我们把运行Interact中的交互信息存入Map[String,String]结构中。在这里进行了Interact到一个函数Map=>(List,A)的转换。

1 val prg = for {
2     x <- Ask("What's your first name?")
3     y <- Ask("What's your last name?")
4     _ <- Tell(s"Hello $y $x!")
5 } yield ()                                        //> prg  : ch13.ex6.Free[ch13.ex6.Interact,Unit] = Bind(Ask(What's your first n
6                                                   //| ame?),<function1>)
7 
8 prg.foldMap(TestConsole)

在上一节我们讨论了Trampoline。主要目的是解决泛函算法中不可避免的堆栈溢出问题。如果我们用Free Monad来解决IO问题的话,堆栈溢出问题也是无法避免的。我们应该考虑在Free Monad里使用Trampoline类型。这样我们才可以放心地用Free Monad来产生任何类型的Monad并在运算中以heap换stack解决堆栈溢出问题。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏计算机视觉与深度学习基础

Leetcode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such th...

1659
来自专栏种道伟的专栏

Lua 性能剖析

lua语言在游戏行业大受欢迎,因运行效率高(相比于其他脚本语言),热更方便等原因被广泛应用。想在现有c++系统中引入lua,被挑战的第一个问题往往是:“Lua性...

3.2K3
来自专栏Crossin的编程教室

【每周一坑】神奇的九宫格

五一小长假大家应该玩的挺开心吧,还沉浸在假日的愉悦中么?请大家收收心,准备准备月底的端午节。 看看本周的题目吧,本周的题目由读者 @疯琴 提供,我们做了小小的改...

2657
来自专栏Android知识点总结

2-3树与红黑树

433
来自专栏牛客网

深信服面试 C++/云计算面经

1275
来自专栏Albert陈凯

Scala 特性

面向对象特性 Scala是一种纯面向对象的语言,每个值都是对象。对象的数据类型以及行为由类和特质描述。 类抽象机制的扩展有两种途径:一种途径是子类继承,另一...

2567
来自专栏编程

C语言嵌入式系统编程修炼之性能优化

这是我13年前创作和发表在互联网上的文章,这么多年过去了,这篇文章仍然在到处传播。现在贴回Linuxer公众号。 全文目录: C语言嵌入式系统编程修炼之道——背...

1797
来自专栏Python中文社区

Python如何传递运算表达式

正小歪,Python 工程师,主要负责 Web 开发和日志数据处理。博客文章《真正的 Tornado 异步非阻塞》、《使用 JWT 让你的 RESTful AP...

761
来自专栏mukekeheart的iOS之旅

No.011 Container With Most Water

11. Container With Most Water Total Accepted: 86363 Total Submissions: 244589 Di...

2179
来自专栏Spark学习技巧

SparkSql的优化器-Catalyst

一,概述 为了实现Spark SQL,基于Scala中的函数编程结构设计了一个新的可扩展优化器Catalyst。Catalyst可扩展的设计有两个目的。 首先,...

2139

扫码关注云+社区