# 泛函编程（7）－数据结构－List－折叠算法

折叠算法是List的典型算法。通过折叠算法可以实现众多函数组合（function composition）。所以折叠算法也是泛函编程里的基本组件（function combinator）。了解折叠算法的原理对了解泛函组合有着至关紧要的帮助。折叠算法又可分右折叠和左折叠。我们先从右折叠（foldRight）开始:

```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       }```

```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       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       }```

```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)))```

```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```

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))))```

``` 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       }```

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

```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))))```

`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 }```

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

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

210 篇文章59 人订阅

0 条评论

## 相关文章

### Dataset 列表：机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1831

### XML Encryption in .Net

XML Encryption in .Net One of the new features being introduced with the Whidbey...

4477

### Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1876

### App Guide相关

##TourGuide https://github.com/worker8/TourGuide

822

### 高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分，其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4

### 简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2349

### Effective Testing with RSpec 3 （英文版）(序言)

Early praise for Effective Testing with RSpec 3

1844

471

### OpenCv as配置

copy到opencv的javalib里面当so运行就可，调用initDebug初始化即可

1151

### Html5模拟通讯录人员排序（sen.js）

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6386