列表

使用列表

列表字面量

再简单回顾一下：

  val fruit = List("apples", "oranges", "pears")
  val nums = List(1, 2, 3, 4)
  val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
  val empty = List()

注意列表是不可变的。

列表类型

列表是同质化的（homogeneous），所有的成员都有相同的类型，中括号描述成员类型 List[T]。

val fruit: List[String] = List("apples", "oranges", "pears")
val nums: List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty: List[Nothing] = List()

Scala里的 不可变 列表类是协变的（covariant）。如果S是T的子类，那List[S] 也是List[T]的子类。

由于Nothing是所有类的子类，所以List[Nothing]是所有List[T]类型的子类：

  // List() is also of type List[String]!
  val xs: List[String] = List()

构造列表

Nil代表空列表；::（发音为「cons」），elm::list把单个元素elm接在列表list的前面。

  val fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
  val nums = 1 :: (2 :: (3 :: (4 :: Nil)))
  val diag3 = (1 :: (0 :: (0 :: Nil))) ::
              (0 :: (1 :: (0 :: Nil))) ::
              (0 :: (0 :: (1 :: Nil))) :: Nil
  val empty = Nil

由于操作符::是右结合性，所以：

A :: (B :: C)

相当于：

A :: B :: C

所以前一个例子中很多括号都可以省略：

  val nums = 1 :: 2 :: 3 :: 4 :: Nil

列表的基本操作

三个基本操作：head、tail、isEmpty。

  val fruit = "apples" :: "oranges" :: "pears" :: Nil
  val nums = 1 :: 2 :: 3 :: 4 :: Nil
  val diag3 = (1 :: (0 :: (0 :: Nil))) ::
              (0 :: (1 :: (0 :: Nil))) ::
              (0 :: (0 :: (1 :: Nil))) :: Nil
  val empty = Nil
  
empty.isEmpty // true
fruit.isEmpty // flase
fruit.head // "apples"
fruit.tail.head // "organges"
diag3.head // List(1, 0, 0)

head与tail只能用在非空列表上，不然抛异常：

  scala> Nil.head
  java.util.NoSuchElementException: head of empty list

一个排序的例子，使用插入排序：对于非空列表x::xs可以先排序xs。然后再把x插入 正确的地方：

  def isort(xs: List[Int]): List[Int] =
    if (xs.isEmpty) Nil
    else insert(xs.head, isort(xs.tail))

  def insert(x: Int, xs: List[Int]): List[Int] =
    if (xs.isEmpty || x <= xs.head) x :: xs
    else xs.head :: insert(x, xs.tail)

其他常用操作：

• 添加元素。在头部添加元素：1 :: 2 :: Nil
• 添加元素到尾部（需要遍历，性能较差）：List(1, 2, 3, 4, 5) :+ 6
• 连接列表，把两个列表连起来：List(1, 2) ::: List(2, 3)
• 添加集合，把另一个集合里的东西都加进去：List(1, 2) ++ Set(3, 4, 5)
• 检查相等，两个集合的类型和元素都相同：List(1, 2) == List(1, 2)
• 去重：List(1, 2, 3, 4, 5, 4, 3).distinct
• 删除，删除前n个元素：List('a', 'b', 'c') drop 2
• 删除，删除后n个元素（需要遍历，性能较差）：List('a', 'b', 'c') dropRight 2
• 过滤：List(1, 8, 5, 20, 3, 77, 66) filter (_ > 18)
• 降维，多维列表重组为一维的：List(List(1, 2, 3), List(4, 5, 6)).flatten
• 分区，按条件分为一个元组中的两个表：List(1, 2, 3, 4, 5) partition (_ < 3)
• 反序：List(1, 2, 3).reverse
• 分片：List(0, 1, 2, 3, 4, 5) slice (1, 3)
• 按条件排序：List("apple", "to") sortBy (_.size)
• 按默认类型属性排序：List("apple", "to").sorted
• 切分，按索引切分：List(2, 3, 5, 7) splitAt 2
• 取前n个元素：List(0, 1, 2, 3, 4, 5, 6) take 3
• 取后n个元素（需要遍历，性能较差）：List(0, 1, 2, 3, 4, 5, 6) takeRight 3
• 压缩两个列表：List(1, 2) zip List("a", "b")

