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

Last change on this file since 28559 was 28559, checked in by Jim Ursetto, 8 years ago

wiki/man/4: Note alist-update introduced in 4.7.4

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.  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]])</procedure>
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])</procedure>
25<procedure>(alist-update! KEY VALUE ALIST [TEST])</procedure>
26
27If the list {{ALIST}} contains a pair of the form {{(KEY . X)}}, then this procedure
28replaces {{X}} with {{VALUE}} and returns {{ALIST}}. If {{ALIST}} contains no such item, then
29{{alist-update}} returns {{((KEY . VALUE) . ALIST)}}. The optional argument
30{{TEST}} specifies the comparison procedure to search a matching pair in {{ALIST}}
31and defaults to {{eqv?}}. {{alist-update!}} is the destructive version of {{alist-update}}.
32
33{{alist-update}} (the non-destructive version) was introduced in Chicken 4.7.4.
34
35==== atom?
36
37<procedure>(atom? X)</procedure>
38
39Returns {{#t}} if {{X}} is not a pair. This is identical to {{not-pair?}} from [[Unit srfi-1]] but
40kept for historical reasons.
41
42
43==== rassoc
44
45<procedure>(rassoc KEY LIST [TEST])</procedure>
46
47Similar to {{assoc}}, but compares {{KEY}} with the {{cdr}} of each pair in {{LIST}} using
48{{TEST}} as the comparison procedures (which defaults to {{eqv?}}.
49
50
51==== butlast
52
53<procedure>(butlast LIST)</procedure>
54
55Returns a fresh list with all elements but the last of {{LIST}}.
56
57
58==== chop
59
60<procedure>(chop LIST N)</procedure>
61
62Returns a new list of sublists, where each sublist contains {{N}}
63elements of {{LIST}}. If {{LIST}} has a length that is not
64a multiple of {{N}}, then the last sublist contains the remaining
65elements.
66
67<enscript highlight=scheme>
68(chop '(1 2 3 4 5 6) 2) ==> ((1 2) (3 4) (5 6))
69(chop '(a b c d) 3)     ==> ((a b c) (d))
70</enscript>
71
72
73==== compress
74
75<procedure>(compress BLIST LIST)</procedure>
76
77Returns a new list with elements taken from {{LIST}} with
78corresponding true values in the list {{BLIST}}.
79
80<enscript highlight=scheme>
81(define nums '(99 100 110 401 1234))
82(compress (map odd? nums) nums)      ==> (99 401)
83</enscript>
84
85
86==== flatten
87
88<procedure>(flatten LIST1 ...)</procedure>
89
90Returns {{LIST1 ...}} concatenated together, with nested lists
91removed (flattened).
92
93
94==== intersperse
95
96<procedure>(intersperse LIST X)</procedure>
97
98Returns a new list with {{X}} placed between each element.
99
100
101==== join
102
103<procedure>(join LISTOFLISTS [LIST])</procedure>
104
105Concatenates the lists in {{LISTOFLISTS}} with {{LIST}} placed
106between each sublist. {{LIST}} defaults to the empty list.
107
108<enscript highlight=scheme>
109(join '((a b) (c d) (e)) '(x y)) ==> (a b x y c d x y e)
110(join '((p q) () (r (s) t)) '(-))  ==> (p q - - r (s) t)
111</enscript>
112
113{{join}} could be implemented as follows:
114
115<enscript highlight=scheme>
116(define (join lstoflsts #!optional (lst '()))
117  (apply append (intersperse lstoflists lst)) )
118</enscript>
119
120
121==== tail?
122
123<procedure>(tail? X LIST)</procedure>
124
125Returns true if {{X}} is one of the tails (cdr's) of {{LIST}}.
126
127=== Queues
128
129
130==== list->queue
131
132<procedure>(list->queue LIST)</procedure>
133
134Returns {{LIST}} converted into a queue, where the first element
135of the list is the same as the first element of the queue. The resulting
136queue may share memory with the list and the list should not be modified
137after this operation.
138
139
140==== make-queue
141
142<procedure>(make-queue)</procedure>
143
144Returns a newly created queue.
145
146
147==== queue?
148
149<procedure>(queue? X)</procedure>
150
151Returns {{#t}} if {{X}} is a queue, or {{#f}} otherwise.
152
153
154==== queue-length
155
156<procedure>(queue-length QUEUE)</procedure>
157
158Returns the current number of items stored in {{QUEUE}}.
159
160
161==== queue->list
162
163<procedure>(queue->list QUEUE)</procedure>
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 is freshly allocated and does not share memory with the queue object.
168
169
170==== queue-add!
171
172<procedure>(queue-add! QUEUE X)</procedure>
173
174Adds {{X}} to the rear of {{QUEUE}}.
175
176
177==== queue-empty?
178
179<procedure>(queue-empty? QUEUE)</procedure>
180
181Returns {{#t}} if {{QUEUE}} is empty, or {{#f}} otherwise.
182
183
184==== queue-first
185
186<procedure>(queue-first QUEUE)</procedure>
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)</procedure>
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)</procedure>
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)</procedure>
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)</procedure>
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?)</procedure><br>
231<procedure>(merge! LIST1 LIST2 LESS?)</procedure>
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?)</procedure><br>
242<procedure>(sort! SEQUENCE LESS?)</procedure>
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?)</procedure>
251
252Returns true if the list or vector {{SEQUENCE}} is already sorted.
253
254==== topological-sort
255
256<procedure>(topological-sort DAG PRED)</procedure>
257
258Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex
259u to v, u will come before v in the resulting list of vertices.
260
261{{DAG}} is a list of sublists. The car of each sublist is a
262vertex. The cdr is the adjacency list of that vertex, i.e. a list of
263all vertices to which there exists an edge from the car vertex.
264{{pred}} is procedure of two arguments that should compare vertices
265for equality.
266
267Time complexity: O (|V| + |E|)
268
269<enscript highlight=scheme>
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=== Random numbers
286
287
288==== random-seed
289
290<procedure>(random-seed [SEED])</procedure>
291
292Seeds the random number generator with {{SEED}} (an exact integer) or
293{{(current-seconds)}} if {{SEED}} is not given.
294
295
296=== Strings
297
298
299==== conc
300
301<procedure>(conc X ...)</procedure>
302
303Returns a string with the string-represenation of all arguments concatenated
304together. {{conc}} could be implemented as
305
306<enscript highlight=scheme>
307(define (conc . args)
308  (apply string-append (map ->string args)) )
309</enscript>
310
311
312
313==== ->string
314
315<procedure>(->string X)</procedure>
316
317Returns a string-representation of {{X}}.
318
319
320==== string-chop
321
322<procedure>(string-chop STRING LENGTH)</procedure>
323
324Returns a list of substrings taken by ''chopping'' {{STRING}} every {{LENGTH}}
325characters:
326
327<enscript highlight=scheme>
328(string-chop "one two three" 4)  ==>  ("one " "two " "thre" "e")
329</enscript>
330
331
332
333==== string-chomp
334
335<procedure>(string-chomp STRING [SUFFIX])</procedure>
336
337If {{STRING}} ends with {{SUFFIX}}, then this procedure returns a copy of its first argument with the suffix
338removed, otherwise returns {{STRING}} unchanged. {{SUFFIX}} defaults to {{"\n"}}.
339
340
341==== string-compare3
342
343<procedure>(string-compare3 STRING1 STRING2)</procedure><br>
344<procedure>(string-compare3-ci STRING1 STRING2)</procedure>
345
346Perform a three-way comparison between the {{STRING1}} and {{STRING2}},
347returning either {{-1}} if {{STRING1}} is lexicographically less
348than {{STRING2}}, {{0}} if it is equal, or {{1}} if it s greater.
349{{string-compare3-ci}} performs a case-insensitive comparison.
350
351
352==== string-intersperse
353
354<procedure>(string-intersperse LIST [STRING])</procedure>
355
356Returns a string that contains all strings in {{LIST}} concatenated
357together.  {{STRING}} is placed between each concatenated string and
358defaults to {{" "}}.
359
360<enscript highlight=scheme>
361(string-intersperse '("one" "two") "three")
362</enscript>
363
364is equivalent to
365
366<enscript highlight=scheme>
367(apply string-append (intersperse '("one" "two") "three"))
368</enscript>
369
370
371==== string-split
372
373<procedure>(string-split STRING [DELIMITER-STRING [KEEPEMPTY]])</procedure>
374
375Split string into substrings delimited by any of the characters given in the delimiter string. If
376no delimiters are specified, a string comprising the tab, newline and space characters
377is assumed. If the
378parameter {{KEEPEMPTY}} is given and not {{#f}}, then empty
379substrings are retained:
380
381<enscript highlight=scheme>
382(string-split "one  two  three") ==> ("one" "two" "three")
383(string-split "foo:bar::baz:" ":" #t) ==> ("foo" "bar" "" "baz" "")
384(string-split "foo:bar:baz,quux,zot" ":," ) ==> ("foo" "bar" "baz" "quux" "zot")
385</enscript>
386
387
388==== string-translate
389
390<procedure>(string-translate STRING FROM [TO])</procedure>
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)</procedure>
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]]])</procedure><br>
421<procedure>(substring-ci=? STRING1 STRING2 [START1 [START2 [LENGTH]]])</procedure>
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])</procedure><br>
433<procedure>(substring-index-ci WHICH WHERE [START])</procedure>
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==== reverse-string-append
442
443<procedure>(reverse-string-append LIST)</procedure>
444
445{{(apply string-append (reverse LIST))}}
446
447
448=== Combinators
449
450
451==== any?
452
453<procedure>(any? X)</procedure>
454
455Ignores its argument and always returns {{#t}}. This is actually useful sometimes.
456
457
458==== constantly
459
460<procedure>(constantly X ...)</procedure>
461
462Returns a procedure that always returns the values {{X ...}} regardless of the number and value of its arguments.
463
464<enscript highlight=scheme>
465(constantly X) <=> (lambda args X)
466</enscript>
467
468
469==== complement
470
471<procedure>(complement PROC)</procedure>
472
473Returns a procedure that returns the boolean inverse of {{PROC}}.
474
475<enscript highlight=scheme>
476(complement PROC) <=> (lambda (x) (not (PROC x)))
477</enscript>
478
479
480==== compose
481
482<procedure>(compose PROC1 PROC2 ...)</procedure>
483
484Returns a procedure that represents the composition of the
485argument-procedures {{PROC1 PROC2 ...}}.
486
487<enscript highlight=scheme>
488(compose F G) <=> (lambda args
489                      (call-with-values
490                         (lambda () (apply G args))
491                         F))
492</enscript>
493
494{{(compose)}} is equivalent to {{values}}.
495
496
497==== conjoin
498
499<procedure>(conjoin PRED ...)</procedure>
500
501Returns a procedure that returns {{#t}} if its argument satisfies the
502predicates {{PRED ...}}.
503<enscript highlight=scheme>
504((conjoin odd? positive?) 33)   ==>  #t
505((conjoin odd? positive?) -33)  ==>  #f
506</enscript>
507
508
509==== disjoin
510
511<procedure>(disjoin PRED ...)</procedure>
512
513Returns a procedure that returns {{#t}} if its argument satisfies any
514predicate {{PRED ...}}.
515<enscript highlight=scheme>
516((disjoin odd? positive?) 32)    ==>  #t
517((disjoin odd? positive?) -32)   ==>  #f
518</enscript>
519
520
521==== each
522
523<procedure>(each PROC ...)</procedure>
524
525Returns a procedure that applies {{PROC ...}} to its arguments, and returns the result(s)
526of the last procedure application. For example
527
528<enscript highlight=scheme>
529(each pp eval)
530</enscript>
531
532is equivalent to
533
534<enscript highlight=scheme>
535(lambda args
536  (apply pp args)
537  (apply eval args) )
538</enscript>
539
540{{(each PROC)}} is equivalent to {{PROC}} and {{(each)}} is equivalent to
541{{void}}.
542
543
544==== flip
545
546<procedure>(flip PROC)</procedure>
547
548Returns a two-argument procedure that calls {{PROC}} with its
549arguments swapped:
550<enscript highlight=scheme>
551(flip PROC) <=> (lambda (x y) (PROC y x))
552</enscript>
553
554
555==== identity
556
557<procedure>(identity X)</procedure>
558
559Returns its sole argument {{X}}.
560
561
562==== list-of?
563
564<procedure>(list-of? PRED)</procedure>
565
566Returns a procedure of one argument that returns {{#t}} when
567applied to a list of elements that all satisfy the predicate procedure
568{{PRED}}, or {{#f}} otherwise.
569
570<enscript highlight=scheme>
571((list-of? even?) '(1 2 3))   ==> #f
572((list-of? number?) '(1 2 3)) ==> #t
573</enscript>
574
575
576==== o
577
578<procedure>(o PROC ...)</procedure>
579
580A single value version of {{compose}} (slightly faster). {{(o)}} is equivalent
581to {{identity}}.
582
583
584=== Binary searching
585
586
587==== binary-search
588
589<procedure>(binary-search SEQUENCE PROC)</procedure>
590
591Performs a binary search in {{SEQUENCE}}, which should be a sorted
592list or vector.  {{PROC}} is called to compare items in the sequence,
593should accept a single argument and return an exact integer: zero if the
594searched value is equal to the current item, negative if the searched
595value is ''less'' than the current item, and positive otherwise.
596Returns the index of the found value or {{#f}} otherwise.
597
598---
599Previous: [[Unit expand]]
600
601Next: [[Unit ports]]
Note: See TracBrowser for help on using the repository browser.