1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
abstract final class List[a] with {
def ::(x: a): List[a] = cons(x, this);
def head: a = match {
case [] => error("[].head");
case x :: xs => x
}
def tail: List[a] = match {
case [] => error("[].tail");
case x :: xs => xs
}
def isEmpty = match {
case [] => False;
case _ :: _ => True;
}
def length: Int = match {
case [] => 0;
case x :: xs => 1 + xs.length;
}
def ::: (that: List[a]): List[a] = match {
case [] => that;
case x :: xs => x :: xs ::: that
}
def append(x: a): List[a] = this ::: x :: [];
def map[b](f: (a)b): List[b] = match {
case [] => [];
case x :: xs => f(x) :: (xs map f)
}
def flatMap[b](f: (a)List[b]): List[b] = match {
case [] => [];
case x :: xs => f(x) ::: (xs flatMap f)
}
def filter(p: (a)Boolean): List[a] = match {
case [] => [];
case x :: xs => if (p(x)) x :: (xs filter p) else xs filter p
}
def foldl[b](f: (b, a)b)(z: b): b = match {
case [] => z;
case x :: xs => (xs foldl f)(f(z, head))
}
def foldr[b](f: (a, b)b)(z: b): b = match {
case [] => z;
case x :: xs => f(x, (xs foldr f)(z))
}
def foldl1(f: (a, a)a): a = match {
case [] => error("[].foldl1");
case x :: xs => (xs foldl f)(x)
}
def foldr1(f: (a, a)a): a = match {
case [] => error("[].foldr1");
case x :: [] => x;
case x :: xs => f(x, (xs foldr1 f))
}
def forall(p: (a)Boolean): Boolean = match {
case [] => True;
case x :: xs => p(x) && (xs forall p)
}
def exists(p: (a)Boolean): Boolean = match {
case [] => False;
case x :: xs => p(x) || (xs exists p)
}
def take(n: Int): List[a] = match {
case [] => [];
case x :: xs => if (n == 0) [] else x :: (xs take (n - 1))
}
def drop(n: Int): List[a] = match {
case [] => [];
case x :: xs => if (n == 0) this else xs drop (n - 1)
}
def takeWhile(p: (a)Boolean): List[a] = match {
case [] => [];
case x :: xs => if (p(x)) x :: (xs takeWhile p) else []
}
def dropWhile(p: (a)Boolean): List[a] = match {
case [] => [];
case x :: xs => if (p(x)) (xs dropWhile p) else this
}
def init: List[a] = match {
case [] => error("[].init");
case x :: [] => [];
case x :: xs => xs.init
}
def last: a = match {
case [] => error("[].last");
case x :: [] => x;
case x :: xs => xs.last
}
def reverse: List[a] = {
def snoc(xs: List[a], x: a) = x :: xs;
foldl(snoc)([])
}
def zip[b](that: List[b]): List[(a,b)] = (this, that) match {
case (x :: xs, y :: ys) => (x, y) :: (xs zip ys)
case _ => []
}
override def toString(): String = "[" + mkString(",") + "]";
def mkString(sep: String): String = match {
case [] => "";
case x :: [] => x.toString();
case x :: xs => x.toString() + sep + xs.toString()
}
}
def error[a](x: String):a = (new java.lang.RuntimeException(x)).throw;
case class Nil[b] extends List[b];
case class ::_class[b](x: b)(xs: List[b]) extends List[b];
def cons[a](x: a, xs: List[a]) = ::_class(x)(xs);
def nil[a] = new Nil[a];
|