映射并转换每一个元素：

scala> List("a", "b", "c") map (_.toUpperCase)
res13: List[String] = List(A, B, C)

用偏函数转换并采集元素：

scala> List(0, 1, 0).collect({case 0 => "ok"})
res8: List[String] = List(ok, ok)

转换每个元素后，重组为一维的表：

scala> List("milk,tea,coffee") map (_.split(','))     // 不重组到一维
res12: List[Array[String]] = List(Array(milk, tea, coffee))

scala> List("milk,tea,coffee") flatMap (_.split(',')) // 重组到一维
res11: List[String] = List(milk, tea, coffee)

数学归约操作：

• 最大的：List(1, 3, 2).max
• 最小的：List(1.1, 3.77, 2).min
• 所有元素求和：List(1, 2, 3).sum
• 所有元素相乘：List(1, 2, 3).product

布尔归约操作：

• 所有的元素都要满足每件：List(24, 17, 32) forall (_ < 18)
• 至少有一个元素都要满足每件：List(24, 17, 32) exists (_ < 18)
• 是否包含指定元素： List(1, 2, 3) contains 2 或 List(1, 2, 3) contains ((x: Int) => {x > 2})
• 以指定列表开头：List(1, 2, 3) startsWith List(0)
• 以指定列表结尾：List(1, 2, 3) endsWith List(2, 3)

通用的列表归约操作：

flod函数：

scala> List(1, 2, 3, 4, 5, 6).fold(0)(_ + _)
res4: Int = 21

scala> List(1, 2, 3, 4, 5, 6).foldLeft(0)(_ + _)
res5: Int = 21

scala> List(1, 2, 3, 4, 5, 6).foldRight(0)(_ + _)
res6: Int = 21

reduce函数：

scala> List(1, 2, 3, 4, 5, 6).reduce(_ + _)
res7: Int = 21

scala> List(1, 2, 3, 4, 5, 6).reduceLeft(_ + _)
res8: Int = 21

scala> List(1, 2, 3, 4, 5, 6).reduceRight(_ + _)
res9: Int = 21

scan函数：

scala> List(1, 2, 3, 4, 5, 6).scan(0)(_ + _)
res10: List[Int] = List(0, 1, 3, 6, 10, 15, 21)

scala> List(1, 2, 3, 4, 5, 6).scanLeft(0)(_ + _)
res11: List[Int] = List(0, 1, 3, 6, 10, 15, 21)

scala> List(1, 2, 3, 4, 5, 6).scanRight(0)(_ + _)
res12: List[Int] = List(21, 20, 18, 15, 11, 6, 0)

列表模式

简单的模式匹配，在确定长度的情况下取出列表里的元素：

  scala> val List(a, b, c) = fruit
  a: String = apples
  b: String = oranges
  c: String = pears

不确定具体长度但知道至少有几个，或是只要取前几个：

  scala> val a :: b :: rest = fruit
  a: String = apples
  b: String = oranges
  rest: List[String] = List(pears)

要注意这里的List(...)和::并不是之前定义的模式匹配。

实际上List(...)是将来会在抽取器章节介绍的抽取器模式。

「cos」模式：

x :: xs

是中缀操作符模式的特例，一般中缀表达式p op q视为p.op(q)。 但是如果作为模式，其实是被当作构造器模式的op(p,q)形式。

对应这个构造器模式的类是scala.::，它可以创建非空列表的类。还有一个List类的 方法::用来实例化scala.::的对象。在将来的「实现列表」章节中会有进一步的描述。

