泛函编程(29)-泛函实用结构:Trampoline-不再怕StackOverflow

   泛函编程方式其中一个特点就是普遍地使用递归算法,而且有些地方还无法避免使用递归算法。比如说flatMap就是一种推进式的递归算法,没了它就无法使用for-comprehension,那么泛函编程也就无法被称为Monadic Programming了。虽然递归算法能使代码更简洁易明,但同时又以占用堆栈(stack)方式运作。堆栈是软件程序有限资源,所以在使用递归算法对大型数据源进行运算时系统往往会出现StackOverflow错误。如果不想办法解决递归算法带来的StackOverflow问题,泛函编程模式也就失去了实际应用的意义了。

针对StackOverflow问题,Scala compiler能够对某些特别的递归算法模式进行优化:把递归算法转换成while语句运算,但只限于尾递归模式(TCE, Tail Call Elimination),我们先用例子来了解一下TCE吧:

以下是一个右折叠算法例子:

1 def foldR[A,B](as: List[A], b: B, f: (A,B) => B): B = as match {
2     case Nil => b
3     case h :: t => f(h,foldR(t,b,f))
4 }                                                 //> foldR: [A, B](as: List[A], b: B, f: (A, B) => B)B
5 def add(a: Int, b: Int) = a + b                   //> add: (a: Int, b: Int)Int
6 
7 foldR((1 to 100).toList, 0, add)                  //> res0: Int = 5050
8 foldR((1 to 10000).toList, 0, add)                //> java.lang.StackOverflowError

以上的右折叠算法中自引用部分不在最尾部,Scala compiler无法进行TCE,所以处理一个10000元素的List就发生了StackOverflow。

再看看左折叠:

1 def foldL[A,B](as: List[A], b: B, f: (B,A) => B): B = as match {
2     case Nil => b
3     case h :: t => foldL(t,f(b,h),f)
4 }                                                 //> foldL: [A, B](as: List[A], b: B, f: (B, A) => B)B
5 foldL((1 to 100000).toList, 0, add)               //> res1: Int = 705082704

在这个左折叠例子里自引用foldL出现在尾部位置,Scala compiler可以用TCE来进行while转换:

 1   def foldl2[A,B](as: List[A], b: B,
 2                  f: (B,A) => B): B = {
 3     var z = b
 4     var az = as
 5     while (true) {
 6       az match {
 7         case Nil => return z
 8         case x :: xs => {
 9           z = f(z, x)
10           az = xs
11         }
12       }
13     }
14     z
15   }

经过转换后递归变成Jump,程序不再使用堆栈,所以不会出现StackOverflow。

但在实际编程中,统统把递归算法编写成尾递归是不现实的。有些复杂些的算法是无法用尾递归方式来实现的,加上JVM实现TCE的能力有局限性,只能对本地(Local)尾递归进行优化。

我们先看个稍微复杂点的例子:

1 def even[A](as: List[A]): Boolean = as match {
2     case Nil => true
3     case h :: t => odd(t)
4 }                                                 //> even: [A](as: List[A])Boolean
5 def odd[A](as: List[A]): Boolean = as match {
6     case Nil => false
7     case h :: t => even(t)
8 }                                                 //> odd: [A](as: List[A])Boolean

在上面的例子里even和odd分别为跨函数的各自的尾递归,但Scala compiler无法进行TCE处理,因为JVM不支持跨函数Jump:

1 even((1 to 100).toList)                           //> res2: Boolean = true
2 even((1 to 101).toList)                           //> res3: Boolean = false
3 odd((1 to 100).toList)                            //> res4: Boolean = false
4 odd((1 to 101).toList)                            //> res5: Boolean = true
5 even((1 to 10000).toList)                         //> java.lang.StackOverflowError

处理10000个元素的List还是出现了StackOverflowError

我们可以通过设计一种数据结构实现以heap交换stack。Trampoline正是专门为解决StackOverflow问题而设计的数据结构:

