UtilStrictLists.icl 5.17 KB
Newer Older
Diederik van Arkel's avatar
Diederik van Arkel committed
1
2
3
4
5
6
implementation module UtilStrictLists

import StdArray, StdBool, StdClass, StdInt, StdList, StdMisc, StdOrdList, StdString

//	A strict list data structure

7
::	List t	=	(:!) infixr 0 !t !(List t)
Diederik van Arkel's avatar
Diederik van Arkel committed
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
			|	Nil
			
instance toString (List a) | toString a
where
	toString Nil	= "[]"
	toString (h:!t)	= "[" +++ toString h +++ toS t +++ "]"
	where
		toS Nil = ""
		toS (h:!t) = "," +++ toString h +++ toS t

// General operations on lists

Singleton :: !(List t) -> t;
Singleton (x:!Nil) =  x;
	
IsEmptyList	:: !(List t) -> Bool;
IsEmptyList Nil =  True;
IsEmptyList xs 	=  False;
	
Head :: !(List t) -> t;
Head (h:!t)	= h;
Head list	= abort "Head: Empty list";
	
31
Concat	:: !(List .t) !u:(List .t) -> u:List .t;
Diederik van Arkel's avatar
Diederik van Arkel committed
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
Concat (x:!xs)	ys
	#! xs = Concat xs ys;
	= 	x :! xs;
//	= 	x :! Concat xs ys;
Concat Nil		ys	= 	ys;
	
Reverse	:: !(List t) -> List t;
Reverse l =  Reverse2 l Nil;
	
Reverse2 :: !(List .a) !u:(List .a) -> v:List .a, [u <= v];
Reverse2 Nil	rev =  rev;
Reverse2 (f:!r)	rev	=  Reverse2 r (f:!rev);
	
LLength	:: !(List t) -> Int;
LLength l =  Length2 0 l;
	
Length2	:: !Int !(List t) -> Int;
Length2 n Nil	=  n;
Length2 n (f:!r) =  Length2 (inc n) r;
		
52
Filter :: !(s -> Bool) !(List s) -> List s;
Diederik van Arkel's avatar
Diederik van Arkel committed
53
54
55
56
57
58
59
60
Filter _ Nil
	=	Nil;
Filter p (h :! t)
	| p h
		=	h :! Filter p t;
	// otherwise
		=	Filter p t;

61
FilterR :: !(s -> Bool) !(List s) -> List s;
Diederik van Arkel's avatar
Diederik van Arkel committed
62
63
FilterR p list = FilterR2 p list Nil;

64
FilterR2 :: !(s -> Bool) !(List s) !(List s) -> List s;
Diederik van Arkel's avatar
Diederik van Arkel committed
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
FilterR2 p Nil		acc			= acc;
FilterR2 p (x:!xs)	acc | p x	= FilterR2 p xs (x:!acc);
								= FilterR2 p xs acc;
	
Append :: !(List t) !t -> List t;
Append Nil		x =  x:!Nil;
Append (f:!r)	x =  f :! Append r x;

Select :: !(List t) !Int -> t;
Select (f:!r) 0 = f;
Select (f:!r) i = Select r (dec i);
Select list  i = abort "Select: index out of range";

Update2	:: !(List (List t)) !Int !Int !t -> List (List t);
Update2 (f:!r) 0 j x = Update_new f j x :! r;
Update2 (f:!r) i j x = f :! Update2 r (dec i) j x;
Update2 list  i j x = abort "Update2: index out of range";
	
Update_new :: !(List t) !Int !t -> List t;
Update_new (f:!r) 0 x = x :! r;
Update_new (f:!r) i x = f :! Update_new r (dec i) x;
Update_new list  i x =  abort "Update: index out of range";
 							
AppendLists :: !(List .a) !u:(List .a) -> v:List .a, [u <= v];
AppendLists Nil l2 = l2; 
AppendLists (h:!t) l2 = h :! (AppendLists t l2);

FlattenList :: !(List (List .a)) -> List .a;
FlattenList (h:!t)	= AppendLists h (FlattenList t);
FlattenList Nil		= Nil;

