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

Last change on this file since 30603 was 30603, checked in by certainty, 7 years ago

updated documentation of topological-sort

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