1
/* any l: or all the elements of list l together
3
* any (map (equal 0) list) == true, if any element of list is zero.
4
* any :: [bool] -> bool
6
any = foldr logical_or false;
8
/* all l: and all the elements of list l together
10
* all (map (==0) list) == true, if every element of list is zero.
11
* all :: [bool] -> bool
13
all = foldr logical_and true;
15
/* concat l: join a list of lists together
17
* concat ["abc","def"] == "abcdef".
18
* concat :: [[*]] -> [*]
20
concat l = foldr join [] l;
22
/* delete eq x l: delete the first x from l
24
* delete equal 'b' "abcdb" == "acdb"
25
* delete :: (* -> bool) -> * -> [*] -> [*]
35
/* difference eq a b: delete b from a
37
* difference equal "asdf" "ad" == "sf"
38
* difference :: (* -> bool) -> [*] -> [*] -> [*]
40
difference = foldl @ converse @ delete;
42
/* drop n l: drop the first n elements from list l
44
* drop 3 "abcd" == "d"
45
* drop :: num -> [*] -> [*]
48
= l, n <= 0 || l == []
49
= drop (n - 1) (tl l);
51
/* dropwhile fn l: drop while fn is true
53
* dropwhile is_digit "1234pigs" == "pigs"
54
* dropwhile :: (* -> bool) -> [*] -> [*]
58
= dropwhile fn x, fn a
64
/* extract n l: extract element at index n from list l
66
extract = converse subscript;
68
/* filter fn l: return all elements of l for which predicate fn holds
70
* filter is_digit "1one2two3three" = "123"
71
* filter :: (* -> bool) -> [*] -> [*]
81
/* foldl fn st l: fold list l from the left with function fn and start st
83
* Start from the left hand end of the list (unlike foldr, see below).
84
* foldl is less useful (and much slower).
86
* foldl fn start [a,b .. z] = ((((st fn a) fn b) ..) fn z)
87
* foldl :: (* -> ** -> *) -> * -> [**] -> *
91
= foldl fn (fn st (hd l)) (tl l);
93
/* foldl1 fn l: like foldl, but use the 1st element as the start value
95
* foldl1 fn [1,2,3] == ((1 fn 2) fn 3)
96
* foldl1 :: (* -> * -> *) -> [*] -> *
100
= foldl fn (hd l) (tl l);
102
/* foldr fn st l: fold list l from the right with function fn and start st
104
* foldr fn st [a,b..z] = (a fn (b fn (.. (z fn st))))
105
* foldr :: (* -> ** -> **) -> ** -> [*] -> **
109
= fn (hd l) (foldr fn st (tl l));
111
/* foldrl fn l: like foldr, but use the 1st element as the start value
113
* foldr1 fn [1,2,3,4] == (2 fn (3 fn (4 fn 1)))
114
* foldr1 :: (* -> * -> *) -> [*] -> *
118
= foldr fn (hd l) (tl l);
120
/* Search a list for an element, returning its index (or -1)
122
* index (equal 12) [13,12,11] == 1
123
* index :: (* -> bool) -> [*] -> real
131
= search (tl l) (n + 1);
134
/* init l: remove last element of list l
137
* init [1,2,3] == [1,2]
141
= error "init of []", l == [];
143
= hd l : init (tl l);
145
/* iterate f x: repeatedly apply f to x
147
* return the infinite list [x, f x, f (f x), ..].
148
* iterate (multiply 2) 1 == [1, 2, 4, 8, 16, 32, 64 ... ]
149
* iterate :: (* -> *) -> * -> [*]
151
iterate f x = x : iterate f (f x);
153
/* join_sep sep l: join a list with a separator
155
* join_sep ", " (map print [1 .. 4]) == "1, 2, 3, 4"
156
* join_sep :: [*] -> [[*]] -> [*]
161
fn a b = a ++ sep ++ b;
164
/* last l: return the last element of list l
166
* The dual of hd. last [1,2,3] == 3
170
= error "last of []", l == []
174
/* len l: length of list l
175
* (see also is_list_len and friends in predicate.def)
183
/* limit l: return the first element of l which is equal to its predecessor
185
* useful for checking for convergence
189
= error "incorrect use of limit",
190
l == [] || tl l == [] || tl (tl l) == []
197
/* Turn a function of n args into a function which takes a single arg of an
200
list_1ary fn x = fn x?0;
201
list_2ary fn x = fn x?0 x?1;
202
list_3ary fn x = fn x?0 x?1 x?2;
203
list_4ary fn x = fn x?0 x?1 x?2 x?3;
204
list_5ary fn x = fn x?0 x?1 x?2 x?3 x?4;
205
list_6ary fn x = fn x?0 x?1 x?2 x?3 x?4 x?5;
206
list_7ary fn x = fn x?0 x?1 x?2 x?3 x?4 x?5 x?6;
208
/* map fn l: map function fn over list l
210
* map :: (* -> **) -> [*] -> [**]
214
= f (hd l) : map f (tl l);
216
/* map2 fn l1 l2: map two lists together with fn
218
* map2 :: (* -> ** -> ***) -> [*] -> [**] -> [***]
220
map2 fn l1 l2 = map (list_2ary fn) (zip2 l1 l2);
222
/* map3 fn l1 l2 l3: map three lists together with fn
224
* map3 :: (* -> ** -> *** -> ****) -> [*] -> [**] -> [***] -> [****]
226
map3 fn l1 l2 l3 = map (list_3ary fn) (zip3 l1 l2 l3);
228
/* member l x: true if x is a member of list l
230
* is_digit == member "0123456789"
231
* member :: [*] -> * -> bool
233
member l x = any (map (equal x) l);
235
/* merge b l r: merge two lists based on a bool list
237
* merge :: [bool] -> [*] -> [*] -> [*]
240
= [], p == [] || l == [] || r == []
249
/* mkset eq l: remove duplicates from list l using equality function
251
* mkset :: (* -> bool) -> [*] -> [*]
255
= a : filter (not @ eq a) (mkset eq x)
260
/* postfix l r: add r to the end of list l
263
* postfix :: [*] -> ** -> [*,**]
265
postfix l r = l ++ [r];
267
/* repeat x: make an infinite list of xes
271
repeat x = map (const x) [1..];
273
/* replicate n x: make n copies of x in a list
275
* replicate :: num -> * -> [*]
277
replicate n x = take n (repeat x);
279
/* reverse l: reverse list l
281
* reverse :: [*] -> [*]
283
reverse l = foldl (converse cons) [] l;
285
/* scan fn st l: apply (fold fn r) to every initial segment of a list
287
* scan add 0 [1,2,3] == [1,3,6]
288
* scan :: (* -> ** -> *) -> * -> [**] -> [*]
301
/* sort l: sort list l into ascending order
305
sort l = sortc less_equal l;
307
/* sortc comp l: sort list l into order using a comparision function
309
* Uses merge sort (n log n behaviour)
310
* sortc :: (* -> * -> bool) -> [*] -> [*]
314
= merge (sortc comp (take n2 l)) (sortc comp (drop n2 l))
319
/* merge l1 l2: merge sorted lists l1 and l2 to make a single
325
= a : merge x (b : y), comp a b
326
= b : merge (a : x) y
333
/* sortpl pl l: sort by a list of predicates
335
* sortpl :: (* -> bool) -> [*] -> [*]
340
/* Comparision function ... put true before false, if equal move on to
341
* the next predicate.
353
/* sortr l: sort list l into descending order
355
* sortr :: [*] -> [*]
357
sortr l = sortc more l;
359
/* split fn l: break a list into sections separated by many fn
361
* split is_space " hello world " == ["hello", "world"]
362
* split is_space " " == []
363
* split :: (* -> bool) -> [*] -> [[*]]
366
= [], l == [] || l' == []
367
= head : split fn tail
372
head = takewhile nfn l';
373
tail = dropwhile nfn l';
376
/* splits fn l: break a list into sections separated by a single fn
378
* split (equal ',') ",,1" == ["", "", "1"]
379
* split :: (* -> bool) -> [*] -> [[*]]
383
= head : splits fn tail
390
head = takewhile fn' l;
391
tail = dropif (dropwhile fn' l);
394
/* splitpl fnl l: split a list up with a list of predicates
396
* splitpl [is_digit, is_letter, is_digit] "123cat" == ["123", "cat", []]
397
* splitpl :: [* -> bool] -> [*] -> [[*]]
401
= head : splitpl (tl fnl) tail
403
head = takewhile (hd fnl) l;
404
tail = dropwhile (hd fnl) l;
407
/* split_lines n l: split a list into equal length lines
409
* split_lines 4 "1234567" == ["1234", "567"]
410
* splitl :: int -> [*] -> [[*]]
414
= take n l : split_lines n (drop n l);
416
/* take n l: take the first n elements from list l
417
* take :: num -> [*] -> [*]
422
= hd l : take (n-1) (tl l);
424
/* takewhile fn l: take from the front of a list while predicate fn holds
426
* takewhile is_digit "123onetwothree" == "123"
427
* takewhile :: (* -> bool) -> [*] -> [*]
431
= hd l : takewhile fn (tl l), fn (hd l)
434
/* zip2 l1 l2: zip two lists together
436
* zip2 [1,2] ['a', 'b', 'c'] == [[1,'a'],[2,'b']]
437
* zip2 :: [*] -> [**] -> [[*,**]]
440
= [], l1 == [] || l2 == []
441
= [hd l1, hd l2] : zip2 (tl l1) (tl l2);
443
/* zip3 l1 l2 l3: zip three lists together
445
* zip3 [1,2] ['a', 'b', 'c'] [true] == [[1,'a',true]]
446
* zip3 :: [*] -> [**] ->[***] -> [[*,**,***]]
449
= [], l1 == [] || l2 == [] || l3 == []
450
= [hd l1, hd l2, hd l3] : zip3 (tl l1) (tl l2) (tl l3);