当前位置:必发365电子游戏 > 编程 > c)的右折叠算法
c)的右折叠算法
2019-12-19

     折叠算法是List的一级算法。通过折叠算法能够兑现广大函数组合(function composition)。所以折叠算法也是泛函编制程序里的主导组件(function combinator)。精晓折叠算法的原理对驾驭泛函组合具备显要的提携。折叠算法又可分右折叠和左折叠。大家先从右折叠(foldRight)开端:

 图片 1图片 2

从上述两图示能够得出对List(a,b,c卡塔尔的右折叠算法:op(a,op(b,op(c,z卡塔尔(英语:State of Qatar)卡塔尔卡塔尔(قطر‎能够看看括号是从右初始的。总结方法如图二:op(a,sub卡塔尔国, sub是双重子树,能够一定要用递归算法。这里z代表了二个开头值。大家后天得以推算出foldRight的函数款式(function signature)了:

1       def foldRight[A,B](l: List[A], z: B)(op: (A,B) => B): B = l match {
2           case Nil => z
3           case Cons(h,t) => op(h,foldRight(t,z)(f))
4       }

小心foldRight不是一个尾递归算法(tail recursive)。大家试着对三个List(1,2,3卡塔尔国举办操作,先来个加法: 

1 foldRight(List(1,2,3),0)((x,y) => x + y)          //> res13: Int = 6
2 foldRight(List(1,2,3),0){_ + _}                   //> res14: Int = 6

大家能够用”等量替换“方法简便:

1  // (List(x1,x2,x3...x{n-1}, xn) foldRight acc) op => x1 op (...(xn op acc)...)
2  // foldRight(Cons(1,Cons(2,Cons(3,Nil))), 0) {_ + _}
3  // 1 + foldRight(Cons(2,Cons(3,Nil)), 0) {_ + _}
4  // 1 + (2 + foldRight(Cons(3,Nil), 0) {_ + _})
5  // 1 + (2 + (3 + foldRight(Nil, 0) {_ + _}))
6  // 1 + (2 + (3 + 0)) = 6

1 foldRight(List(1,2,3),1){_ * _}                   //> res16: Int = 6
2 foldRight(List(1,2,3),Nil:List[Int]) { (a,b) => Cons(a+10,b) }
                                                    //> res17: ch3.list.List[Int] = Cons(11,Cons(12,Cons(13,Nil)))

当心上述的初叶值1和Nil:List[Int]。z的等级次序能够不是A,所以op的结果也可以有不小可能率不是A类型,但在上述的加法和乘法的例子里z都以Int类型的。但在List重构例子里z是List[Int]花色,所以op的结果也是List[Int]品类的,那一点要非常注意。

再来看看左折叠算法:

图片 3图片 4

从上述图示分析,左折叠算法正是具备List成分对z的操作op。从图二可知,op对z,a操作后op的结果再作为z与b再开展op操作,如此循环。看来又是二个递归算法,而z正是三个用op积攒的值了:op(op(op(z,a卡塔尔(قطر‎,b卡塔尔(英语:State of Qatar),c卡塔尔。左折叠算法的括号是从左侧开头的。来拜谒foldLeft的得以完成:

1       def foldLeft[A,B](l: List[A], acc: B)(op: (B,A) => B): B = l match {
2           case Nil => acc
3           case Cons(h,t) => foldLeft(t,op(acc,h))(op)
4       }

小心z (zero卡塔尔(قطر‎ 形成了 acc (accumulator),op: (B,A卡塔尔 = B, 和foldRight的op函数入参顺序是背本趋末的。foldLeft是个尾递归方法。

1 foldLeft(List(1,2,3),0)((b,a) => a + b)           //> res18: Int = 6
2 foldLeft(List(1,2,3),0){_ + _}                    //> res19: Int = 6
3 foldLeft(List(1,2,3),1)((b,a) => a * b)           //> res20: Int = 6
4 foldLeft(List(1,2,3),1){_ * _}                    //> res21: Int = 6
5 foldLeft(List(1,2,3),Nil:List[Int]) { (b,a) => Cons(a+10,b) }
6                                                   //> res22: ch3.list.List[Int] = Cons(13,Cons(12,Cons(11,Nil)))

上述加法和乘法的积攒值acc都是A类型,但只顾List重构的acc是List[Int]类型的,这时候op入参的任务就很注重了。再在乎一下,foldLeft重构的List的要素排列是反向的Cons(13,Cons(12,Cons(11,Nil卡塔尔(英语:State of Qatar)卡塔尔(英语:State of Qatar)。大家仍可以用“等量替换”方法实行简要:

1 // (List(x1,x2,x3...x{n-1}, xn) foldLeft acc) op => (...(acc op x1) op x2)...) op x{n-1}) op xn
2  // foldLeft(Cons(1,Cons(2,Cons(3,Nil))), 0) {_ + _}
3  // foldLeft(Cons(2,Cons(3,Nil)), (0 + 1)) {_ + _}
4  // foldLeft(Cons(3,Nil), ((0 + 1) + 2)) {_ + _}
5  // foldLeft(Nil, (((0 + 1) + 2) + 3)) {_ + _}
6  // (((0 + 1) + 2) + 3) + 0 = 6

除foldRight,foldLeft之外,折叠算法还包涵了:reduceRight,reduceLeft,scanRight,scanLeft。

 图片 5图片 6

reduceLeft是以率先个,reduceRight是以最后三个List成分作为初步值的折叠算法,未有独自的初叶值:

1       def reduceLeft[A](l: List[A])(op: (A,A) => A): A = l match {
2           case Nil => sys.error("Empty list!")
3           case Cons(h,t) => foldLeft(t,h)(op)
4       }
5       def reduceRight[A](l: List[A])(op: (A,A) => A): A = l match {
6           case Cons(h,Nil) => h
7           case Cons(h,t) => op(h,reduceRight(t)(op))
8       }

1  reduceLeft(List(1,2,3)) {_ + _}                  //> res23: Int = 6
2  reduceRight(List(1,2,3)) {_ + _}                 //> res24: Int = 6

scanLeft, scanRight 分别把每回op的结果插入新产生的List作为重返结果。

 先实现scanLeft:

1        def scanLeft[A](l: List[A],z: A)(op: (A,A) => A): List[A] = l match {
2            case Nil => Cons(z,Nil)
3            case Cons(h,t) => Cons(z,scanLeft(t,op(z,h))(op))
4        }

1 scanLeft(List(1,2,3),0) {_ + _}                   //> res25: ch3.list.List[Int] = Cons(0,Cons(1,Cons(3,Cons(6,Nil))))

索求简约:

 1  // (List(x1,x2,x3...x{n-1}, xn) scanLeft acc) op => (...(acc op x1) op x2)...) op x{n-1}) op xn
 2  // scanLeft(Cons(1,Cons(2,Cons(3,Nil))), 0) {_ + _}
 3  // Cons(0,scanLeft(Cons(1,Cons(2,Cons(3,Nil))), 0) {_ + _})
 4  // Cons(0,Cons((0 + 1), scanLeft(Cons(2,Cons(3,Nil)), (0 + 1)) {_ + _}))
 5  // ==> Cons(0,Cons(1,scanLeft(Cons(2,Cons(3,Nil)), 1) {_ + _}))
 6  // Cons(0,Cons(1,Cons(2 + 1,scanLeft(Cons(3,Nil), 1 + 2) {_ + _})))
 7  // ==> Cons(0,Cons(1,Cons(3,scanLeft(Cons(3,Nil), 3) {_ + _})))
 8  // Cons(0,Cons(1,Cons(3,Cons(3 + 3,foldLeft(Nil, 3 + 3) {_ + _}))))
 9  // ==> Cons(0,Cons(1,Cons(3,Cons(6,foldLeft(Nil, 6) {_ + _}))))
10  // Cons(0,Cons(1,Cons(3,Cons(6,Nil))))

再实现scanRight:

 1     def reverse[A](l: List[A]): List[A] = foldLeft(l,Nil:List[A]){(acc,h) => Cons(h,acc)}
 2        
 3        def scanRight[A](l: List[A],z: A)(op: (A,A) => A): List[A] =  {
 4                 var scanned = List(z)
 5                 var acc = z
 6                 var ll = reverse(l)
 7                 var x = z
 8                 while (
 9                 ll match {
10                              case Nil => false
11                              case Cons(h,t) => { x = h; ll = t; true }
12                 }
13             ) {
14                         acc = op(acc,x)
15                            scanned = Cons(acc,scanned)
16                 }
17          scanned
18       }

事实上未能想出用递归算法达成scanRight的办法,只可以用while loop来化解了。注意纵然应用了暂且变量,但这么些变量都以本地密封的,所以scanRight依然纯函数。scanRight成分遍历(traverse)顺序是反向的,所以用reverse函数把List(1,2,3卡塔尔先成为List(3,2,1卡塔尔(قطر‎。

 

1 scanRight(List(1,2,3),0) {_ + _}                  //> res26: ch3.list.List[Int] = Cons(6,Cons(5,Cons(3,Cons(0,Nil))))

在意scanRight和scanLeft的结果分歧。这是因为算法分化:成分遍历(traverse)顺序分裂。

上边开首示范一下折叠算法作为宗旨组件(combinator)来贯彻部分函数功效:

上次兑现了函数++,即append。大家意气风发致能够用foldLeft和foldRight来完结:

1       def appendByFoldRight[A](l1: List[A], l2: List[A]): List[A] = foldRight(l1,l2){(h,acc) => Cons(h,acc)}
2       def appendByFoldLeft[A](l1: List[A], l2: List[A]): List[A] = foldLeft(reverse(l1),l2){(acc,h) => Cons(h,acc)}

1 appendByFoldLeft(List(1,2),List(3,4))             //> res27: ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Nil))))
2 appendByFoldRight(List(1,2),List(3,4))            //> res28: ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Nil))))

是因为append的功力是将多个List拼接起来,必需有限支撑最后结果List成分的次第。所以在appendByFoldLeft里接收了reverse。再介意foldLeft和foldRight在op参数地方是相反的。

事情未发生前递归算法完结的函数有个别是足以用折叠算法达成的:

1       def map_1[A,B](l: List[A])(f: A => B): List[B] = foldRight(l,Nil: List[B]){(h,acc) => Cons(f(h),acc)}

1       def filter_1[A](l: List[A])(f: A => Boolean): List[A] = foldRight(l,Nil: List[A]){(h,acc) => if (f(h)) Cons(h,acc) else acc }
2       def flatMap_1[A,B](l: List[A])(f: A => List[B]): List[B] = foldRight(l,Nil: List[B]){(h,acc) => appendByFoldRight(f(h),acc)}

1       def lengthByFoldRight[A](l: List[A]): Int = foldRight(l,0){(_,acc) => acc + 1 }
2       def lengthByFoldLeft[A](l: List[A]): Int = foldLeft(l,0){(acc,_) => acc + 1 }

c)的右折叠算法。还有个别相比直接的:

1     def conCat[A](ll: List[List[A]]): List[A] = foldRight(ll,Nil: List[A]){appendByFoldRight}

那些函数能够用来促成flatMap:

 

1      def flatMap_1[A,B](l: List[A])(f: A => List[B]): List[B] = conCat(map(l)(f))

假如精通以上函数完结方式有困难时方可先从品种相配上伊始,也许试着用“等量替换”方法大概追踪一下。