首页 > 代码库 > Scala 的list
Scala 的list
9.1 使用列表
列表类型:跟数组一样,列表也是同质化的(homogeneous)。即所有元素都要是同种类型。
列表结构:所有列表由两部分组成:Nil 和 ::(cons)。
基本操作:主要有三个:head , tail , isEmpty 。这些都定义在List Object里。head 和 tail只能用在非空列表里。可以用“插入排序”的例子来进行说明。
模式匹配:::在Scala标准库里是一个case class 。所以可以使用用模式匹配
9.2 List类的定义
List是一个抽象类。List里定义了很多方法,解释如下:
分解列表。
啮合(zipping lists):把两个List结合成一个列表对,如,有列表:xs = List(X1 , ... Xn) 和 ys = List(y1 , ... , yn) , xs zip ys,则生成List对:List((X1 , Y1), ... (Xn , Yn))
操作列表:跟其他中缀操作符一样,::实现为一个对象的方法。Scala里以“:”结尾的操作符都被当成右操作符,也就是从右往左运算。
连接列表:“:::”操作符可以用来连接两个列表。
反转列表:另一个有用的操作就是反转(reversal)。给出了一种reverse方法的实现,但是这种方法跟List的长度成正比,不是很有效。之后会给出一种只有线性关系的实现。
def reverse[A](xs : List[A]) : List[A] = xs match{ case Nil => Nil case x :: xs => reverse(xs) ::: List(x)}
9.3 例子:归并排序(merge sort)
之前的插入排序(insertion sort)虽然简单,但不是很有效。平均复杂度与输入列表的长度的平方成正比。一个比插入排序更好的算法是“归并排序”。工作原理如下:
一,如果这个List有0个或者1个元素,那么它是已经排好的,可以直接返回这个列表。稍长的列表可以分成两部分,每部分包含大概原List一半的长度内容。每个子列表被一个递归的排序调用进行排序,然后两个排序好的列表被一个合并操作合并在一起。
对于一个归并排序的实现,我们仍然要指定元素类型,同时也要有用来做比较(comparison)的函数,用来确定排序规则。一个实现如下:
def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = { def merge(xs1: List[A], xs2: List[A]): List[A] = if (xs1.isEmpty) xs2 else if (xs2.isEmpty) xs1 else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2) else xs2.head :: merge(xs1, xs2.tail) val n = xs.length / 2 if (n == 0) xs else merge(msort(less)(xs.take(n)), msort(less)(xs.drop(n))) }
msort的定义用到了柯里化,所以可以这样使用:
val intSort = msort((x : Int , y : Int) => x < y)val reverseSort = msort((x : Int , y : Int) => x > y
val
list
=
List(
1
to
20
by
2
:_
*)
val
list
1
=
list++List(
21
,
22
)
println(
"list1="
+list
1
)
val
list
2
=
22
+
:
21
+
:
list
println(
"list2="
+list
2
)
val
list
3
=
list--List(
19
,
20
)
println(
"list3="
+list
3
)
val
list
4
=
list-
19
-
20
println(
"list4="
+list
4
)
val
list
5
=
list
:::
List(
21
,
22
)
println(
"list5="
+list
5
)
val
list
6
=
22
::
21
::
list
println(
"list6="
+list
6
)
val
list
7
=
list.break(
_
>
10
)
println(
"list7="
+list
7
)
val
list
8
=
list.companion(
4
,
5
)
println(
"list8="
+list
8
)
val
list
9
=
list.drop(
5
)
println(
"list9="
+list
9
)
val
list
10
=
list.dropWhile(
_
<
10
)
println(
"list10="
+list
10
)
val
list
11
=
List(
"a"
,
"b"
).mapConserve(
_
.toUpperCase())
println(
"list11="
+list
11
)
val
list
12
=
list.remove(
_%
5
==
0
)
println(
"list12="
+list
12
)
val
list
13
=
(
15
::
list).removeDuplicates
println(
"list13="
+list
13
)
val
list
14
=
list.reverse
println(
"list14="
+list
14
)
val
list
15
=
list.slice(
2
,
6
)
println(
"list15="
+list
15
)
list
1
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
,
21
,
22
)
list
2
=
List(
22
,
21
,
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
)
list
3
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
)
list
4
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
)
list
5
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
,
21
,
22
)
list
6
=
List(
22
,
21
,
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
)
list
7
=
(List(
1
,
3
,
5
,
7
,
9
),List(
11
,
13
,
15
,
17
,
19
))
list
8
=
List(
4
,
5
)
list
9
=
List(
11
,
13
,
15
,
17
,
19
)
list
10
=
List(
11
,
13
,
15
,
17
,
19
)
list
11
=
List(A, B)
list
12
=
List(
1
,
3
,
7
,
9
,
11
,
13
,
17
,
19
)
list
13
=
List(
15
,
1
,
3
,
5
,
7
,
9
,
11
,
13
,
17
,
19
)
list
14
=
List(
19
,
17
,
15
,
13
,
11
,
9
,
7
,
5
,
3
,
1
)
list
15
=
List(
5
,
7
,
9
,
11
)
val
list
16
=
list.sort((x,y)
=
>x>y)
println(
"list16="
+list
16
)
val
list
17
=
list.span(
_
<
10
)
println(
"list17="
+list
17
)
val
list
18
=
list.splitAt(
8
)
println(
"list18="
+list
18
)
val
list
19
=
list.stringPrefix
println(
"list19="
+list
19
)
val
list
20
=
list.take(
5
)
println(
"list20="
+list
20
)
val
list
21
=
list.takeRight(
5
)
println(
"list21="
+list
21
)
val
list
22
=
list.takeWhile(
_
<
15
)
println(
"list22="
+list
22
)
val
list
23
=
list.toList
println(
"list23="
+list
23
)
val
list
24
=
list.toStream
println(
"list24="
+list
24
)
val
list
25
=
list++
:
List(
21
,
22
)
println(
"list25="
+list
25
)
val
list
26
=
list./
:
(
0
)((x,y)
=
>x+y)
println(
"list26="
+list
26
)
val
list
27
=
list./
:
\(
0
)((x,y)
=
>x+y)
println(
"list27="
+list
27
)
val
list
28
=
list.
:
\(
0
)((x,y)
=
>x+y)
println(
"list28="
+list
28
)
val
list
29
=
list.
:
\(
0
)((x,y)
=
>x+y)
println(
"list29="
+list
29
)
val
list
30
=
list
:
+
20
:
+
21
println(
"list30="
+list
30
)
list
16
=
List(
19
,
17
,
15
,
13
,
11
,
9
,
7
,
5
,
3
,
1
)
list
17
=
(List(
1
,
3
,
5
,
7
,
9
),List(
11
,
13
,
15
,
17
,
19
))
list
18
=
(List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
),List(
17
,
19
))
list
19
=
List
list
20
=
List(
1
,
3
,
5
,
7
,
9
)
list
21
=
List(
11
,
13
,
15
,
17
,
19
)
list
22
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
)
list
23
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
)
list
24
=
Stream(
1
, ?)
list
25
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
,
21
,
22
)
list
26
=
100
list
27
=
100
list
28
=
100
list
29
=
100
list
30
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
,
20
,
21
)
val
list
31
=
list.addString(
new
StringBuilder(
"a"
))
println(
"list31="
+list
31
)
val
list
32
=
list.apply(
5
)
println(
"list32="
+list
32
)
val
list
33
=
list.canEqual(
""
)
println(
"list33="
+list
33
)
val
list
34
=
list.collect{
case
i
:
Int
=
> i+
"b"
}
println(
"list34="
+list
34
)
val
list
35
=
list.andThen(
_
<
10
).isDefinedAt(
10
)
println(
"list35="
+list
35
)
val
list
36
=
list.collectFirst{
case
i
:
Int
=
> i+
"b"
}
println(
"list36="
+list
36
)
val
list
37
=
list.take(
3
).combinations(
2
).toList
println(
"list37="
+list
37
)
val
list
38
=
list.compose(list.reverse)
println(
"list38="
+list
38
)
val
list
39
=
list.contains(
9
)
println(
"list39="
+list
39
)
val
list
40
=
list.containsSlice(List(
1
,
3
))
println(
"list40="
+list
40
)
val
array
=
new
Array[Int](
10
)
list.copyToArray(array)
println(
"array="
+array.mkString(
","
))
list.copyToArray(array,
5
)
println(
"array="
+array.mkString(
","
))
list.copyToArray(array,
1
,
3
)
println(
"array="
+array.mkString(
","
))
val
buff
=
new
ListBuffer[Int]();
list.copyToBuffer(buff)
println(
"buff="
+buff)
val
list
41
=
list.corresponds(list)(
_
>
=_
)
println(
"list41="
+list
41
)
val
list
42
=
list.count(
_
<
15
)
println(
"list42="
+list
42
)
val
list
43
=
list.diff(List(
1
,
5
,
11
))
println(
"list43="
+list
43
)
val
list
44
=
list.distinct
println(
"list44="
+list
44
)
val
list
45
=
list.dropRight(
3
)
println(
"list45="
+list
45
)
list
31
=
a
135791113151719
list
32
=
11
list
33
=
true
list
34
=
List(
1
b,
3
b,
5
b,
7
b,
9
b,
11
b,
13
b,
15
b,
17
b,
19
b)
list
35
=
false
list
36
=
Some(
1
b)
list
37
=
List(List(
1
,
3
), List(
1
,
5
), List(
3
,
5
))
list
38
=
<function
1
>
list
39
=
true
list
40
=
true
array
=
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
array
=
1
,
3
,
5
,
7
,
9
,
1
,
3
,
5
,
7
,
9
array
=
1
,
1
,
3
,
5
,
9
,
1
,
3
,
5
,
7
,
9
buff
=
ListBuffer(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
)
list
41
=
true
list
42
=
7
list
43
=
List(
3
,
7
,
9
,
13
,
15
,
17
,
19
)
list
44
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
)
list
45
=
List(
1
,
3
,
5
,
7
,
9
,
11
,
13
)
Scala 的list