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
|
implement Lists;
include "lists.m";
# these will be more useful when p is a closure
allsat[T](p: ref fn(x: T): int, l: list of T): int
{
for(; l != nil; l = tl l)
if(!p(hd l))
return 0;
return 1;
}
anysat[T](p: ref fn(x: T): int, l: list of T): int
{
for(; l != nil; l = tl l)
if(p(hd l))
return 1;
return 0;
}
map[T](f: ref fn(x: T): T, l: list of T): list of T
{
if(l == nil)
return nil;
return f(hd l) :: map(f, tl l);
}
filter[T](p: ref fn(x: T): int, l: list of T): list of T
{
if(l == nil)
return nil;
if(p(hd l))
return hd l :: filter(p, tl l);
return filter(p, tl l);
}
partition[T](p: ref fn(x: T): int, l: list of T): (list of T, list of T)
{
l1: list of T;
l2: list of T;
for(; l != nil; l = tl l)
if(p(hd l))
l1 = hd l :: l1;
else
l2 = hd l :: l2;
return (reverse(l1), reverse(l2));
}
append[T](l: list of T, x: T): list of T
{
# could use the reversing loops instead if this is ever a bottleneck
if(l == nil)
return x :: nil;
return hd l :: append(tl l, x);
}
concat[T](l: list of T, l2: list of T): list of T
{
if(l2 == nil)
return l;
for(rl1 := reverse(l); rl1 != nil; rl1 = tl rl1)
l2 = hd rl1 :: l2;
return l2;
}
combine[T](l: list of T, l2: list of T): list of T
{
for(; l != nil; l = tl l)
l2 = hd l :: l2;
return l2;
}
reverse[T](l: list of T): list of T
{
rl: list of T;
for(; l != nil; l = tl l)
rl = hd l :: rl;
return rl;
}
last[T](l: list of T): T
{
# l must not be nil
while(tl l != nil)
l = tl l;
return hd l;
}
# delete the first instance of x in l
delete[T](x: T, l: list of T): list of T
for { T => eq: fn(a, b: T): int; }
{
o: list of T;
for(; l != nil; l = tl l)
if(T.eq(x, hd l)){
l = tl l;
for(; o != nil; o = tl o)
l = hd o :: l;
break;
}
return l;
}
pair[T1, T2](l1: list of T1, l2: list of T2): list of (T1, T2)
{
if(l1 == nil && l2 == nil)
return nil;
return (hd l1, hd l2) :: pair(tl l1, tl l2);
}
unpair[T1, T2](l: list of (T1, T2)): (list of T1, list of T2)
{
l1: list of T1;
l2: list of T2;
for(; l != nil; l = tl l){
(v1, v2) := hd l;
l1 = v1 :: l1;
l2 = v2 :: l2;
}
return (reverse(l1), reverse(l2));
}
ismember[T](x: T, l: list of T): int
for { T => eq: fn(a, b: T): int; }
{
for(; l != nil; l = tl l)
if(T.eq(x, hd l))
return 1;
return 0;
}
|
