source: project/chicken/trunk/manual/Unit data-structures @ 10796

Last change on this file since 10796 was 10796, checked in by Ivan Raikov, 12 years ago

Factored out unit ports from extras and utils.

File size: 12.8 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
72==== compress
73
74 [procedure] (compress BLIST LIST)
75
76Returns a new list with elements taken from {{LIST}} with
77corresponding 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
89Returns {{LIST1 ...}} concatenated together, with nested lists
90removed (flattened).
91
92
93==== intersperse
94
95 [procedure] (intersperse LIST X)
96
97Returns a new list with {{X}} placed between each element.
98
99
100==== join
101
102 [procedure] (join LISTOFLISTS [LIST])
103
104Concatenates the lists in {{LISTOFLISTS}} with {{LIST}} placed
105between 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
124Returns {{LIST}} with its elements sorted in a random order given by
125procedure RANDOM.
126
127
128==== tail?
129
130 [procedure] (tail? X LIST)
131
132Returns 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
141Returns {{LIST}} converted into a queue, where the first element
142of the list is the same as the first element of the queue. The resulting
143queue may share memory with the list and the list should not be modified
144after this operation.
145
146
147==== make-queue
148
149 [procedure] (make-queue)
150
151Returns a newly created queue.
152
153
154==== queue?
155
156 [procedure] (queue? X)
157
158Returns {{#t}} if {{X}} is a queue, or {{#f}} otherwise.
159
160
161==== queue->list
162
163 [procedure] (queue->list QUEUE)
164
165Returns {{QUEUE}} converted into a list, where the first element
166of the list is the same as the first element of the queue. The resulting
167list 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
174Adds {{X}} to the rear of {{QUEUE}}.
175
176
177==== queue-empty?
178
179 [procedure] (queue-empty? QUEUE)
180
181Returns {{#t}} if {{QUEUE}} is empty, or {{#f}} otherwise.
182
183
184==== queue-first
185
186 [procedure] (queue-first QUEUE)
187
188Returns the first element of {{QUEUE}}. If {{QUEUE}} is empty
189an error is signaled
190
191
192==== queue-last
193
194 [procedure] (queue-last QUEUE)
195
196Returns the last element of {{QUEUE}}. If {{QUEUE}} is empty
197an error is signaled
198
199
200==== queue-remove!
201
202 [procedure] (queue-remove! QUEUE)
203
204Removes and returns the first element of {{QUEUE}}. If {{QUEUE}}
205is empty an error is signaled
206
207
208==== queue-push-back!
209
210 [procedure] (queue-push-back! QUEUE ITEM)
211
212Pushes 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
220Pushes the items in item-list back onto the queue,
221so 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
233Joins two lists in sorted order. {{merge!}} is the destructive
234version of merge. {{LESS?  }} should be a procedure of two arguments,
235that returns true if the first argument is to be ordered before the
236second argument.
237
238
239==== sort
240
241 [procedure] (sort SEQUENCE LESS?)
242 [procedure] (sort! SEQUENCE LESS?)
243
244Sort {{SEQUENCE}}, which should be a list or a vector. {{sort!}}
245is the destructive version of sort.
246
247
248==== sorted?
249
250 [procedure] (sorted? SEQUENCE LESS?)
251
252Returns 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
263Seeds 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
274Returns a string with the string-represenation of all arguments concatenated
275together. {{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
288Returns a string-representation of {{X}}.
289
290
291==== string-chop
292
293 [procedure] (string-chop STRING LENGTH)
294
295Returns a list of substrings taken by ''chopping'' {{STRING}} every {{LENGTH}}
296characters:
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
308If {{STRING}} ends with {{SUFFIX}}, then this procedure returns a copy of its first argument with the suffix
309removed, 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
317Perform a three-way comparison between the {{STRING1}} and {{STRING2}},
318returning either {{-1}} if {{STRING1}} is lexicographically less
319than {{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
327Returns a string that contains all strings in {{LIST}} concatenated
328together.  {{STRING}} is placed between each concatenated string and
329defaults to {{" "}}.
330
331<enscript highlight=scheme>
332(string-intersperse '("one" "two") "three")
333</enscript>
334
335is 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
346Split string into substrings separated by the given delimiters. If
347no delimiters are specified, a string comprising the tab, newline and space characters
348is assumed. If the
349parameter {{KEEPEMPTY}} is given and not {{#f}}, then empty
350substrings 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
362Returns a fresh copy of {{STRING}} with characters matching
363{{FROM}} translated to {{TO}}.  If {{TO}} is omitted, then
364matching characters are removed. {{FROM}} and {{TO}} may be
365a character, a string or a list. If both {{FROM}} and {{TO}}
366are strings, then the character at the same position in {{TO}}
367as the matching character in {{FROM}} is substituted.
368
369
370==== string-translate*
371
372 [procedure] (string-translate* STRING SMAP)
373
374Substitutes elements of {{STRING}} according to {{SMAP}}.
375{{SMAP}} should be an association-list where each element of the list
376is a pair of the form {{(MATCH \. REPLACEMENT)}}. Every occurrence of
377the 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  '(("<" . "&lt;") (">" . "&gt;") ("\"" . "&quot;")) )
384=>  "&lt;h1&gt;this is a &quot;string&quot;&lt;/h1&gt;"
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
393Returns {{#t}} if the strings {{STRING1}} and {{STRING2}} are equal, or
394{{#f}} otherwise.
395The comparison starts at the positions {{START1}} and {{START2}} (which default
396to 0), comparing {{LENGTH}} characters (which defaults to the minimum of the remaining
397length 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
405Searches for first index in string {{WHERE}} where string
406{{WHICH}} occurs.  If the optional argument {{START}} is given,
407then the search starts at that index.  {{substring-index-ci}}
408is a case-insensitive version of {{substring-index}}.
409
410
411
412=== Combinators
413
414
415==== any?
416
417 [procedure] (any? X)
418
419Ignores its argument and always returns {{#t}}. This is actually useful sometimes.
420
421
422==== constantly
423
424 [procedure] (constantly X ...)
425
426Returns 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
437Returns 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
448Returns a procedure that represents the composition of the
449argument-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
465Returns a procedure that returns {{#t}} if its argument satisfies the
466predicates {{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
477Returns a procedure that returns {{#t}} if its argument satisfies any
478predicate {{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
490Returns a procedure that applies {{PROC ...}} to its arguments, and returns the result(s)
491of the last procedure application. For example
492
493<enscript highlight=scheme>
494(each pp eval)
495</enscript>
496
497is 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
513Returns a two-argument procedure that calls {{PROC}} with its
514arguments 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
524Returns its sole argument {{X}}.
525
526
527==== project
528
529 [procedure] (project N)
530
531Returns a procedure that returns its {{N}}th argument (starting from 0).
532
533
534==== list-of
535
536 [procedure] (list-of PRED)
537
538Returns a procedure of one argument that returns {{#t}} when
539applied 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
552Ignores it's arguments, does nothing and returns an unspecified value.
553
554
555==== o
556
557 [procedure] (o PROC ...)
558
559A single value version of {{compose}} (slightly faster). {{(o)}} is equivalent
560to {{identity}}.
561
562=== Binary searching
563
564
565==== binary-search
566
567 [procedure] (binary-search SEQUENCE PROC)
568
569Performs a binary search in {{SEQUENCE}}, which should be a sorted
570list or vector.  {{PROC}} is called to compare items in the sequence,
571should accept a single argument and return an exact integer: zero if the
572searched value is equal to the current item, negative if the searched
573value is ''less'' than the current item, and positive otherwise.
574Returns the index of the found value or {{#f}} otherwise.
575
576Previous: [[Unit eval]]
577
578Next: [[Unit ports]]
Note: See TracBrowser for help on using the repository browser.