再次用模式匹配的方式来实现前面已经实现过的插入排序法：

  def isort(xs: List[Int]): List[Int] = xs match {
    case List() => List()                    // empty list
    case x :: xs1 => insert(x, isort(xs1))
  }

  def insert(x: Int, xs: List[Int]): List[Int] = xs match {
    case List() => List(x)                   // empty list
    case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys)
  }

List类的一阶方法

这里介绍的方法是List类的方法，所以是在独立的对象上被调用。

连接列表

连接两个列表的操作符是:::，例如：

  scala> List(1, 2) ::: List(3, 4, 5)
  res0: List[Int] = List(1, 2, 3, 4, 5)

  scala> List() ::: List(1, 2, 3)
  res1: List[Int] = List(1, 2, 3)

  scala> List(1, 2, 3) ::: List(4)
  res2: List[Int] = List(1, 2, 3, 4)

它也是右结合的：

xs ::: ys ::: zs

相当于：

xs ::: (ys ::: zs)

分治原则

手动实现一个连接列表的append方法。先用模式匹配把输入的列表拆分为更加简单的样本：

  def append[T](xs: List[T], ys: List[T]): List[T] =
    xs match {
      case List() => ys
      case x :: xs1 => x :: append(xs1, ys)
    }

以上代码的让ys操持完整而xs被一步步拆分并放到ys前面，所以把注意集中到xs的 模式匹配上。

再通过递归调用层层套用剩下的元素，通过添加单个元素的方法::连接列表。

列表长度

  scala> List(1, 2, 3).length
  res3: Int = 3

length方法要遍历整个列表来取得长度，所以判断是否为空一般用isEmpty而不用length。

取头和尾

head取头，tail取的是除了第一个元素外剩下列表。这两个方法的运行时间是常量。

last取尾，init取最后一个以外的列表。这两个方法会遍历整个列表。

  scala> val abcde = List('a', 'b', 'c', 'd', 'e')
  abcde: List[Char] = List(a, b, c, d, e)

  scala> abcde.last
  res4: Char = e

  scala> abcde.init
  res5: List[Char] = List(a, b, c, d)

对于空列表会抛异常

  scala> List().init
  java.lang.UnsupportedOperationException: Nil.init
   at scala.List.init(List.scala:544)
   at ...

  scala> List().last
  java.util.NoSuchElementException: Nil.last
   at scala.List.last(List.scala:563)
   at ...

反转列表

reverse是创建了一个新列表：

  scala> abcde.reverse
  res6: List[Char] = List(e, d, c, b, a)

  scala> abcde
  res7: List[Char] = List(a, b, c, d, e)

一些简单的规律：

xs.reverse.reverse equals xs

xs.reverse.init equals xs.tail.reverse
xs.reverse.tail equals xs.init.reverse
xs.reverse.head equals xs.last
xs.reverse.last equals xs.head

通过连接在尾部添加操作:::来实现反转：

  def rev[T](xs: List[T]): List[T] = xs match {
    case List() => xs
    case x :: xs1 => rev(xs1) ::: List(x)
  }

当然这样的效率低得很，因为列表要一个一个遍历才能找到最后一个元素。

前缀与后缀

take和drop取得或舍去列表指定长度个元素，长度超过时不会抛异常而是返回整个列表 或空列表。

  scala> abcde take 2
  res8: List[Char] = List(a, b)

  scala> abcde drop 2
  res9: List[Char] = List(c, d, e)

splitAt在指定位置拆分列表。

xs splitAt n

// equals

(xs take n, xs drop n)

例：

  scala> abcde splitAt 2
  res10: (List[Char], List[Char]) = (List(a, b),List(c, d, e))

取得指定元素

通过索引取得指定元素：

  scala> abcde apply 2 // rare in Scala
  res11: Char = c

  scala> abcde(2) // rare in Scala
  res12: Char = c

includes方法取得所有的索引列表：

  scala> abcde.indices
  res13: List[Int] = List(0, 1, 2, 3, 4)

zip