1 trait Trampoline[+A] {
2  final def runT: A = this match {
3       case Done(a) => a
4       case More(k) => k().runT
5   }
6 }
7 case class Done[+A](a: A) extends Trampoline[A]
8 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]

Trampoline代表一个可以一步步进行的运算。每步运算都有两种可能:Done(a),直接完成运算并返回结果a,或者More(k)运算k后进入下一步运算;下一步又有可能存在Done和More两种情况。注意Trampoline的runT方法是明显的尾递归,而且runT有final标示,表示Scala可以进行TCE。

有了Trampoline我们可以把even,odd的函数类型换成Trampoline:

1 def even[A](as: List[A]): Trampoline[Boolean] = as match {
2     case Nil => Done(true)
3     case h :: t => More(() => odd(t))
4 }                                                 //> even: [A](as: List[A])ch13.ex1.Trampoline[Boolean]
5 def odd[A](as: List[A]): Trampoline[Boolean] = as match {
6     case Nil => Done(false)
7     case h :: t => More(() => even(t))
8 }                                                 //> odd: [A](as: List[A])ch13.ex1.Trampoline[Boolean]

我们可以用Trampoline的runT来运算结果:

1 even((1 to 10000).toList).runT                    //> res6: Boolean = true
2 even((1 to 10001).toList).runT                    //> res7: Boolean = false
3 odd((1 to 10000).toList).runT                     //> res8: Boolean = false
4 odd((1 to 10001).toList).runT                     //> res9: Boolean = true

这次我们不但得到了正确结果而且也没有发生StackOverflow错误。就这么简单?

我们再从一个比较实际复杂一点的例子分析。在这个例子中我们遍历一个List并维持一个状态。我们首先需要State类型:

 1 case class State[S,+A](runS: S => (A,S)) {
 2 import State._
 3     def flatMap[B](f: A => State[S,B]): State[S,B] = State[S,B] {
 4         s => {
 5             val (a1,s1) = runS(s)
 6             f(a1) runS s1
 7         }
 8     }
 9   def map[B](f: A => B): State[S,B] = flatMap( a => unit(f(a)))
10 }
11 object State {
12     def unit[S,A](a: A) = State[S,A] { s => (a,s) }
13     def getState[S]: State[S,S] = State[S,S] { s => (s,s) }
14     def setState[S](s: S): State[S,Unit] = State[S,Unit] { _ => ((),s)}
15 }

再用State类型来写一个对List元素进行序号标注的函数:

 1 def zip[A](as: List[A]): List[(A,Int)] = {
 2     as.foldLeft(
 3       unit[Int,List[(A,Int)]](List()))(
 4       (acc,a) => for {
 5         xs <- acc
 6         n <- getState[Int]
 7         _ <- setState[Int](n + 1)
 8       } yield (a,n) :: xs
 9     ).runS(0)._1.reverse
10 }                                                 //> zip: [A](as: List[A])List[(A, Int)]

运行一下这个zip函数:

1 zip((1 to 10).toList)                             //> res0: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,6
2                                                   //| ), (8,7), (9,8), (10,9))

结果正确。如果针对大型的List呢?

1 zip((1 to 10000).toList)                          //> java.lang.StackOverflowError

按理来说foldLeft是尾递归的,怎么StackOverflow出现了。这是因为State组件flatMap是一种递归算法,也会导致StackOverflow。那么我们该如何改善呢?我们是不是像上面那样把State转换动作的结果类型改成Trampoline就行了呢?

 1 case class State[S,A](runS: S => Trampoline[(A,S)]) {
 2     def flatMap[B](f: A => State[S,B]): State[S,B] = State[S,B] {
 3         s => More(() => {
 4             val (a1,s1) = runS(s).runT
 5             More(() => f(a1) runS s1)
 6         })
 7     }
 8   def map[B](f: A => B): State[S,B] = flatMap( a => unit(f(a)))
 9 }
