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

Last change on this file since 15773 was 15773, checked in by felix winkelmann, 11 years ago

units used by default have been reduced to library and eval (expand); added -setup-mode option to compiler and interpreter

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