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

Last change on this file since 15896 was 15896, checked in by Ivan Raikov, 10 years ago

merged manual from wiki

File size: 14.2 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=== Strings
287
288
289==== conc
290
291 [procedure] (conc X ...)
292
293Returns a string with the string-represenation of all arguments concatenated
294together. {{conc}} could be implemented as
295
296<enscript highlight=scheme>
297(define (conc . args)
298  (apply string-append (map ->string args)) )
299</enscript>
300
301
302
303==== ->string
304
305 [procedure] (->string X)
306
307Returns a string-representation of {{X}}.
308
309
310==== string-chop
311
312 [procedure] (string-chop STRING LENGTH)
313
314Returns a list of substrings taken by ''chopping'' {{STRING}} every {{LENGTH}}
315characters:
316
317<enscript highlight=scheme>
318(string-chop "one two three" 4)  ==>  ("one " "two " "thre" "e")
319</enscript>
320
321
322
323==== string-chomp
324
325 [procedure] (string-chomp STRING [SUFFIX])
326
327If {{STRING}} ends with {{SUFFIX}}, then this procedure returns a copy of its first argument with the suffix
328removed, otherwise returns {{STRING}} unchanged. {{SUFFIX}} defaults to {{"\n"}}.
329
330
331==== string-compare3
332
333 [procedure] (string-compare3 STRING1 STRING2)
334 [procedure] (string-compare3-ci STRING1 STRING2)
335
336Perform a three-way comparison between the {{STRING1}} and {{STRING2}},
337returning either {{-1}} if {{STRING1}} is lexicographically less
338than {{STRING2}}, {{0}} if it is equal, or {{1}} if it s greater.
339{{string-compare3-ci}} performs a case-insensitive comparison.
340
341
342==== string-intersperse
343
344 [procedure] (string-intersperse LIST [STRING])
345
346Returns a string that contains all strings in {{LIST}} concatenated
347together.  {{STRING}} is placed between each concatenated string and
348defaults to {{" "}}.
349
350<enscript highlight=scheme>
351(string-intersperse '("one" "two") "three")
352</enscript>
353
354is equivalent to
355
356<enscript highlight=scheme>
357(apply string-append (intersperse '("one" "two") "three"))
358</enscript>
359
360
361==== string-split
362
363 [procedure] (string-split STRING [DELIMITER-STRING [KEEPEMPTY]])
364
365Split string into substrings separated by the given delimiters. If
366no delimiters are specified, a string comprising the tab, newline and space characters
367is assumed. If the
368parameter {{KEEPEMPTY}} is given and not {{#f}}, then empty
369substrings are retained:
370
371<enscript highlight=scheme>
372(string-split "one  two  three") ==> ("one" "two" "three")
373(string-split "foo:bar::baz:" ":" #t) ==> ("foo" "bar" "" "baz" "")
374</enscript>
375
376
377==== string-translate
378
379 [procedure] (string-translate STRING FROM [TO])
380
381Returns a fresh copy of {{STRING}} with characters matching
382{{FROM}} translated to {{TO}}.  If {{TO}} is omitted, then
383matching characters are removed. {{FROM}} and {{TO}} may be
384a character, a string or a list. If both {{FROM}} and {{TO}}
385are strings, then the character at the same position in {{TO}}
386as the matching character in {{FROM}} is substituted.
387
388
389==== string-translate*
390
391 [procedure] (string-translate* STRING SMAP)
392
393Substitutes elements of {{STRING}} according to {{SMAP}}.
394{{SMAP}} should be an association-list where each element of the list
395is a pair of the form {{(MATCH \. REPLACEMENT)}}. Every occurrence of
396the string {{MATCH}} in {{STRING}} will be replaced by the string
397{{REPLACEMENT}}:
398
399<enscript highlight=scheme>
400(string-translate*
401  "<h1>this is a \"string\"</h1>"
402  '(("<" . "&lt;") (">" . "&gt;") ("\"" . "&quot;")) )
403=>  "&lt;h1&gt;this is a &quot;string&quot;&lt;/h1&gt;"
404</enscript>
405
406
407==== substring=?
408
409 [procedure] (substring=? STRING1 STRING2 [START1 [START2 [LENGTH]]])
410 [procedure] (substring-ci=? STRING1 STRING2 [START1 [START2 [LENGTH]]])
411
412Returns {{#t}} if the strings {{STRING1}} and {{STRING2}} are equal, or
413{{#f}} otherwise.
414The comparison starts at the positions {{START1}} and {{START2}} (which default
415to 0), comparing {{LENGTH}} characters (which defaults to the minimum of the remaining
416length of both strings).
417
418
419==== substring-index
420
421 [procedure] (substring-index WHICH WHERE [START])
422 [procedure] (substring-index-ci WHICH WHERE [START])
423
424Searches for first index in string {{WHERE}} where string
425{{WHICH}} occurs.  If the optional argument {{START}} is given,
426then the search starts at that index.  {{substring-index-ci}}
427is a case-insensitive version of {{substring-index}}.
428
429
430
431=== Combinators
432
433
434==== any?
435
436 [procedure] (any? X)
437
438Ignores its argument and always returns {{#t}}. This is actually useful sometimes.
439
440
441==== none?
442
443 [procedure] (none? X)
444
445Ignores its argument and always returns {{#f}}. This is actually useful sometimes.
446
447
448==== always?
449
450 [procedure] (always? X)
451
452Ignores its arguments and always returns {{#t}}. This is actually useful sometimes.
453
454
455==== never?
456
457 [procedure] (never? X)
458
459Ignores its arguments and always returns {{#f}}. This is actually useful sometimes.
460
461
462==== constantly
463
464 [procedure] (constantly X ...)
465
466Returns a procedure that always returns the values {{X ...}} regardless of the number and value of its arguments.
467
468<enscript highlight=scheme>
469(constantly X) <=> (lambda args X)
470</enscript>
471
472
473==== complement
474
475 [procedure] (complement PROC)
476
477Returns a procedure that returns the boolean inverse of {{PROC}}.
478
479<enscript highlight=scheme>
480(complement PROC) <=> (lambda (x) (not (PROC x)))
481</enscript>
482
483
484==== compose
485
486 [procedure] (compose PROC1 PROC2 ...)
487
488Returns a procedure that represents the composition of the
489argument-procedures {{PROC1 PROC2 ...}}.
490
491<enscript highlight=scheme>
492(compose F G) <=> (lambda args
493                      (call-with-values
494                         (lambda () (apply G args))
495                         F))
496</enscript>
497
498{{(compose)}} is equivalent to {{values}}.
499
500
501==== conjoin
502
503 [procedure] (conjoin PRED ...)
504
505Returns a procedure that returns {{#t}} if its argument satisfies the
506predicates {{PRED ...}}.
507<enscript highlight=scheme>
508((conjoin odd? positive?) 33)   ==>  #t
509((conjoin odd? positive?) -33)  ==>  #f
510</enscript>
511
512
513==== disjoin
514
515 [procedure] (disjoin PRED ...)
516
517Returns a procedure that returns {{#t}} if its argument satisfies any
518predicate {{PRED ...}}.
519<enscript highlight=scheme>
520((disjoin odd? positive?) 32)    ==>  #t
521((disjoin odd? positive?) -32)   ==>  #f
522</enscript>
523
524
525==== each
526
527 [procedure] (each PROC ...)
528
529Returns a procedure that applies {{PROC ...}} to its arguments, and returns the result(s)
530of the last procedure application. For example
531
532<enscript highlight=scheme>
533(each pp eval)
534</enscript>
535
536is equivalent to
537
538<enscript highlight=scheme>
539(lambda args
540  (apply pp args)
541  (apply eval args) )
542</enscript>
543
544{{(each PROC)}} is equivalent to {{PROC}} and {{(each)}} is equivalent to
545{{noop}}.
546
547
548==== flip
549
550 [procedure] (flip PROC)
551
552Returns a two-argument procedure that calls {{PROC}} with its
553arguments swapped:
554<enscript highlight=scheme>
555(flip PROC) <=> (lambda (x y) (PROC y x))
556</enscript>
557
558
559==== identity
560
561 [procedure] (identity X)
562
563Returns its sole argument {{X}}.
564
565
566==== project
567
568 [procedure] (project N)
569
570Returns a procedure that returns its {{N}}th argument (starting from 0).
571
572
573==== list-of?
574
575 [procedure] (list-of? PRED)
576
577Returns a procedure of one argument that returns {{#t}} when
578applied to a list of elements that all satisfy the predicate procedure
579{{PRED}}, or {{#f}} otherwise.
580
581<enscript highlight=scheme>
582((list-of? even?) '(1 2 3))   ==> #f
583((list-of? number?) '(1 2 3)) ==> #t
584</enscript>
585
586
587==== noop
588
589 [procedure] (noop X ...)
590
591Ignores its arguments, does nothing and returns an unspecified value.
592
593
594==== o
595
596 [procedure] (o PROC ...)
597
598A single value version of {{compose}} (slightly faster). {{(o)}} is equivalent
599to {{identity}}.
600
601
602==== left-section
603
604 [procedure] (left-section PROC ARG0 ...)
605
606Returns a procedure that partially applies some of its arguments starting from the left.
607
608{{PROC}} a procedure.
609
610{{ARG0 ...}} some prefix of the arguments for {{PROC}}.
611
612
613==== right-section
614
615 [procedure] (right-section PROC ARG0 ...)
616
617Returns a procedure that partially applies some of its arguments starting from the right.
618
619{{PROC}} a procedure.
620
621{{ARG0 ...}} some reversed suffix of the arguments for {{PROC}}.
622
623
624
625=== Binary searching
626
627
628==== binary-search
629
630 [procedure] (binary-search SEQUENCE PROC)
631
632Performs a binary search in {{SEQUENCE}}, which should be a sorted
633list or vector.  {{PROC}} is called to compare items in the sequence,
634should accept a single argument and return an exact integer: zero if the
635searched value is equal to the current item, negative if the searched
636value is ''less'' than the current item, and positive otherwise.
637Returns the index of the found value or {{#f}} otherwise.
638
639---
640Previous: [[Unit expand]]
641
642Next: [[Unit ports]]
Note: See TracBrowser for help on using the repository browser.