1 | [[tags: manual]] |
---|
2 | [[toc:]] |
---|
3 | |
---|
4 | == Unit data-structures |
---|
5 | |
---|
6 | This unit contains a collection of procedures related to data |
---|
7 | structures. This unit is used by default, unless the program is |
---|
8 | compiled with the {{-explicit-use}} option. |
---|
9 | |
---|
10 | |
---|
11 | === Lists |
---|
12 | |
---|
13 | |
---|
14 | ==== alist-ref |
---|
15 | |
---|
16 | [procedure] (alist-ref KEY ALIST [TEST [DEFAULT]]) |
---|
17 | |
---|
18 | Looks up {{KEY}} in {{ALIST}} using {{TEST}} as the comparison function (or {{eqv?}} if |
---|
19 | no test was given) and returns the cdr of the found pair, or {{DEFAULT}} (which defaults to {{#f}}). |
---|
20 | |
---|
21 | |
---|
22 | ==== alist-update! |
---|
23 | |
---|
24 | [procedure] (alist-update! KEY VALUE ALIST [TEST]) |
---|
25 | |
---|
26 | If the list {{ALIST}} contains a pair of the form {{(KEY . X)}}, then this procedure |
---|
27 | replaces {{X}} with {{VALUE}} and returns {{ALIST}}. If {{ALIST}} contains no such item, then |
---|
28 | {{alist-update!}} returns {{((KEY . VALUE) . ALIST)}}. The optional argument |
---|
29 | {{TEST}} specifies the comparison procedure to search a matching pair in {{ALIST}} |
---|
30 | and defaults to {{eqv?}}. |
---|
31 | |
---|
32 | |
---|
33 | ==== atom? |
---|
34 | |
---|
35 | [procedure] (atom? X) |
---|
36 | |
---|
37 | Returns {{#t}} if {{X}} is not a pair. This is identical to {{not-pair?}} from [[Unit srfi-1]] but |
---|
38 | kept for historical reasons. |
---|
39 | |
---|
40 | |
---|
41 | ==== rassoc |
---|
42 | |
---|
43 | [procedure] (rassoc KEY LIST [TEST]) |
---|
44 | |
---|
45 | Similar to {{assoc}}, but compares {{KEY}} with the {{cdr}} of each pair in {{LIST}} using |
---|
46 | {{TEST}} as the comparison procedures (which defaults to {{eqv?}}. |
---|
47 | |
---|
48 | |
---|
49 | ==== butlast |
---|
50 | |
---|
51 | [procedure] (butlast LIST) |
---|
52 | |
---|
53 | Returns a fresh list with all elements but the last of {{LIST}}. |
---|
54 | |
---|
55 | |
---|
56 | ==== chop |
---|
57 | |
---|
58 | [procedure] (chop LIST N) |
---|
59 | |
---|
60 | Returns a new list of sublists, where each sublist contains {{N}} |
---|
61 | elements of {{LIST}}. If {{LIST}} has a length that is not |
---|
62 | a multiple of {{N}}, then the last sublist contains the remaining |
---|
63 | elements. |
---|
64 | |
---|
65 | <enscript highlight=scheme> |
---|
66 | (chop '(1 2 3 4 5 6) 2) ==> ((1 2) (3 4) (5 6)) |
---|
67 | (chop '(a b c d) 3) ==> ((a b c) (d)) |
---|
68 | </enscript> |
---|
69 | |
---|
70 | |
---|
71 | |
---|
72 | ==== compress |
---|
73 | |
---|
74 | [procedure] (compress BLIST LIST) |
---|
75 | |
---|
76 | Returns a new list with elements taken from {{LIST}} with |
---|
77 | corresponding true values in the list {{BLIST}}. |
---|
78 | |
---|
79 | <enscript highlight=scheme> |
---|
80 | (define nums '(99 100 110 401 1234)) |
---|
81 | (compress (map odd? nums) nums) ==> (99 401) |
---|
82 | </enscript> |
---|
83 | |
---|
84 | |
---|
85 | ==== flatten |
---|
86 | |
---|
87 | [procedure] (flatten LIST1 ...) |
---|
88 | |
---|
89 | Returns {{LIST1 ...}} concatenated together, with nested lists |
---|
90 | removed (flattened). |
---|
91 | |
---|
92 | |
---|
93 | ==== intersperse |
---|
94 | |
---|
95 | [procedure] (intersperse LIST X) |
---|
96 | |
---|
97 | Returns a new list with {{X}} placed between each element. |
---|
98 | |
---|
99 | |
---|
100 | ==== join |
---|
101 | |
---|
102 | [procedure] (join LISTOFLISTS [LIST]) |
---|
103 | |
---|
104 | Concatenates the lists in {{LISTOFLISTS}} with {{LIST}} placed |
---|
105 | between each sublist. {{LIST}} defaults to the empty list. |
---|
106 | |
---|
107 | <enscript highlight=scheme> |
---|
108 | (join '((a b) (c d) (e)) '(x y)) ==> (a b x y c d x y e) |
---|
109 | (join '((p q) () (r (s) t)) '(-)) ==> (p q - - r (s) t) |
---|
110 | </enscript> |
---|
111 | |
---|
112 | {{join}} could be implemented as follows: |
---|
113 | |
---|
114 | <enscript highlight=scheme> |
---|
115 | (define (join lstoflsts #!optional (lst '())) |
---|
116 | (apply append (intersperse lstoflists lst)) ) |
---|
117 | </enscript> |
---|
118 | |
---|
119 | |
---|
120 | ==== shuffle |
---|
121 | |
---|
122 | [procedure] (shuffle LIST RANDOM) |
---|
123 | |
---|
124 | Returns {{LIST}} with its elements sorted in a random order given by |
---|
125 | procedure RANDOM. |
---|
126 | |
---|
127 | |
---|
128 | ==== tail? |
---|
129 | |
---|
130 | [procedure] (tail? X LIST) |
---|
131 | |
---|
132 | Returns true if {{X}} is one of the tails (cdr's) of {{LIST}}. |
---|
133 | |
---|
134 | === Queues |
---|
135 | |
---|
136 | |
---|
137 | ==== list->queue |
---|
138 | |
---|
139 | [procedure] (list->queue LIST) |
---|
140 | |
---|
141 | Returns {{LIST}} converted into a queue, where the first element |
---|
142 | of the list is the same as the first element of the queue. The resulting |
---|
143 | queue may share memory with the list and the list should not be modified |
---|
144 | after this operation. |
---|
145 | |
---|
146 | |
---|
147 | ==== make-queue |
---|
148 | |
---|
149 | [procedure] (make-queue) |
---|
150 | |
---|
151 | Returns a newly created queue. |
---|
152 | |
---|
153 | |
---|
154 | ==== queue? |
---|
155 | |
---|
156 | [procedure] (queue? X) |
---|
157 | |
---|
158 | Returns {{#t}} if {{X}} is a queue, or {{#f}} otherwise. |
---|
159 | |
---|
160 | |
---|
161 | ==== queue->list |
---|
162 | |
---|
163 | [procedure] (queue->list QUEUE) |
---|
164 | |
---|
165 | Returns {{QUEUE}} converted into a list, where the first element |
---|
166 | of the list is the same as the first element of the queue. The resulting |
---|
167 | list may share memory with the queue object and should not be modified. |
---|
168 | |
---|
169 | |
---|
170 | ==== queue-add! |
---|
171 | |
---|
172 | [procedure] (queue-add! QUEUE X) |
---|
173 | |
---|
174 | Adds {{X}} to the rear of {{QUEUE}}. |
---|
175 | |
---|
176 | |
---|
177 | ==== queue-empty? |
---|
178 | |
---|
179 | [procedure] (queue-empty? QUEUE) |
---|
180 | |
---|
181 | Returns {{#t}} if {{QUEUE}} is empty, or {{#f}} otherwise. |
---|
182 | |
---|
183 | |
---|
184 | ==== queue-first |
---|
185 | |
---|
186 | [procedure] (queue-first QUEUE) |
---|
187 | |
---|
188 | Returns the first element of {{QUEUE}}. If {{QUEUE}} is empty |
---|
189 | an error is signaled |
---|
190 | |
---|
191 | |
---|
192 | ==== queue-last |
---|
193 | |
---|
194 | [procedure] (queue-last QUEUE) |
---|
195 | |
---|
196 | Returns the last element of {{QUEUE}}. If {{QUEUE}} is empty |
---|
197 | an error is signaled |
---|
198 | |
---|
199 | |
---|
200 | ==== queue-remove! |
---|
201 | |
---|
202 | [procedure] (queue-remove! QUEUE) |
---|
203 | |
---|
204 | Removes and returns the first element of {{QUEUE}}. If {{QUEUE}} |
---|
205 | is empty an error is signaled |
---|
206 | |
---|
207 | |
---|
208 | ==== queue-push-back! |
---|
209 | |
---|
210 | [procedure] (queue-push-back! QUEUE ITEM) |
---|
211 | |
---|
212 | Pushes an item into the first position of a queue, i.e. the next |
---|
213 | {{queue-remove!}} will return {{ITEM}}. |
---|
214 | |
---|
215 | |
---|
216 | ==== queue-push-back-list! |
---|
217 | |
---|
218 | [procedure] (queue-push-back-list! QUEUE LIST) |
---|
219 | |
---|
220 | Pushes the items in item-list back onto the queue, |
---|
221 | so that {{(car LIST)}} becomes the next removable item. |
---|
222 | |
---|
223 | |
---|
224 | |
---|
225 | === Sorting |
---|
226 | |
---|
227 | |
---|
228 | ==== merge |
---|
229 | |
---|
230 | [procedure] (merge LIST1 LIST2 LESS?) |
---|
231 | [procedure] (merge! LIST1 LIST2 LESS?) |
---|
232 | |
---|
233 | Joins two lists in sorted order. {{merge!}} is the destructive |
---|
234 | version of merge. {{LESS? }} should be a procedure of two arguments, |
---|
235 | that returns true if the first argument is to be ordered before the |
---|
236 | second argument. |
---|
237 | |
---|
238 | |
---|
239 | ==== sort |
---|
240 | |
---|
241 | [procedure] (sort SEQUENCE LESS?) |
---|
242 | [procedure] (sort! SEQUENCE LESS?) |
---|
243 | |
---|
244 | Sort {{SEQUENCE}}, which should be a list or a vector. {{sort!}} |
---|
245 | is the destructive version of sort. |
---|
246 | |
---|
247 | |
---|
248 | ==== sorted? |
---|
249 | |
---|
250 | [procedure] (sorted? SEQUENCE LESS?) |
---|
251 | |
---|
252 | Returns true if the list or vector {{SEQUENCE}} is already sorted. |
---|
253 | |
---|
254 | |
---|
255 | |
---|
256 | === Random numbers |
---|
257 | |
---|
258 | |
---|
259 | ==== random-seed |
---|
260 | |
---|
261 | [procedure] (random-seed [SEED]) |
---|
262 | |
---|
263 | Seeds the random number generator with {{SEED}} (an exact integer) or |
---|
264 | {{(current-seconds)}} if {{SEED}} is not given. |
---|
265 | |
---|
266 | |
---|
267 | === Strings |
---|
268 | |
---|
269 | |
---|
270 | ==== conc |
---|
271 | |
---|
272 | [procedure] (conc X ...) |
---|
273 | |
---|
274 | Returns a string with the string-represenation of all arguments concatenated |
---|
275 | together. {{conc}} could be implemented as |
---|
276 | |
---|
277 | <enscript highlight=scheme> |
---|
278 | (define (conc . args) |
---|
279 | (apply string-append (map ->string args)) ) |
---|
280 | </enscript> |
---|
281 | |
---|
282 | |
---|
283 | |
---|
284 | ==== ->string |
---|
285 | |
---|
286 | [procedure] (->string X) |
---|
287 | |
---|
288 | Returns a string-representation of {{X}}. |
---|
289 | |
---|
290 | |
---|
291 | ==== string-chop |
---|
292 | |
---|
293 | [procedure] (string-chop STRING LENGTH) |
---|
294 | |
---|
295 | Returns a list of substrings taken by ''chopping'' {{STRING}} every {{LENGTH}} |
---|
296 | characters: |
---|
297 | |
---|
298 | <enscript highlight=scheme> |
---|
299 | (string-chop "one two three" 4) ==> ("one " "two " "thre" "e") |
---|
300 | </enscript> |
---|
301 | |
---|
302 | |
---|
303 | |
---|
304 | ==== string-chomp |
---|
305 | |
---|
306 | [procedure] (string-chomp STRING [SUFFIX]) |
---|
307 | |
---|
308 | If {{STRING}} ends with {{SUFFIX}}, then this procedure returns a copy of its first argument with the suffix |
---|
309 | removed, otherwise returns {{STRING}} unchanged. {{SUFFIX}} defaults to {{"\n"}}. |
---|
310 | |
---|
311 | |
---|
312 | ==== string-compare3 |
---|
313 | |
---|
314 | [procedure] (string-compare3 STRING1 STRING2) |
---|
315 | [procedure] (string-compare3-ci STRING1 STRING2) |
---|
316 | |
---|
317 | Perform a three-way comparison between the {{STRING1}} and {{STRING2}}, |
---|
318 | returning either {{-1}} if {{STRING1}} is lexicographically less |
---|
319 | than {{STRING2}}, {{0}} if it is equal, or {{1}} if it s greater. |
---|
320 | {{string-compare3-ci}} performs a case-insensitive comparison. |
---|
321 | |
---|
322 | |
---|
323 | ==== string-intersperse |
---|
324 | |
---|
325 | [procedure] (string-intersperse LIST [STRING]) |
---|
326 | |
---|
327 | Returns a string that contains all strings in {{LIST}} concatenated |
---|
328 | together. {{STRING}} is placed between each concatenated string and |
---|
329 | defaults to {{" "}}. |
---|
330 | |
---|
331 | <enscript highlight=scheme> |
---|
332 | (string-intersperse '("one" "two") "three") |
---|
333 | </enscript> |
---|
334 | |
---|
335 | is equivalent to |
---|
336 | |
---|
337 | <enscript highlight=scheme> |
---|
338 | (apply string-append (intersperse '("one" "two") "three")) |
---|
339 | </enscript> |
---|
340 | |
---|
341 | |
---|
342 | ==== string-split |
---|
343 | |
---|
344 | [procedure] (string-split STRING [DELIMITER-STRING [KEEPEMPTY]]) |
---|
345 | |
---|
346 | Split string into substrings separated by the given delimiters. If |
---|
347 | no delimiters are specified, a string comprising the tab, newline and space characters |
---|
348 | is assumed. If the |
---|
349 | parameter {{KEEPEMPTY}} is given and not {{#f}}, then empty |
---|
350 | substrings are retained: |
---|
351 | |
---|
352 | <enscript highlight=scheme> |
---|
353 | (string-split "one two three") ==> ("one" "two" "three") |
---|
354 | (string-split "foo:bar::baz:" ":" #t) ==> ("foo" "bar" "" "baz" "") |
---|
355 | </enscript> |
---|
356 | |
---|
357 | |
---|
358 | ==== string-translate |
---|
359 | |
---|
360 | [procedure] (string-translate STRING FROM [TO]) |
---|
361 | |
---|
362 | Returns a fresh copy of {{STRING}} with characters matching |
---|
363 | {{FROM}} translated to {{TO}}. If {{TO}} is omitted, then |
---|
364 | matching characters are removed. {{FROM}} and {{TO}} may be |
---|
365 | a character, a string or a list. If both {{FROM}} and {{TO}} |
---|
366 | are strings, then the character at the same position in {{TO}} |
---|
367 | as the matching character in {{FROM}} is substituted. |
---|
368 | |
---|
369 | |
---|
370 | ==== string-translate* |
---|
371 | |
---|
372 | [procedure] (string-translate* STRING SMAP) |
---|
373 | |
---|
374 | Substitutes elements of {{STRING}} according to {{SMAP}}. |
---|
375 | {{SMAP}} should be an association-list where each element of the list |
---|
376 | is a pair of the form {{(MATCH \. REPLACEMENT)}}. Every occurrence of |
---|
377 | the string {{MATCH}} in {{STRING}} will be replaced by the string |
---|
378 | {{REPLACEMENT}}: |
---|
379 | |
---|
380 | <enscript highlight=scheme> |
---|
381 | (string-translate* |
---|
382 | "<h1>this is a \"string\"</h1>" |
---|
383 | '(("<" . "<") (">" . ">") ("\"" . """)) ) |
---|
384 | => "<h1>this is a "string"</h1>" |
---|
385 | </enscript> |
---|
386 | |
---|
387 | |
---|
388 | ==== substring=? |
---|
389 | |
---|
390 | [procedure] (substring=? STRING1 STRING2 [START1 [START2 [LENGTH]]]) |
---|
391 | [procedure] (substring-ci=? STRING1 STRING2 [START1 [START2 [LENGTH]]]) |
---|
392 | |
---|
393 | Returns {{#t}} if the strings {{STRING1}} and {{STRING2}} are equal, or |
---|
394 | {{#f}} otherwise. |
---|
395 | The comparison starts at the positions {{START1}} and {{START2}} (which default |
---|
396 | to 0), comparing {{LENGTH}} characters (which defaults to the minimum of the remaining |
---|
397 | length of both strings). |
---|
398 | |
---|
399 | |
---|
400 | ==== substring-index |
---|
401 | |
---|
402 | [procedure] (substring-index WHICH WHERE [START]) |
---|
403 | [procedure] (substring-index-ci WHICH WHERE [START]) |
---|
404 | |
---|
405 | Searches for first index in string {{WHERE}} where string |
---|
406 | {{WHICH}} occurs. If the optional argument {{START}} is given, |
---|
407 | then the search starts at that index. {{substring-index-ci}} |
---|
408 | is a case-insensitive version of {{substring-index}}. |
---|
409 | |
---|
410 | |
---|
411 | |
---|
412 | === Combinators |
---|
413 | |
---|
414 | |
---|
415 | ==== any? |
---|
416 | |
---|
417 | [procedure] (any? X) |
---|
418 | |
---|
419 | Ignores its argument and always returns {{#t}}. This is actually useful sometimes. |
---|
420 | |
---|
421 | |
---|
422 | ==== constantly |
---|
423 | |
---|
424 | [procedure] (constantly X ...) |
---|
425 | |
---|
426 | Returns a procedure that always returns the values {{X ...}} regardless of the number and value of its arguments. |
---|
427 | |
---|
428 | <enscript highlight=scheme> |
---|
429 | (constantly X) <=> (lambda args X) |
---|
430 | </enscript> |
---|
431 | |
---|
432 | |
---|
433 | ==== complement |
---|
434 | |
---|
435 | [procedure] (complement PROC) |
---|
436 | |
---|
437 | Returns a procedure that returns the boolean inverse of {{PROC}}. |
---|
438 | |
---|
439 | <enscript highlight=scheme> |
---|
440 | (complement PROC) <=> (lambda (x) (not (PROC x))) |
---|
441 | </enscript> |
---|
442 | |
---|
443 | |
---|
444 | ==== compose |
---|
445 | |
---|
446 | [procedure] (compose PROC1 PROC2 ...) |
---|
447 | |
---|
448 | Returns a procedure that represents the composition of the |
---|
449 | argument-procedures {{PROC1 PROC2 ...}}. |
---|
450 | |
---|
451 | <enscript highlight=scheme> |
---|
452 | (compose F G) <=> (lambda args |
---|
453 | (call-with-values |
---|
454 | (lambda () (apply G args)) |
---|
455 | F)) |
---|
456 | </enscript> |
---|
457 | |
---|
458 | {{(compose)}} is equivalent to {{values}}. |
---|
459 | |
---|
460 | |
---|
461 | ==== conjoin |
---|
462 | |
---|
463 | [procedure] (conjoin PRED ...) |
---|
464 | |
---|
465 | Returns a procedure that returns {{#t}} if its argument satisfies the |
---|
466 | predicates {{PRED ...}}. |
---|
467 | <enscript highlight=scheme> |
---|
468 | ((conjoin odd? positive?) 33) ==> #t |
---|
469 | ((conjoin odd? positive?) -33) ==> #f |
---|
470 | </enscript> |
---|
471 | |
---|
472 | |
---|
473 | ==== disjoin |
---|
474 | |
---|
475 | [procedure] (disjoin PRED ...) |
---|
476 | |
---|
477 | Returns a procedure that returns {{#t}} if its argument satisfies any |
---|
478 | predicate {{PRED ...}}. |
---|
479 | <enscript highlight=scheme> |
---|
480 | ((disjoin odd? positive?) 32) ==> #t |
---|
481 | ((disjoin odd? positive?) -32) ==> #f |
---|
482 | </enscript> |
---|
483 | |
---|
484 | |
---|
485 | |
---|
486 | ==== each |
---|
487 | |
---|
488 | [procedure] (each PROC ...) |
---|
489 | |
---|
490 | Returns a procedure that applies {{PROC ...}} to its arguments, and returns the result(s) |
---|
491 | of the last procedure application. For example |
---|
492 | |
---|
493 | <enscript highlight=scheme> |
---|
494 | (each pp eval) |
---|
495 | </enscript> |
---|
496 | |
---|
497 | is equivalent to |
---|
498 | |
---|
499 | <enscript highlight=scheme> |
---|
500 | (lambda args |
---|
501 | (apply pp args) |
---|
502 | (apply eval args) ) |
---|
503 | </enscript> |
---|
504 | |
---|
505 | {{(each PROC)}} is equivalent to {{PROC}} and {{(each)}} is equivalent to |
---|
506 | {{noop}}. |
---|
507 | |
---|
508 | |
---|
509 | ==== flip |
---|
510 | |
---|
511 | [procedure] (flip PROC) |
---|
512 | |
---|
513 | Returns a two-argument procedure that calls {{PROC}} with its |
---|
514 | arguments swapped: |
---|
515 | <enscript highlight=scheme> |
---|
516 | (flip PROC) <=> (lambda (x y) (PROC y x)) |
---|
517 | </enscript> |
---|
518 | |
---|
519 | |
---|
520 | ==== identity |
---|
521 | |
---|
522 | [procedure] (identity X) |
---|
523 | |
---|
524 | Returns its sole argument {{X}}. |
---|
525 | |
---|
526 | |
---|
527 | ==== project |
---|
528 | |
---|
529 | [procedure] (project N) |
---|
530 | |
---|
531 | Returns a procedure that returns its {{N}}th argument (starting from 0). |
---|
532 | |
---|
533 | |
---|
534 | ==== list-of |
---|
535 | |
---|
536 | [procedure] (list-of PRED) |
---|
537 | |
---|
538 | Returns a procedure of one argument that returns {{#t}} when |
---|
539 | applied to a list of elements that all satisfy the predicate procedure |
---|
540 | {{PRED}}, or {{#f}} otherwise. |
---|
541 | |
---|
542 | <enscript highlight=scheme> |
---|
543 | ((list-of even?) '(1 2 3)) ==> #f |
---|
544 | ((list-of number?) '(1 2 3)) ==> #t |
---|
545 | </enscript> |
---|
546 | |
---|
547 | |
---|
548 | ==== noop |
---|
549 | |
---|
550 | [procedure] (noop X ...) |
---|
551 | |
---|
552 | Ignores it's arguments, does nothing and returns an unspecified value. |
---|
553 | |
---|
554 | |
---|
555 | ==== o |
---|
556 | |
---|
557 | [procedure] (o PROC ...) |
---|
558 | |
---|
559 | A single value version of {{compose}} (slightly faster). {{(o)}} is equivalent |
---|
560 | to {{identity}}. |
---|
561 | |
---|
562 | === Binary searching |
---|
563 | |
---|
564 | |
---|
565 | ==== binary-search |
---|
566 | |
---|
567 | [procedure] (binary-search SEQUENCE PROC) |
---|
568 | |
---|
569 | Performs a binary search in {{SEQUENCE}}, which should be a sorted |
---|
570 | list or vector. {{PROC}} is called to compare items in the sequence, |
---|
571 | should accept a single argument and return an exact integer: zero if the |
---|
572 | searched value is equal to the current item, negative if the searched |
---|
573 | value is ''less'' than the current item, and positive otherwise. |
---|
574 | Returns the index of the found value or {{#f}} otherwise. |
---|
575 | |
---|
576 | Previous: [[Unit eval]] |
---|
577 | |
---|
578 | Next: [[Unit ports]] |
---|