source: project/chicken/branches/prerelease/manual/Unit data-structures @ 11958

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

Merged trunk and prerelease.

File size: 13.6 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==== none?
423
424 [procedure] (none? X)
425
426Ignores its argument and always returns {{#f}}. This is actually useful sometimes.
427
428
429==== always?
430
431 [procedure] (always? X)
432
433Ignores its arguments and always returns {{#t}}. This is actually useful sometimes.
434
435
436==== never?
437
438 [procedure] (never? X)
439
440Ignores its arguments and always returns {{#f}}. This is actually useful sometimes.
441
442
443==== constantly
444
445 [procedure] (constantly X ...)
446
447Returns a procedure that always returns the values {{X ...}} regardless of the number and value of its arguments.
448
449<enscript highlight=scheme>
450(constantly X) <=> (lambda args X)
451</enscript>
452
453
454==== complement
455
456 [procedure] (complement PROC)
457
458Returns a procedure that returns the boolean inverse of {{PROC}}.
459
460<enscript highlight=scheme>
461(complement PROC) <=> (lambda (x) (not (PROC x)))
462</enscript>
463
464
465==== compose
466
467 [procedure] (compose PROC1 PROC2 ...)
468
469Returns a procedure that represents the composition of the
470argument-procedures {{PROC1 PROC2 ...}}.
471
472<enscript highlight=scheme>
473(compose F G) <=> (lambda args
474                      (call-with-values
475                         (lambda () (apply G args))
476                         F))
477</enscript>
478
479{{(compose)}} is equivalent to {{values}}.
480
481
482==== conjoin
483
484 [procedure] (conjoin PRED ...)
485
486Returns a procedure that returns {{#t}} if its argument satisfies the
487predicates {{PRED ...}}.
488<enscript highlight=scheme>
489((conjoin odd? positive?) 33)   ==>  #t
490((conjoin odd? positive?) -33)  ==>  #f
491</enscript>
492
493
494==== disjoin
495
496 [procedure] (disjoin PRED ...)
497
498Returns a procedure that returns {{#t}} if its argument satisfies any
499predicate {{PRED ...}}.
500<enscript highlight=scheme>
501((disjoin odd? positive?) 32)    ==>  #t
502((disjoin odd? positive?) -32)   ==>  #f
503</enscript>
504
505
506==== each
507
508 [procedure] (each PROC ...)
509
510Returns a procedure that applies {{PROC ...}} to its arguments, and returns the result(s)
511of the last procedure application. For example
512
513<enscript highlight=scheme>
514(each pp eval)
515</enscript>
516
517is equivalent to
518
519<enscript highlight=scheme>
520(lambda args
521  (apply pp args)
522  (apply eval args) )
523</enscript>
524
525{{(each PROC)}} is equivalent to {{PROC}} and {{(each)}} is equivalent to
526{{noop}}.
527
528
529==== flip
530
531 [procedure] (flip PROC)
532
533Returns a two-argument procedure that calls {{PROC}} with its
534arguments swapped:
535<enscript highlight=scheme>
536(flip PROC) <=> (lambda (x y) (PROC y x))
537</enscript>
538
539
540==== identity
541
542 [procedure] (identity X)
543
544Returns its sole argument {{X}}.
545
546
547==== project
548
549 [procedure] (project N)
550
551Returns a procedure that returns its {{N}}th argument (starting from 0).
552
553
554==== list-of
555
556 [procedure] (list-of PRED)
557
558Returns a procedure of one argument that returns {{#t}} when
559applied to a list of elements that all satisfy the predicate procedure
560{{PRED}}, or {{#f}} otherwise.
561
562<enscript highlight=scheme>
563((list-of even?) '(1 2 3))   ==> #f
564((list-of number?) '(1 2 3)) ==> #t
565</enscript>
566
567
568==== noop
569
570 [procedure] (noop X ...)
571
572Ignores it's arguments, does nothing and returns an unspecified value.
573
574
575==== o
576
577 [procedure] (o PROC ...)
578
579A single value version of {{compose}} (slightly faster). {{(o)}} is equivalent
580to {{identity}}.
581
582
583==== left-section
584
585 [procedure] (left-section PROC ARG0 ...)
586
587Returns a procedure that partially applies some of its' arguments starting from the left.
588
589{{PROC}} a procedure.
590
591{{ARG0 ...}} some prefix of the arguments for {{PROC}}.
592
593
594==== right-section
595
596 [procedure] (right-section PROC ARG0 ...)
597
598Returns a procedure that partially applies some of its' arguments starting from the right.
599
600{{PROC}} a procedure.
601
602{{ARG0 ...}} some reversed suffix of the arguments for {{PROC}}.
603
604
605
606=== Binary searching
607
608
609==== binary-search
610
611 [procedure] (binary-search SEQUENCE PROC)
612
613Performs a binary search in {{SEQUENCE}}, which should be a sorted
614list or vector.  {{PROC}} is called to compare items in the sequence,
615should accept a single argument and return an exact integer: zero if the
616searched value is equal to the current item, negative if the searched
617value is ''less'' than the current item, and positive otherwise.
618Returns the index of the found value or {{#f}} otherwise.
619
620Previous: [[Unit eval]]
621
622Next: [[Unit ports]]
Note: See TracBrowser for help on using the repository browser.