10 object State {
11     def unit[S,A](a: A) = State[S,A] { s => Done((a,s)) }
12     def getState[S]: State[S,S] = State[S,S] { s => Done((s,s)) }
13     def setState[S](s: S): State[S,Unit] = State[S,Unit] { _ => Done(((),s))}
14 }
15 trait Trampoline[+A] {
16  final def runT: A = this match {
17       case Done(a) => a
18       case More(k) => k().runT
19   }
20 }
21 case class Done[+A](a: A) extends Trampoline[A]
22 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
23 
24 def zip[A](as: List[A]): List[(A,Int)] = {
25     as.foldLeft(
26       unit[Int,List[(A,Int)]](List()))(
27       (acc,a) => for {
28         xs <- acc
29         n <- getState[Int]
30         _ <- setState[Int](n + 1)
31       } yield (a,n) :: xs
32     ).runS(0).runT._1.reverse
33 }                                                 //> zip: [A](as: List[A])List[(A, Int)]
34 zip((1 to 10).toList)                             //> res0: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,
35                                                   //| 6), (8,7), (9,8), (10,9))

在这个例子里我们把状态转换函数 S => (A,S) 变成 S => Trampoline[(A,S)]。然后把其它相关函数类型做了相应调整。运行zip再检查结果:结果正确。那么再试试大型List:

1 zip((1 to 10000).toList)                          //> java.lang.StackOverflowError

还是会出现StackOverflow。这次是因为flatMap中的runT不在尾递归位置。那我们把Trampoline变成Monad看看如何?那我们就得为Trampoline增加一个flatMap函数:

 1 trait Trampoline[+A] {
 2  final def runT: A = this match {
 3       case Done(a) => a
 4       case More(k) => k().runT
 5   }
 6   def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = {
 7       this match {
 8           case Done(a) => f(a)
 9           case More(k) => f(runT)
10       }
11   }
12 }
13 case class Done[+A](a: A) extends Trampoline[A]
14 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]

这样我们可以把State.flatMap调整成以下这样:

 1 case class State[S,A](runS: S => Trampoline[(A,S)]) {
 2     def flatMap[B](f: A => State[S,B]): State[S,B] = State[S,B] {
 3         s => More(() => {
 4 //            val (a1,s1) = runS(s).runT
 5 //            More(() => f(a1) runS s1)
 6           runS(s) flatMap {   // runS(s) >>> Trampoline
 7             case (a1,s1) => More(() => f(a1) runS s1)
 8           }
 9         })
10     }
11   def map[B](f: A => B): State[S,B] = flatMap( a => unit(f(a)))
12 }

现在我们把递归算法都推到了Trampoline.flatMap这儿了。不过Trampoline.flatMap的runT引用f(runT)不在尾递归位置,所以这样调整还不足够。看来核心还是要解决flatMap尾递归问题。我们可以再为Trampoline增加一个状态结构FlatMap然后把flatMap函数引用变成类型实例构建(type construction):

1 case class Done[+A](a: A) extends Trampoline[A]
2 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
3 case class FlatMap[A,B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]

case class FlatMap这种Trampoline状态意思是先引用sub然后把结果传递到下一步k再运行k:基本上是沿袭flatMap功能。再调整Trampoline.resume, Trampoline.flatMap把FlatMap这种状态考虑进去:

 1 trait Trampoline[+A] {
 2  final def runT: A = resume match {
 3       case Right(a) => a
 4       case Left(k) => k().runT
 5   }
 6   def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = {
 7       this match {
 8 //          case Done(a) => f(a)
 9 //          case More(k) => f(runT)
10       case FlatMap(a,g) => FlatMap(a, (x: Any) => g(x) flatMap f)
11       case x => FlatMap(x, f)
12       }
13   }
14   def map[B](f: A => B) = flatMap(a => Done(f(a)))
15   def resume: Either[() => Trampoline[A], A] = this match {
16     case Done(a) => Right(a)
17     case More(k) => Left(k)
18     case FlatMap(a,f) => a match {
19         case Done(v) => f(v).resume
20         case More(k) => Left(() => k() flatMap f)
21         case FlatMap(b,g) => FlatMap(b, (x: Any) => g(x) flatMap f).resume
22     }
23   }
24 }
25 case class Done[+A](a: A) extends Trampoline[A]
26 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
27 case class FlatMap[A,B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]