把两个列表组成对偶（二元组），如果长度不一样会丢弃长出来的：

  scala> abcde.indices zip abcde
  res14: List[(Int, Char)] = List((0,a), (1,b), (2,c), (3,d),
  (4,e))

  scala> val zipped = abcde zip List(1, 2, 3)
  zipped: List[(Char, Int)] = List((a,1), (b,2), (c,3))

如果是为了把元素和索引zip在一起，用zipWithIndex方法更有效：

  scala> abcde.zipWithIndex
  res15: List[(Char, Int)] = List((a,0), (b,1), (c,2), (d,3), (e,4))

toString 和 mkString

toString简单字符串化列表

  scala> abcde.toString
  res16: String = List(a, b, c, d, e)

mkString通过三个参数来指定前后包列表的字符和分隔列表元素的字符：

xs mkString (pre, sep, post)

还有两个变体：

xs mkString sep
// equals
xs mkString ("", sep, "")

xs mkString
// equals
xs mkString ""

例子：

  scala> abcde mkString ("[", ",", "]")
  res17: String = [a,b,c,d,e]

  scala> abcde mkString ""
  res18: String = abcde

  scala> abcde.mkString
  res19: String = abcde

  scala> abcde mkString ("List(", ", ", ")")
  res20: String = List(a, b, c, d, e)

还有一个addSting变体让结果添加到StringBuilder中，而不是作为结果返回：

  scala> val buf = new StringBuilder
  buf: StringBuilder =

  scala> abcde addString (buf, "(", ";", ")")
  res21: StringBuilder = (a;b;c;d;e)

列表的转换

List类的toArray和Array类的toList，列表和数组转来转去。

  scala> val arr = abcde.toArray
  arr: Array[Char] = Array(a, b, c, d, e)

  scala> arr.toString
  res22: String = Array(a, b, c, d, e)

  scala> arr.toList
  res23: List[Char] = List(a, b, c, d, e)

copyToArray把列表复制到数组中一会连续的空间内：

  xs copyToArray (arr, start)

start为开始的位置。当然还要保证数组中有足够的空间。例子：

  scala> val arr2 = new Array[Int](10)
  arr2: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

  scala> List(1, 2, 3) copyToArray (arr2, 3)

  scala> arr2.toString
  res25: String = Array(0, 0, 0, 1, 2, 3, 0, 0, 0, 0)

elements提供了通过枚举器访问列表元素的方法：

  scala> val it = abcde.elements
  it: Iterator[Char] = non-empty iterator

  scala> it.next
  res26: Char = a

  scala> it.next
  res27: Char = b

例：归并排序

归并排序：如果列表长度为0或是1，就算是已经排序好的，直接返回。长度大于1的列表 可以拆成两个长度接近的，每个再递归调用完成排序，再把返回的两个排序好的列表合并。

函数的实现用到了柯里化，接收元素之间的比较大小的函数和要排序的列表：

  def msort[T](less: (T, T) => Boolean)
      (xs: List[T]): List[T] = {

    def merge(xs: List[T], ys: List[T]): List[T] =
      (xs, ys) match {
        case (Nil, _) => ys
        case (_, Nil) => xs
        case (x :: xs1, y :: ys1) =>
          if (less(x, y)) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
      }

    val n = xs.length / 2
    if (n == 0) xs
    else {
      val (ys, zs) = xs splitAt n
      merge(msort(less)(ys), msort(less)(zs))
    }
  }

使用的方法：

  scala> msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
  res28: List[Int] = List(1, 3, 5, 7)

作为一个柯里化的例子，可以用下划线代表末指定的参数列表：

  scala> val intSort = msort((x: Int, y: Int) => x < y) _
  intSort: (List[Int]) => List[Int] = <function>

如果要改成倒序排序的话，只要换个比较函数：

  scala> val reverseIntSort = msort((x: Int, y: Int) => x > y) _
  reverseIntSort: (List[Int]) => List[Int] = <function>

