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
194
195
196
197
198
199
200
201
202
203
204
|
.TH LISTS 2
.SH NAME
lists: allsat, anysat, append, combine, concat, delete, filter, find, ismember, last, map, pair, partition, reverse, unpair\- list operations
.SH SYNOPSIS
.EX
include "lists.m"
lists := load Lists Lists->PATH;
append: fn[T](l: list of T, x: T): list of T;
combine: fn[T](l1: list of T, l2: list of T): list of T;
concat: fn[T](l1: list of T, l2: list of T): list of T;
delete: fn[T](x: T, l: list of T): list of T
for { T => eq: fn(a, b: T): int; };
find: fn[T](x: T, l: list of T): list of T
for { T => eq: fn(a, b: T): int; };
ismember: fn[T](x: T, l: list of T): int
for { T => eq: fn(a, b: T): int; };
last: fn[T](l: list of T): T;
pair: fn[T1, T2](l1: list of T1, l2: list of T2):
list of (T1, T2);
reverse: fn[T](l: list of T): list of T;
unpair: fn[T1, T2](l: list of (T1, T2)):
(list of T1, list of T2);
allsat: fn[T](p: ref fn(x: T): int, l: list of T): int;
anysat: fn[T](p: ref fn(x: T): int, l: list of T): int;
filter: fn[T](p: ref fn(x: T): int, l: list of T): list of T;
map: fn[T](f: ref fn(x: T): T, l: list of T): list of T;
partition: fn[T](p: ref fn(x: T): int, l: list of T):
(list of T, list of T);
.EE
.SH DESCRIPTION
The module provides operations on lists of type
.IR T ,
which may be any reference type, or
.BR string .
Reference types are
.BR array ,
.BR chan ,
.BR list ,
.BR module ,
and
.BI ref " adt".
None of the operations change their parameter lists: they always return a new list.
.PP
First, there is a group of common list operations.
.PP
.B Append
returns a new list with the elements of
.I l
followed by the element
.IR x .
.PP
.B Combine
returns a new list that has the elements of both
.I l1
and
.I l2
in no defined order.
.PP
.B Concat
returns a new list that has the elements of
.I l1
followed by the elements of
.IR l2 .
.PP
.B Delete
returns a new list in which the first element of
.I l
that is equal to
.I x
has been removed (all others remain).
.I X
must be an adt reference type
.I T
with an operation
.IB T .eq
that returns true (non-zero) if two values of type
.I T
are considered equal.
.PP
.B Find
finds the first instance of
.I x
in list
.I l
and returns the tail of
.I l
with
.I x
at its head.
.B Find
returns nil if there is no
instance of
.I x
in
.IR l .
.PP
.B Ismember
returns 1 if
there is an element of
.I l
that is equal to
.IR x .
.PP
.B Last
returns the value of the element at the end of list
.IR l .
A run-time error occurs if
.I l
is nil.
.PP
.B Pair
takes two lists
.I l1
and
.IR l2 ,
and returns a new list of tuples
.BI ( v1,\ v2 )
in which each element of
.I l1
has been paired with the corresponding element of
.IR l2 .
A run-time error occurs if the lists are not equal in length.
.PP
.B Reverse
returns a new list containing the elements of
.I l
in reverse order.
.PP
.B Unpair
takes a list of tuples
.BI ( v1,\ v2 )
and returns a tuple of lists
.BI ( l1,\ l2 )
where
.I l1
contains the first element of each tuple, and
.I l2
contains the second element of each tuple.
.PP
A second group of operations applies a function
.I f
or a Boolean predicate
.I p
to each element of a list
.IR l ,
returning a transformed list or a Boolean value.
A predicate
.I p
must return non-zero if its parameter value satisfies its condition, and must return zero if it does not.
.PP
.B Allsat
returns 1 if all elements of
.I l
satisfy
.IR p ,
and returns 0 otherwise.
.PP
.B Anysat
returns 1 if any element of
.I l
satisfies
.IR p ,
and returns 0 otherwise.
.PP
.B Filter
returns a new list containing only the elements of
.I l
that satisfy
.IR p .
.PP
.B Map
returns a new list in which each element of
.I l
has been transformed by
.I f
(ie, if
.I l
is
.IB e0 :: e1 :: ...
then the result is
.IB f(e0) :: f(e1) :: ... ).
.PP
.B Partition
returns a tuple of lists
.BI ( l1,\ l2 )
of lists where
.I l1
contains all elements of
.I l
that satisfy
.I p
and
.I l2
contains all elements of
.I l
that do not satisfy
.IR p .
.SH SOURCE
.B /appl/lib/lists.b
.SH BUGS
The current implementation of polymorphism is limited to reference types and strings,
which in turn limits use of this module.
|
