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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
(*
Title: Standard Basis Library: List Structure
Author: David Matthews
Copyright David Matthews 1999, 2005
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*)
(* G&R 2004 status: Updated. *)
signature LIST =
sig
datatype list = datatype list
(* G&R include the definition of list below in their "Interface". This is illegal. *)
(*datatype 'a list = nil | :: of 'a * 'a list *)
exception Empty
val null : 'a list -> bool
val length : 'a list -> int
val @ : ('a list * 'a list) -> 'a list
val concat : 'a list list -> 'a list
val revAppend : ('a list * 'a list) -> 'a list
val tabulate : (int * (int -> 'a)) -> 'a list
val hd : 'a list -> 'a
val tl : 'a list -> 'a list
val last : 'a list -> 'a
val getItem : 'a list -> ('a * 'a list) option
val nth : ('a list * int) -> 'a
val take : ('a list * int) -> 'a list
val drop : ('a list * int) -> 'a list
val rev : 'a list -> 'a list
val app : ('a -> unit) -> 'a list -> unit
val map : ('a -> 'b) -> 'a list -> 'b list
val mapPartial : ('a -> 'b option) -> 'a list -> 'b list
val find : ('a -> bool) -> 'a list -> 'a option
val filter : ('a -> bool) -> 'a list -> 'a list
val partition : ('a -> bool) -> 'a list -> ('a list * 'a list)
val foldl : (('a * 'b) -> 'b) -> 'b -> 'a list -> 'b
val foldr : (('a * 'b) -> 'b) -> 'b -> 'a list -> 'b
val exists : ('a -> bool) -> 'a list -> bool
val all : ('a -> bool) -> 'a list -> bool
val collate: ('a * 'a -> order) -> 'a list * 'a list -> order
end;
structure List: LIST =
struct
datatype list = datatype list
exception Empty
fun null [] = true | null (_::_) = false
val length = length (* Declared in prelude. *)
(* ...
fun nil @ M = M (* append *)
| (x::L) @ M = x :: (L @ M);
... *)
(* Dave's improved(?) version SPF 10/2/94 *)
(* Taken from the prelude. The idea is to avoid rebuilding the
list if the second list is empty. *)
fun x @ nil = x (* append *)
| x @ y =
let
fun app nil = y
| app (a :: b) = a :: app b
in
app x
end;
fun hd (a::_) = a | hd _ = raise Empty
and tl (_::a) = a | tl _ = raise Empty
(* TODO: We could avoid the test for nil in the recursive cases. *)
fun last [] = raise Empty
| last [a] = a
| last (_::b) = last b
fun getItem [] = NONE
| getItem (a::b) = SOME(a, b)
(* We could raise subscript immediately if i < 0 and we probably
would have to if we were using fixed precision arithmetic. *)
fun nth([], _) = raise General.Subscript
| nth(a::_, 0) = a
| nth(_::l, i) = nth(l, i-1)
(* TODO: Many of these functions involve recursing down the list and
so require stack space proportional to the length of the list.
Would it be more efficient to build the lists in reverse and then
reverse the result? That would save on stack space at the expense
of constructing the list twice. *)
fun take(_, 0) = []
| take([], _) = raise General.Subscript
| take(a::b, i) = a :: take(b, i-1)
fun drop(l, 0) = l
| drop([], _) = raise General.Subscript
| drop(_::l, i) = drop(l, i-1)
fun revAppend([], a) = a
| revAppend(x::y, a) = revAppend(y, x::a)
fun rev l = revAppend(l, [])
fun concat [] = []
| concat (a::b) = a @ concat b
fun app f [] = ()
| app f (h::t) = (f h; app f t)
fun map f [] = []
| map f (a::b) = f a :: map f b;
fun mapPartial f [] = []
| mapPartial f (a::b) =
case f a of
SOME r => r :: mapPartial f b
| NONE => mapPartial f b
fun find f [] = NONE
| find f (a::b) = if f a then SOME a else find f b
fun filter f [] = []
| filter f (a::b) = if f a then a :: filter f b else filter f b
(* This is defined to evaluate f from left to right. *)
(* TODO: This involves returning a pair and creating new pairs
which allocates storage in Poly/ML. Is there a more efficient
implementation? e.g. recurse down the list and then reverse it. *)
fun partition f [] = ([], [])
| partition f (a::b) =
let
val test = f a
and (x, y) = partition f b
in
if test then (a::x, y) else (x, a::y)
end
fun foldl f b [] = b
| foldl f b (x::y) = foldl f (f(x, b)) y
fun foldr f b [] = b
| foldr f b (x::y) = f(x, foldr f b y)
fun exists f [] = false
| exists f (a::b) = if f a then true else exists f b
fun all f [] = true
| all f (a::b) = if f a then all f b else false
(* tabulate a function. Rewritten again this time using an array. *)
fun tabulate(n, f) =
let
val a = Array.tabulate(n, f)
in
Array.foldr (op ::) [] a
end
(* Lexicographic comparison. *)
fun collate cmp ([], []) = General.EQUAL
| collate cmp ([], _) = General.LESS
| collate cmp (_, []) = General.GREATER
| collate cmp (a::b, c::d) =
(case cmp (a, c) of General.EQUAL => collate cmp (b, d) | notEqual => notEqual)
end;
(* Values available at the top level. *)
exception Empty = List.Empty
val null : 'a list -> bool = List.null
val hd : 'a list -> 'a = List.hd
val tl : 'a list -> 'a list = List.tl
val length : 'a list -> int = List.length
val rev : 'a list -> 'a list = List.rev
val op @ : ('a list * 'a list) -> 'a list = List.@
val app : ('a -> unit) -> 'a list -> unit = List.app
val map : ('a -> 'b) -> 'a list -> 'b list = List.map
val foldr: ('a*'b->'b)-> 'b -> 'a list -> 'b = List.foldr
val foldl: ('a*'b->'b)-> 'b -> 'a list -> 'b = List.foldl;
|