上面的intSort和reverseIntSort都已经绑定了排序的方法，只要传入待排序的列表：

  scala> val mixedInts = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)
  mixedInts: List[Int] = List(4, 1, 9, 0, 5, 8, 3, 6, 2, 7)

  scala> intSort(mixedInts)
  res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

  scala> reverseIntSort(mixedInts)
  res1: List[Int] = List(9, 8, 7, 6, 5, 4, 3, 2, 1, 0)

List类的高阶函数

这里介绍的方法是List类的方法，所以是在独立的对象上被调用。

Scala中以操作符形式出现的高阶函数更加简洁地处理Java中用循环来处理的问题。

列表间映射

xs map fun把列表中每个元素用方法处理过后生成新列表。xs代表List[T]；fun 代表T => U的函数。

  scala> List(1, 2, 3) map (_ + 1)
  res29: List[Int] = List(2, 3, 4)

  scala> val words = List("the", "quick", "brown", "fox")
  words: List[java.lang.String] = List(the, quick, brown, fox)
 
  scala> words map (_.length)
  res30: List[Int] = List(3, 5, 5, 3)

  scala> words map (_.toList.reverse.mkString)
  res31: List[String] = List(eht, kciuq, nworb, xof)

flatMap和map类似，但它把所有元素连成一个列表：

  scala> words map (_.toList)
  res32: List[List[Char]] = List(List(t, h, e), List(q, u, i,
      c, k), List(b, r, o, w, n), List(f, o, x))

  scala> words flatMap (_.toList)
  res33: List[Char] = List(t, h, e, q, u, i, c, k, b, r, o, w,
      n, f, o, x)

flatMap和map合作建立出所有1 <= j < i < 5的(i, j)对偶：

  scala> List.range(1, 5) flatMap ( i => List.range(1, i) map (j => (i, j)) )
  res34: List[(Int, Int)] = List((2,1), (3,1), (3,2), (4,1),
      (4,2), (4,3))

上面的代码List.range(1, 5)产生从1到5的整数列表。对于其中的每项i再产生1到 i的列表。map产生(i, j)元组列表，这里的j<i。flatMpa对每个1到5之间的i 产生列表，并连接所有列表得到结果。

等同于以下循环结构：

for (i <- List.range(1, 5); j <- List.range(1, i)) yield (i, j)

foreach没有返回结果（或返回Unit）。如下对sum变量累加，但是没有返回值：

  scala> var sum = 0
  sum: Int = 0

  scala> List(1, 2, 3, 4, 5) foreach (sum += _)

  scala> sum
  res36: Int = 15

过滤

xs filter p，xs代表List[T]，p代表T => Boolean形式的函数。返回符合的结果列表：

  scala> List(1, 2, 3, 4, 5) filter (_ % 2 == 0)
  res37: List[Int] = List(2, 4)

  scala> words filter (_.length == 3)
  res38: List[java.lang.String] = List(the, fox)

partition方法返回的是所有符合的元素和所有不符合的元素两个列表对。

xs partition p
// equals
( xs filter p , xs filter (!p(_)) )

例：

  scala> List(1, 2, 3, 4, 5) partition (_ % 2 == 0)
  res39: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))

find方法只返回第一个符合的元素，一个都不符合返回None：

  scala> List(1, 2, 3, 4, 5) find (_ % 2 == 0)
  res40: Option[Int] = Some(2)

  scala> List(1, 2, 3, 4, 5) find (_ <= 0)
  res41: Option[Int] = None

takeWhile不断累积符合的结果直到遇到不符合的；dropWhile不断丢弃不符的元素直到 遇到符合的。

  scala> List(1, 2, 3, -4, 5) takeWhile (_ > 0)
  res42: List[Int] = List(1, 2, 3)

  scala> words dropWhile (_ startsWith "t")
  res43: List[java.lang.String] = List(quick, brown, fox)

span方法组合了takeWhile和dropWhile返回一对列表，就像是splitAt组合了 take和drop一样。

xs span p
// equals
(xs takeWhile p , xs dropWhile p)