在以上对Trampoline的调整里我们引用了Monad的结合特性(associativity):

FlatMap(FlatMap(b,g),f) == FlatMap(b,x => FlatMap(g(x),f)

重新右结合后我们可以用FlatMap正确表达复数步骤的运算了。

现在再试着运行zip:

 1 def zip[A](as: List[A]): List[(A,Int)] = {
 2     as.foldLeft(
 3       unit[Int,List[(A,Int)]](List()))(
 4       (acc,a) => for {
 5         xs <- acc
 6         n <- getState[Int]
 7         _ <- setState[Int](n + 1)
 8       } yield (a,n) :: xs
 9     ).runS(0).runT._1.reverse
10 }                                                 //> zip: [A](as: List[A])List[(A, Int)]
11 zip((1 to 10000).toList)                          //> res0: List[(Int, Int)] = List((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,

这次运行正常,再不出现StackOverflowError了。

实际上我们可以考虑把Trampoline当作一种通用的堆栈溢出解决方案。

我们首先可以利用Trampoline的Monad特性来调控函数引用,如下:

1 val x = f() 
2 val y = g(x) 
3 h(y)
4 //以上这三步函数引用可以写成:
5 for {
6  x <- f()
7  y <- g(x)
8  z <- h(y) 
9 } yield z

举个实际例子:

 1 implicit def step[A](a: => A): Trampoline[A] = {
 2     More(() => Done(a))
 3 }                                                 //> step: [A](a: => A)ch13.ex1.Trampoline[A]
 4 def getNum: Double = 3                            //> getNum: => Double
 5 def addOne(x: Double) = x + 1                     //> addOne: (x: Double)Double
 6 def timesTwo(x: Double) = x * 2                   //> timesTwo: (x: Double)Double
 7 (for {
 8     x <- getNum
 9     y <- addOne(x)
10     z <- timesTwo(y)
11 } yield z).runT                                   //> res6: Double = 8.0

又或者:

1 def fib(n: Int): Trampoline[Int] = {
2     if (n <= 1) Done(n) else for {
3         x <- More(() => fib(n-1))
4         y <- More(() => fib(n-2))
5     } yield x + y
6 }                                                 //> fib: (n: Int)ch13.ex1.Trampoline[Int]
7 (fib(10)).runT                                    //> res7: Int = 55

从上面得出我们可以用flatMap来对Trampoline运算进行流程控制。另外我们还可以通过把多个Trampoline运算交叉组合来实现并行运算:

 1 trait Trampoline[+A] {
 2  final def runT: A = resume match {
 3       case Right(a) => a
 4       case Left(k) => k().runT
 5   }
 6   def flatMap[B](f: A => Trampoline[B]): Trampoline[B] = {
 7       this match {
 8 //          case Done(a) => f(a)
 9 //          case More(k) => f(runT)
10       case FlatMap(a,g) => FlatMap(a, (x: Any) => g(x) flatMap f)
11       case x => FlatMap(x, f)
12       }
13   }
14   def map[B](f: A => B) = flatMap(a => Done(f(a)))
15   def resume: Either[() => Trampoline[A], A] = this match {
16     case Done(a) => Right(a)
17     case More(k) => Left(k)
18     case FlatMap(a,f) => a match {
19         case Done(v) => f(v).resume
20         case More(k) => Left(() => k() flatMap f)
21         case FlatMap(b,g) => FlatMap(b, (x: Any) => g(x) flatMap f).resume
22     }
23   }
24   def zip[B](tb: Trampoline[B]): Trampoline[(A,B)] = {
25     (this.resume, tb.resume) match {
26         case (Right(a),Right(b)) => Done((a,b))
27         case (Left(f),Left(g)) => More(() => f() zip g())
28         case (Right(a),Left(k)) => More(() => Done(a) zip k())
29         case (Left(k),Right(a)) => More(() => k() zip Done(a))
30     }
31   }
32 }
33 case class Done[+A](a: A) extends Trampoline[A]
34 case class More[+A](k: () => Trampoline[A]) extends Trampoline[A]
35 case class FlatMap[A,B](sub: Trampoline[A], k: A => Trampoline[B]) extends Trampoline[B]

我们可以用这个zip函数把几个Trampoline运算交叉组合起来实现并行运算:

1 def hello: Trampoline[Unit] = for {
2     _ <- print("Hello ")
3     _ <- println("World!")
4 } yield ()                                        //> hello: => ch13.ex1.Trampoline[Unit]
5 
6 (hello zip hello zip hello).runT                  //> Hello Hello Hello World!
7                                                   //| World!
8                                                   //| World!
9                                                   //| res8: ((Unit, Unit), Unit) = (((),()),())

用Trampoline可以解决StackOverflow这个大问题。现在我们可以放心地进行泛函编程了。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

【Spring实战】—— 4 Spring中bean的init和destroy方法讲解

本篇文章主要介绍了在spring中通过配置init-method和destroy-method方法来实现Bean的初始化和销毁时附加的操作。 在java中,...

1996
来自专栏C/C++基础

设计模式(11)——模板方法模式(Template Method Pattern,行为型)

模板方法模式(Template Method Pattern)属行为型,在一个方法中定义一个算法骨架,而将一些步骤延迟到子类中,使子类可以不改变算法结构即可重定...

622
来自专栏androidBlog

带你了解Android常见的内存缓存算法

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

351
来自专栏跟着阿笨一起玩NET

UML类图几种关系的总结

本文转载:http://blog.csdn.net/tianhai110/article/details/6339565

461
来自专栏熊二哥

快速入门系列--深入理解C#

C#语言在近些年得到了长足的方法,代码风格越来越简洁美观,例如常用的泛型及其约束、可空类型、隐式类型、匿名类型和委托等,通过下面的表格可以对这部分相对简单的特性...

1845
来自专栏HTML5学堂

2015.12.21 HTML5真题练习

HTML5学堂:每天一道题,强壮程序员!今日主要涉及12.18日关于字符串相关知识题目的解答,以及一道涉及数据类型的题目。 HTML5真题【2015.12.18...

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

Scalaz(35)- Free :运算-Trampoline,say NO to StackOverflowError

   在前面几次讨论中我们介绍了Free是个产生Monad的最基本结构。它的原理是把一段程序(AST)一连串的运算指令(ADT)转化成数据结构存放在内存里,这个...

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

Scalaz(27)- Inference & Unapply :类型的推导和匹配

 经过一段时间的摸索,用scala进行函数式编程的过程对我来说就好像是想着法儿如何将函数的款式对齐以及如何正确地匹配类型,真正是一种全新的体验,但好像有点太偏...

1838
来自专栏编程

记住这35个大神级别的Python操作,足够精简上千行代码!

从我开始学习python的时候,我就开始自己总结一个python小技巧的集合。后来当我什么时候在Stack Overflow或者在某个开源软件里看到一段很酷代码...

2327
来自专栏青玉伏案

代码重构(五):继承关系重构规则

陆陆续续的发表了多篇关于重构的文章了,还是那句话,重构是一个项目迭代开发中必不可少的一个阶段。其实重构伴随着你的项目的整个阶段。在前几篇关于重构的文章中我们谈到...

1816

扫码关注云+社区