Chapter 16 《Working with Lists》
2018-06-28 本文已影响5人
liqing151
列表
- 不同于数组，列表的元素是不能改变的，列表是链表。
- 同一个列表的所有元素都必须是相同类型的。元素类型为
T的列表类型为List[T]。注意T可能是Any这样的父类。Scala的List是协变的，List[Child]是List[Father]的子类。空列表的类型为List[Nothing]，因此是任何List[T]的子类型。可以使用空列表List()也就是Nil来构建列表。
- 同一个列表的所有元素都必须是相同类型的。元素类型为
- 所有的列表都构建自两个基础单元，一个是
Nil，一个是::。::是中缀表示符，在列表前添加元素。
- 所有的列表都构建自两个基础单元，一个是
列表的基本操作
head，tail，isEmpty。head和tail只对非空列表有定义，否则会抛出异常。
列表模式
- 列表也可以使用模式匹配解开。
a::b::list可以匹配长度大于等于2的列表。a::Nil表示只有一个元素的列表，推荐使用列表模式来对列表进行解构。
- 列表也可以使用模式匹配解开。
- 匹配列表最常见的方式是区分空列表和非空列表。
List的初阶方法
入参中没有函数的方法成为称为方法。
-
- 拼接两个列表
:::
-
:::入参为两个列表，返回结果为包含了这两个列表所有元素的一个列表，列表的返回类型是两个列表元素类型继承树上的最近公共父节点。也是右结合的操作符。 - 对列表的操作用的比较多的是分而治之的思想。许多对列表的算法都首先使用模式匹配将输入的列表切分为更小的样例，这是分的思想，然后对每个样例构建对应的结果，如果结果是一个非空的列表，那么这个列表的局部可以通过递归的调用同一个算法来实现，这是治的思想。
- 拼接两个列表
- 获取列表长度：
length
这个不同于数组，需要更长的时间，所以如果使用xs.isEmpty的时刻，最好不要使用xs.length == 0。isEmpty直接定义在了::类和Nil类中。
- 获取列表长度：
- 访问列表的末端：
init和last，和head以及tail是对偶方法。
当应用到空列表的时候会出错。head和tail在访问的时候消耗的常量时间，但init和last消耗的是线性时间，所以一般使用的都是head和tail
- 访问列表的末端：
- 反转列表：
reverse
如果在算法中需要频繁的访问列表的末尾元素，可以先将列表进行反转，然后再将列表反转回原样。
- 反转列表：
- 前缀和后缀：
drop，take，splitAt
take返回前n个元素，如果n>list.length，那么就返回整个列表；
drop表示丢弃前n个元素，如果n>list.length，那么就返回空列表；
splitAt操作将列表从指定的位置切开，生成对偶(list take n, list drop n)，spiltAt会避免list的两次遍历，结果是(list take n, list drop n)，并不代表实现也是这么实现的。
- 前缀和后缀：
- 元素选择：
apply和indices
apply支持从对列表的随机访问，相对于数组而言在列表中直接使用下标并不是很常见。a apply b可以简写为a(b)，编译器会进行展开。list(n)的耗时跟下标n成正比。
indices方法返回指令列表所有有效下标的组合。
- 元素选择：
- 扁平化列表：
flatten
接收一个列表的列表并将扁平化，返回单个列表。flatten函数只能扁平化一层的嵌套。只能应用与所有元素都是列表的列表，否则会抛出异常。
- 扁平化列表：
- 对列表使用
zip和unzip
zip入参为两个列表，返回一个元素是对偶类型的列表。如果两个列表长度不同，则丢弃没有匹配上的元素，zipWithIndex，可以将元素和下标zip起来，是常见的应用。元组的列表也可以只用unzip来转换成为列表元组。unzip和zip应用的都是对偶，三个元素组成的元组是无法应用的。
- 对列表使用
- 显示列表：
toString和mkString，addString
toString返回列表的标准字符串表现形式：List(a, b, c, d, e)。
如需要不同的表现形式，则需要使用mkString，入参有三个，pre，seperator，post。有重载的版本，xs.mkstring表示元素之间的分隔符为空格，入参有一个的版本表示pre和post都是空字符串。
mkString还有一个变种，就是addString，addString接受一个StingBuilder，将生成的字符串添加到StringBuilder上而不是直接返回。addString和mkString这两个方法继承自List的超特质Traversable，所以可以用在所有其他集合类型上。
- 显示列表：
- 转换列表：
iterator, toArray, copyToArray
toArray可以转换一个List到Array；
toList可以转换一个Array到List；
copyToArray有两个入参，其中一个是目标array，目标array必须足够大，能够容纳整个列表。可以通过iterator来使用迭代器访问列表中的元素。
msort[T](less: (T, T) => Boolean)(xs: List[T])使用currying可以进行函数的定制方便用户使用，例如intSort = msort((x:Int, y:Int) => x < y) _是部分应用函数，缺少一个参数，使用intSort(List(1, 3, 4))就可以进行排序。同样的可以定制intReverseSort = msort((x:Int, y:Int) => x > y) _
- 转换列表：
List类的高阶方法
许多对列表的操作都有相似的结构，有一些模式反复出现。入参中有函数的方法就是高阶方法。
- 对列表做映射：
map, flatMap, foreach
map操作接收T=>U函数，生成List[U]。
flatMap操作接收T=>List[U]，将所有的结果拼起来生成List[U]。
foreach的函数类型为T=>Unit，并没有列表类型的结果被组装出来，赋值运算的结果类型为Unit，值为()。
- 对列表做映射：
- 过滤列表：
filter, partition, find, takeWhile, dropWhile, span
filter接收一个判断函数，T => Boolean，列表元素的类型为T
partition类似filter，接收一个判断函数，T => Boolean，生成的是一对列表元组，元组中的第一个列表包含了所有前提条件为true的元素，第二个列表包含了所有前提条件为false的元素。
find方法和``filter类似，返回满足给定条件的第一个元素，而不是所有元素，接收一个判断函数，返回的是Option类型的值。
takeWhile和dropWhile接收一个判断函数为前提条件，takeWhile返回列表中满足条件的最长前缀，dropWhile去除列表中满足条件的最长前缀。
span方法生成列表元组：(list takeWhile p，list dropWhile p)，类似于splitAt，span不会重复遍历列表。
- 过滤列表：
- 对列表的前提条件检查：
forAll和exists
返回的都是布尔值
- 对列表的前提条件检查：
- 折叠列表：
/:和:\
/:为是左折叠，和foldLeft是一样的，(num /: xs)(_ + _)
可以使用(word.head /: word.tail)(_ + " " + _)去除最前面word之前多余的空格。
:\为右折叠，和foldRight是一样的，(xs :\ num)(_ + _)
对于结合性的操作，右折叠和左折叠是等效的，对于不同的操作可能存在执行效率上的差异。
- 折叠列表：
- 列表排序：
sortWith
接收一个比较函数compare，对列表进行排序，表达式x compare y在x出现在y之前应返回true
- 列表排序：
List伴生对象的方法
之前的都是List类的方法，List伴生对象中的方法是可以在全局访问的。
- 从元素创建列表：
List.apply
当伴生对象存在apply函数时，可使用()来代替apply。也就是说List(1,2,3)和List.apply(1,2,3)是相同的效果。
- 从元素创建列表：
- 创建数值区间：
List.range
List.range(from, until, step:option)，until不是列表的一部分。
- 创建数值区间：
- 创建相同元素的列表：
List.fill
fill方法创建包含0个或者多个同一个元素拷贝的列表，第一个参数列表确定列表的维度以及每一维度的长度；第二个参数列表是需要拷贝的元素
- 创建相同元素的列表：
- 表格化一个函数：
List.tabulate
相同与fill方法，但是列表中的值是通过给定函数计算出来的，计算与维度长度有关
- 表格化一个函数：
- 拼接多个列表：
List.concat
将多个列表的元素拼接起来
- 拼接多个列表：
同时处理多个列表
元组的zipped方法将若干通用的操作一般化了，不再只是针对单个列表而是能够同时处理多个列表。zip会将所有有值的元素zip起来，多余的元素会被丢弃。
Scala类型推断算法
-
Scala的类型推断是基于程序流的，局部的，对于方法调用m(args)，如果知道m的类型，可以将该类型运用到之后的运算中。Scala类型推断算法会考虑第一个参数列表里的所有入参类型，但在currying的函数中，后面的参数列表并不会用于类型推断。 - 所以如果入参中有非函数入参和函数入参，将函数入参单独放在最后一个列表中，这样方法的正确实例类型可以从非函数入参推断出来，而这个类型又能被继续用于对函数入参做类型检查。
