xref: /inferno-os/appl/lib/lists.b (revision 1aff7a0a7dab24c5871eb95737c86616c9fd848b) 
1implement Lists;
2
3include "lists.m";
4
5# these will be more useful when p is a closure
6allsat[T](p: ref fn(x: T): int, l: list of T): int
7{
8	for(; l != nil; l = tl l)
9		if(!p(hd l))
10			return 0;
11	return 1;
12}
13
14anysat[T](p: ref fn(x: T): int, l: list of T): int
15{
16	for(; l != nil; l = tl l)
17		if(p(hd l))
18			return 1;
19	return 0;
20}
21
22map[T](f: ref fn(x: T): T, l: list of T): list of T
23{
24	if(l == nil)
25		return nil;
26	return f(hd l) :: map(f, tl l);
27}
28
29filter[T](p: ref fn(x: T): int, l: list of T): list of T
30{
31	if(l == nil)
32		return nil;
33	if(p(hd l))
34		return hd l :: filter(p, tl l);
35	return filter(p, tl l);
36}
37
38partition[T](p: ref fn(x: T): int, l: list of T): (list of T, list of T)
39{
40	l1: list of T;
41	l2: list of T;
42	for(; l != nil; l = tl l)
43		if(p(hd l))
44			l1 = hd l :: l1;
45		else
46			l2 = hd l :: l2;
47	return (reverse(l1), reverse(l2));
48}
49
50append[T](l: list of T, x: T): list of T
51{
52	# could use the reversing loops instead if this is ever a bottleneck
53	if(l == nil)
54		return x :: nil;
55	return hd l :: append(tl l, x);
56}
57
58concat[T](l: list of T, l2: list of T): list of T
59{
60	if(l2 == nil)
61		return l;
62	for(rl1 := reverse(l); rl1 != nil; rl1 = tl rl1)
63		l2 = hd rl1 :: l2;
64	return l2;
65}
66
67combine[T](l: list of T, l2: list of T): list of T
68{
69	for(; l != nil; l = tl l)
70		l2 = hd l :: l2;
71	return l2;
72}
73
74reverse[T](l: list of T): list of T
75{
76	rl: list of T;
77	for(; l != nil; l = tl l)
78		rl = hd l :: rl;
79	return rl;
80}
81
82last[T](l: list of T): T
83{
84	# l must not be nil
85	while(tl l != nil)
86		l = tl l;
87	return hd l;
88}
89
90# find instance of x in l, return tail of l from x
91find[T](x: T, l: list of T): list of T
92	for { T =>	eq:	fn(a, b: T): int; }
93{
94	for(; l != nil; l = tl l)
95		if(T.eq(x, hd l))
96			return l;
97	return nil;
98}
99
100# delete the first instance of x in l
101delete[T](x: T, l: list of T): list of T
102	for { T =>	eq:	fn(a, b: T): int; }
103{
104	loc := find(x, l);
105	if(loc == nil)
106		return l;
107	o: list of T;
108	for(; l != loc; l = tl l)
109		o = hd l :: o;
110	l = tl loc;
111	for(; o != nil; o = tl o)
112		l = hd o :: l;
113	return l;
114}
115
116pair[T1, T2](l1: list of T1, l2: list of T2): list of (T1, T2)
117{
118	if(l1 == nil && l2 == nil)
119		return nil;
120	return (hd l1, hd l2) :: pair(tl l1, tl l2);
121}
122
123unpair[T1, T2](l: list of (T1, T2)): (list of T1, list of T2)
124{
125	l1: list of T1;
126	l2: list of T2;
127	for(; l != nil; l = tl l){
128		(v1, v2) := hd l;
129		l1 = v1 :: l1;
130		l2 = v2 :: l2;
131	}
132	return (reverse(l1), reverse(l2));
133}
134
135ismember[T](x: T, l: list of T): int
136	for { T =>	eq:	fn(a, b: T): int; }
137{
138	for(; l != nil; l = tl l)
139		if(T.eq(x, hd l))
140			return 1;
141	return 0;
142}
143