source: project/wiki/man/4/Unit data-structures @ 15416

Last change on this file since 15416 was 15416, checked in by svnwiki, 11 years ago

Changes applied for Anonymous (209.136.134.158) through svnwiki:

Removed apostrophe

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