和split一样，span避免对列表的二次访问：

  scala> List(1, 2, 3, -4, 5) span (_ > 0)
  res44: (List[Int], List[Int]) = (List(1, 2, 3),List(-4, 5))

列表论断

xs forall p全部符合，xs exits p存在符合的元素。

  scala> def hasZeroRow(m: List[List[Int]]) =
       | m exists (row => row forall (_ == 0))
  hasZeroRow: (List[List[Int]])Boolean

  scala> hasZeroRow(diag3)
  res45: Boolean = false

reduce与folder

化简（reduce）

reduceLeft操作：

List(1, 2, 3, 4).reduceLeft(_ + _)
// 相当于
((1 + 2) + 3) + 4

reduceRight操作：

List(1, 2, 3, 4).reduceRight(_ + _)
// 相当于
((4 + 3) + 2) + 1

折叠（folder）

左折叠操作符/:，格式为：(z /: xs) (op)。其中z为开始值，xs为列表，op为二元操作。

(z /: List(a, b, c)) (op)
// equals
op(op(op(z,a), b), c)

用树表示：

      op
     / \
    op  c
   / \
  op  b
 / \
z   a

举例：

  scala> def sum(xs: List[Int]): Int = (0 /: xs) (_ + _)
  sum: (List[Int])Int
  
  scala> sum(List(1, 2, 3)) // equals 0 + 1 + 2 + 3
  res1: Int = 6

  scala> def product(xs: List[Int]): Int = (1 /: xs) (_ * _)
  product: (List[Int])Int
  
  scala> product(List(1, 2, 3)) // equals 1 * 1 * 2 * 3
  res2: Int = 6

用空格连接所有单词：

  scala> ("" /: words) (_ +" "+ _)
  res46: java.lang.String = the quick brown fox

头上多了一个空格，这样去掉它：

  scala> (words.head /: words.tail) (_ +" "+ _)
  res47: java.lang.String = the quick brown fox

相对的还有右倾斜操作树:\：

(List(a, b, c) :\ z) (op)
// equals
op(a, op(b, op(c, z)))

对于组合操作来说，左右折叠是等价的，但效率上有差异。下面两个把元素连接在一起的 方法：

  def flattenLeft[T](xss: List[List[T]]) =
      (List[T]() /: xss) (_ ::: _)

  def flattenRight[T](xss: List[List[T]]) =
      (xss :\ List[T]()) (_ ::: _)

采用右折叠的flattenLeft需要复制第一个元素列表xss.head一共xss.length-1次， 所以效率差一些。

注意这里两个版本的实现都要对作为折叠开始值的空列表做类型标注。这是由Scala类型 推断的局限性无法推断出正确的类型。不标注的话会有以下错误：

  scala> def flattenRight[T](xss: List[List[T]]) =
       | (xss :\ List()) (_ ::: _)
  <console>:15: error: type mismatch;
   found : List[T]
   required: List[Nothing]
             (xss :\ List()) (_ ::: _)
                                ^

在以后的「实现列表」章节中讨论类型推断失败的原因。

如果觉得/:和:\看起来不清楚，可以用List提供的foldLeft和foldRight方法代替 。比如下面这个查找最大元素的方法：

scala> def findMax(l:List[Int]) = {
     | l.foldLeft(Integer.MIN_VALUE) {Math.max}
     | }
findMax: (l: List[Int])Int

scala> findMax(List(-77,99,-3,18,7,21))
res0: Int = 99

应用场景

reduce与folder更加适合：「两两操作」的结果「继承」到「下一个元素」。

例子：统计字母出现次数

(Map[Char, Int]() /: "Mississippi") {
  (m, c) => m + (c -> (m.getOrElse(c, 0) + 1))
}

res1: scala.collection.immutable.Map[Char,Int] = 
					Map(M -> 1, i -> 4, s -> 4, p -> 2)

例子：使用折叠实现列表反转

def reverseLeft[T](xs: List[T]) = (startvalue /: xs) (operation)