96
P_MapR :: !(s -> (t,Bool)) !(List s) -> (!List t,!Bool)
Diederik van Arkel's avatar
Diederik van Arkel committed
97
98
99
100
101
102
P_MapR f Nil
	=	(Nil, True)
P_MapR f (x:!xs)
	# (fx,b) = f x
	=	P_MapR2 b f xs fx Nil
where
103
	P_MapR2 :: !Bool !(s -> (t,Bool)) !(List s) !t !(List t) -> (!List t,!Bool)
Diederik van Arkel's avatar
Diederik van Arkel committed
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
	P_MapR2 unchanged f Nil		first acc
		= (first:!acc, unchanged)
	P_MapR2 unchanged f (x:!xs)	first acc
		# (fx,b) = f x
		= P_MapR2 (unchanged && b) f xs first (fx:!acc)

//
// Operations on (ordered) lists of strings
//

InsertStringInList :: !String !(List String) -> List String;
InsertStringInList name Nil
	=  name:!Nil;
InsertStringInList name list=:(nm:!rest)
	| nm < name	=	nm :! InsertStringInList name rest;
	| nm == name	=	list;
					=	name :! nm :! rest;

UnionStringList	:: !(List String) !( List String) -> (List String);
UnionStringList	Nil			ys			=  ys;
UnionStringList	xs			Nil			=  xs;
UnionStringList	xl=:(x:!xs)	yl=:(y:!ys)
	| x < y	=	x :! UnionStringList xs yl;
	| x > y	=	y :! UnionStringList xl ys;
			=	x :! UnionStringList xs ys;

StringOccurs :: !String !.(List String) -> Bool;
StringOccurs s Nil 					=  False;
StringOccurs s (x:!xs)	| x == s	=  True;
									=  StringOccurs s xs;
									
//	Sort a list of strings

SortStrings	:: !.(List String) -> .List String;
SortStrings l = ListToStrictList (sort (StrictListToList l))
					
// Compares two sorted lists of strings

EQStrings :: !(List String) !(List String) -> Bool;
EQStrings Nil		Nil						= True;
EQStrings (a:!resta)	(b:!restb)	| a==b	= EQStrings resta restb;
											= False;
EQStrings _			_						= False;

InclString :: !String !(List String) -> List String
InclString new strs | StringOccurs new strs	= strs
											= new:!strs

RemoveDup :: !.(List a) -> .(List a) | Eq a
RemoveDup (x:!xs) = (x:!RemoveDup (Filter ((<>) x) xs))
RemoveDup _      = Nil

RemoveStringFromList :: !String !(List String) -> List String;
RemoveStringFromList name Nil
	=  Nil;
RemoveStringFromList name (nm:!rest)
	| nm==name
		= rest;
		= nm :! RemoveStringFromList name rest;

RemoveMember :: a !u:(List a) -> v:List a | == a, [u <= v];
RemoveMember e (a:!as)
	| a==e		= as
				= (a:!RemoveMember e as)
RemoveMember e Nil = Nil

RemoveMembers :: !u:(List a) !.(List a) -> v:List a | == a, [u <= v];
RemoveMembers x Nil		= x
RemoveMembers x (b:!y)	= RemoveMembers (RemoveMember b x) y

StrictListToList :: !(List .a) -> [.a];
StrictListToList Nil
	=	[];
StrictListToList (h :! t)
	=	[h : StrictListToList t];

ListToStrictList :: ![.a] -> (List .a);
ListToStrictList list
	=	foldr (:!) Nil list; // RWS: wrong line number (change foldr to foldl)

184
Map :: !(s -> t) !(List s) -> List t;
Diederik van Arkel's avatar
Diederik van Arkel committed
185
186
187
Map f (a:!x)	= (f a :! Map f x)
Map f Nil		= Nil

188
MapR :: !(s -> t) !(List s) -> List t;
Diederik van Arkel's avatar
Diederik van Arkel committed
189
190
MapR f list	= MapR2 f list Nil;

191
MapR2 :: (s -> t) !(List s) !(List t) -> List t;
Diederik van Arkel's avatar
Diederik van Arkel committed
192
193
194
MapR2 f Nil		acc	= acc;
MapR2 f (x:!xs)	acc = MapR2 f xs (f x :! acc);