# 泛函编程（6）－数据结构－List基础

List是一种最普通的泛函数据结构，比较直观，有良好的示范基础。List就像一个管子，里面可以装载一长条任何类型的东西。如需要对管子里的东西进行处理，则必须在管子内按直线顺序一个一个的来，这符合泛函编程的风格。与其它的泛函数据结构设计思路一样，设计List时先考虑List的两种状态：空或不为空两种类型。这两种类型可以用case class 来表现:

`1 trait List[+A] {}2 case class Cons[+A](head: A, tail: List[A]) extends List[A]3 case object Nil extends List[Nothing]`

List的另一种实现方式：

`1 trait List[+A] {2  def node: Option[(A, List[A])]3 def isEmpty = node.isEmpty4  }5  object List {6 def empty[A] = new List[A] { def node = None}7 def cons[A](head: A, tail: List[A]) = new List[A] { def node = Some((head, tail))}8 }`

`1  object List {2 def apply[A](as: A*): List[A] = {3 if (as.isEmpty) Nil4 else Cons(as.head,apply(as.tail:_*))5  }6 }`

`1 scala> Array(1,2,3).head2 res11: Int = 134 scala> Array(1,2,3).tail5 res12: Array[Int] = Array(2, 3)`

`1 val li = List(1,2,3) //> li : ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Nil)))2 val ls = List("one","two","three") //> ls : ch3.list.List[String] = Cons(one,Cons(two,Cons(three,Nil)))`

`1 val lInt = Cons(1,Cons(2,Cons(3,Nil))) //> lInt : ch3.list.Cons[Int] = Cons(1,Cons(2,Cons(3,Nil)))`

`1 trait List[+A] {2 def sum: Int = this match {3 case Nil => 04 case Cons(h: Int,t: List[Int]) => h + t.sum5  }6 }`

`1 List(1,2,3) sum //> res0: Int = 6`

`1 def sum[B >: A](z: B)(f: (B,B) => B): B = this match {2 case Nil => z3 case Cons(h,t) => f(h, t.sum(z)(f))4 }`

`1 List(1,2,3).sum(0){_ + _} //> res0: Int = 62 List("hello",",","World","!").sum(""){_ + _} //> res1: String = hello,World!`

` 1 trait List[+A] { 2 3 def head: A = this match { 4 case Nil => sys.error("Empty List!") 5 case Cons(h,t) => h 6  } 7 def tail: List[A] = this match { 8 case Nil => sys.error("Empty List!") 9 case Cons(h,t) => t10  }11 def take(n: Int): List[A] = n match {12 case k if(k<0) => sys.error("index < 0 !")13 case 0 => Nil14 case _ => this match {15 case Nil => Nil16 case Cons(h,t) => Cons(h,t.take(n-1))17  }18  }19 def takeWhile(f: A => Boolean): List[A] = this match {20 case Nil => Nil21 case Cons(h,t) => if(f(h)) Cons(h,t.takeWhile(f)) else Nil22  }23 def drop(n: Int): List[A] = n match {24 case k if(k<0) => sys.error("index < 0 !")25 case 0 => this26 case _ => this match {27 case Nil => Nil28 case Cons(h,t) => t.drop(n-1)29  }30  }31 def dropWhile(f: A => Boolean): List[A] = this match {32 case Nil => Nil33 case Cons(h,t) => if (f(h)) t.dropWhile(f) else this34  }35 }`

`1 List(1,2,3).head //> res0: Int = 12 List(1,2,3).tail //> res1: ch3.list.List[Int] = Cons(2,Cons(3,Nil))3 List(1,2,3).take(2) //> res2: ch3.list.List[Int] = Cons(1,Cons(2,Nil))4 List(1,2,3).takeWhile(x => x < 3) //> res3: ch3.list.List[Int] = Cons(1,Cons(2,Nil))5 List(1,2,3) takeWhile {_ < 3} //> res4: ch3.list.List[Int] = Cons(1,Cons(2,Nil))6 List(1,2,3).drop(2) //> res5: ch3.list.List[Int] = Cons(3,Nil)7 List(1,2,3).dropWhile(x => x < 3) //> res6: ch3.list.List[Int] = Cons(3,Nil)8 List(1,2,3) dropWhile {_ < 3} //> res7: ch3.list.List[Int] = Cons(3,Nil)`

`1 def ++[B >: A](a: List[B]): List[B] = this match {2 case Nil => a3 case Cons(h,t) => Cons(h,t.++(a))4 }`

`1 ist(1,2) ++ List(3,4) //> res8: ch3.list.List[Int] = Cons(1,Cons(2,Cons(3,Cons(4,Nil))))`

`1 def init: List[A] = this match {2 case Cons(_,Nil) => Nil3 case Cons(h,t) => Cons(h,t.init)4  }5 def length: Int = this match {6 case Nil => 07 case Cons(h,t) => 1 + t.length8 }`

`1 List(1,2,3).init //> res9: ch3.list.List[Int] = Cons(1,Cons(2,Nil))2 List(1,2,3).length //> res10: Int = 3`

` 1 def map[B](f: A => B): List[B] = this match { 2 case Nil => Nil 3 case Cons(h,t) => Cons(f(h),( t map f)) 4  } 5 def flatMap[B]( f: A => List[B]): List[B] = this match { 6 case Nil => Nil 7 case Cons(h,t) => f(h) ++ ( t flatMap f ) 8  } 9 def filter(f: A => Boolean): List[A] = this match {10 case Nil => Nil11 case Cons(h,t) => if (f(h)) Cons(h,t.filter(f)) else t.filter(f)12 }`

`1 List(1,2,3) map {_ + 10} //> res13: ch3.list.List[Int] = Cons(11,Cons(12,Cons(13,Nil)))2 List(1,2,3) flatMap {x => List(x+10)} //> res14: ch3.list.List[Int] = Cons(11,Cons(12,Cons(13,Nil)))3 List(1,2,3) filter {_ != 2} //> res15: ch3.list.List[Int] = Cons(1,Cons(3,Nil))`

Top