为了写出正确的startvalue和operation，从可以出现的最小的列表List()开始推导：

List()
// equals
reverseLeft(List())
// equals
(startvalue /: List()) (operation)
// equals
startvalue

所以startvalue一定是List()。再代入推导operation：

List(x)
// equals
reverseLeft(List(x))
// equals
(startvalue /: List(x)) (operation)
// equals
operation(List(), x)
// equals
x :: List()

所以具体实现为：

  def reverseLeft[T](xs: List[T]) =
    (List[T]() /: xs) {(ys, y) => y :: ys}

扫描（scan）

scanLeft和scanRight是把folder和map操作结合在一起。返回的结果是包含所有 中间结果的集合：

scala> (1 to 10).scanLeft(0)(_ + _)
res2: scala.collection.immutable.IndexedSeq[Int] = 
		Vector(0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55)

排序

xs sort before，xs是列表，before是比较元素x是否在y前面的方法。

  scala> List(1, -3, 4, 2, 6) sort (_ < _)
  res48: List[Int] = List(-3, 1, 2, 4, 6)

  scala> words sort (_.length > _.length)
  res49: List[java.lang.String] = List(quick, brown, fox, the)

注意前面还提到过一个msort方法，那个是定义在列表外的。sort是List类的方法。

sortWith排序：

scala> "Mary has a little lamb".split(" ").sortWith(_.length < _.length)
res0: Array[String] = Array(a, has, Mary, lamb, little)

List伴生对象的方法

下面介绍的方法是伴生对象scala.List的，创建列表的工厂方法和特定类型列表的操作。

通过元素创建列表

apply方法：

List(1, 2, 3)
// is actually
List.apply(1, 2, 3)

按数值范围创建列表

range参数可以是：开始、结束、步长：

  scala> List.range(1, 5)
  res51: List[Int] = List(1, 2, 3, 4)

  scala> List.range(1, 9, 2)
  res52: List[Int] = List(1, 3, 5, 7)

  scala> List.range(9, 1, -3)
  res53: List[Int] = List(9, 6, 3)

创建重复元素的列表

make方法：

  scala> List.make(5, 'a')
  res54: List[Char] = List(a, a, a, a, a)

  scala> List.make(3, "hello")
  res55: List[java.lang.String] = List(hello, hello, hello)

解除Zip列表

unzip把二元组列表分成两个列表：

  scala> val zipped = "abcde".toList zip List(1, 2, 3)
  zipped: List[(Char, Int)] = List((a,1), (b,2), (c,3))

  scala> List.unzip(zipped)
  res56: (List[Char], List[Int]) = (List(a, b, c),
      List(1, 2, 3))

Scala类型系统要求类方法能处理所有类型，而unzip只处理二元组列表。所以unzip不能像 zip方法一样放在类里而只能放在伴生对象里。

连接列表

flatten方法只能处理包含子列表的列表所以不能放在List类里。只能放在伴生对象中。

  scala> val xss =
       | List(List('a', 'b'), List('c'), List('d', 'e'))
  xss: List[List[Char]] = List(List(a, b), List(c), List(d, e))

  scala> List.flatten(xss)
  res57: List[Char] = List(a, b, c, d, e)

concat方法把多个列表作为可变长参数形式接收：

  scala> List.concat(List('a', 'b'), List('c'))
  res58: List[Char] = List(a, b, c)

  scala> List.concat(List(), List('b'), List('c'))
  res59: List[Char] = List(b, c)
  
  scala> List.concat()
  res60: List[Nothing] = List()

映射与测试配对

map2方法接收两个列表，分别作为方法的两个参数：

  scala> List.map2(List(10, 20), List(3, 4, 5)) (_ * _)
  res61: List[Int] = List(30, 80)

exist2也是接收两个列表，分别作为方法的两个参数：

  scala> List.forall2(List("abc", "de"),
       | List(3, 2)) (_.length == _)
  res62: Boolean = true

  scala> List.exists2(List("abc", "de"),
       | List(3, 2)) (_.length != _)
  res63: Boolean = false

了解Scala的类型推断方法

Scala的类型推导器是基于流的。

下面是用占位符_推导出的参数类型：

  scala> abcde sort (_ > _)
  res65: List[Char] = List(e, d, c, b, a)

例如对于List[Char]类型的列表abcd，abcd的成员都是Char。所以 abcd.sort(_ > _)的两个参数也只会是Char。所以类型被推导为：

(_ > _)
// trans to
((x: Char, y: Char) => x > y)

再来看msort方法：

  scala> msort((x: Char, y: Char) => x > y)(abcde)
  res64: List[Char] = List(e, d, c, b, a)

msort方法却不能用占位符：

  scala> msort(_ > _)(abcde)
  <console>:12: error: missing parameter type for expanded
  function ((x$1, x$2) => x$1.$greater(x$2))
         msort(_ > _)(abcde)
               ^

原因是对于func(args)这样的方法，先看func是否有已经的类型。如果有的话这个类型 就被用来做参数预期类型的推断。而msort(_ > _)(abcde)这个类型是柯里化的、多态的 方法类型，参数类型是(T, T) => Boolean，返回类型是从List[T]到List[T]的函数 。无法推断第一个参数的类型。所以类型推断器要参数的类型信息。

想要用占位符的话，只能把参数类型传给msort，改为msort[Char]：

  scala> msort[Char](_ > _)(abcde)
  res66: List[Char] = List(e, d, c, b, a)

还有一个方法是交换参数顺序，这样可以用第一个列表的类型来推断比较方法的类型了：

  // same implementation as msort,
  // but with arguments swapped
  def msortSwapped[T](xs: List[T])(less:
      (T, T) => Boolean): List[T] = {
  }
  
  scala> msortSwapped(abcde)(_ > _)
  res67: List[Char] = List(e, d, c, b, a)

需要推断多态方法类型时只会参考第一个参数列表，所以在柯里化方法有两个参数列表时 第二个参数不会用来决定方法类型参数。所以这种方案隐含以下的库方法设计原则：

如果参数包括若干个非函数参数与一个函数参数的组合时，要把函数参数独自放在柯里化 参数列表的最后面。这样方法的正确实例类型就可以通过非函数参数推断出来，推断出来的 类型还可以转面用来完成函数参数的类型检查。调用函数的时候也可以写出更加简洁的 字面量。

再来看更加复杂的折叠操作：

  (xss :\ List[T]()) (_ ::: _)

上面的表达式提供了明确的类型参数的原因是这个右折叠操作的类型取决于两个变量：

  (xs :\ z) (op)

这里把列表xs的类型记为A，如：xs: List[A]；而开始值z有可能是类型B。对应 的操作op必须以A和B的值为参数并返回类型B的结果，即：op: (A, B) => B。

从上面的描述可以看出：这里的op方法要知道A与B两个类型。A一定与List有关 ，但是B不一定与List有关，所以推不出来。所以下面的表达式是编译不过的：

  (xss :\ List()) (_ ::: _) // this won't compile

上面表达式中z的类型为List[Nothing]，据此推断器把B的类型定为Nothing：

  (List[T], List[Nothing]) => List[Nothing]

这就意味着输出与输出都是空列表。

就是因为这个问题，所以在柯里化的方法中，方法类型只取决于第一段参数。但是如果不 这么做的话，推断器还是没有办法取得op的类型。所以只能程序员明确指定类型。

所以Scala采用的局部的、基于流的类型推断方法还是比较有局限性的；不如ML或是Haskell 采用的更加全局化的Hindley-Milner类型推断方式。但是对于面向对象的分支类型处理比 Hindley-Mlner更加优雅。由于这些局限性在比较极端的情况下才遇到，所以在极端情况下 还是明确标类型吧。

另外在遇到多态类型错误时，添加上你认为应该是正确的类型标注也是一种排错方式。