source: project/wiki/eggref/5/arrays @ 37415

Last change on this file since 37415 was 37415, checked in by juergen, 17 months ago

arrays 1.0 docu

File size: 21.6 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4
5== Functional arrays
6
7Functional arrays are like vectors, insofar as they are mutable and
8allow fast access to items stored at a particular position. Fast
9here means O(log n).
10
11Contrary to vectors functional arrays are unbounded, they can expand
12and shrink as needed. Adding and removing at the end, i.e. pruning,
13is cheap.  Moreover, arrays can be typed: adding and updating items
14works only, if the item passes an item? predicate supplied with the
15constructor. If no such predicate is supplied, any? is assumed.
16
17In this implementation, a functional array is internally represented
18by a procedure closed over a completely balanced tree which acts via
19message passing.  To arrive at an index position simply devide the
20position argument recursively by 2 until it reaches 1 and inspect
21quotient and remainder: If the latter is zero, follow the left,
22otherwise the right subtree.
23
24Besides the operations like item, update! add! and prune!, which operate
25on individual indexes we need operations, which operate on the array
26as a whole, like searching, copying or mapping. Of course, one could
27use the individual operations looping along the range of indexes.
28But this is slow, because if we had to go from index 365, say, to
29366, we had to repeat the whole path in the local search tree except
30the last step.  To avoid this we maintain a local cursor which
31allows to process the array by stepping successively along each tree
32level in the correct order.
33
34Since access, adding and pruning is fast, arrays can ideally be
35used to implement sets. For example, to remove an item, simply swap!
36it to the end and prune! it. This doesn't work for arrays, since
37they are ordered by its indices, but it doesn't harm sets, which are
38unorderd.
39
40=== Module structure
41
42We'll separate the library into three modules. The first contains the
43actual closure, named array-handler, which does most of the dirty work.
44
45The second is a record, which contains the array-handler as a field
46as well as two index positions, from (included) and upto (excluded)
47which allow fast subarray operations by simply sharing structure
48as in the pointer arithmetic of C-arrays. But note, that updating a
49subarray updates the original array as well. The same happens with
50the standard list procedure list-tail (but not with subvectors,
51which are freshly constructed).
52
53The third is the set implementation, a record as well, containing
54the handler and an equality-predicate, from which an item-predicate
55can be deduced. There is no point to consider ranges, since sets are
56unordered. But equality is needed, otherwise we don't know, if an item
57is already in the set.
58
59=== The module array-handlers
60
61==== array-handlers
62<procedure>(array-handlers [sym])</procedure>
63documentation procedure.
64
65==== array-handler?
66<procedure>(array-handler? xpr)</procedure>
67type predicate.
68
69==== make-array-handler
70<procedure>(make-array-handler [item?])</procedure>
71creates a new empty array-handler closure, which accepts items of type item?.
72If no item? is supplied, any? is used.
73
74==== array-handler-repeat
75<procedure>(array-handler-repeat [item?] cnt item)</procedure>
76stores item of type item? cnt times in a new empty array-handler closure.
77If no item? is supplied, any? is used.
78
79==== array-handler-iterate
80<procedure>(array-handler-iterate [item?] cnt fn start)</procedure>
81iterates function fn cnt times, starting with start of type item?,
82to make a new array-handler closure.
83If no item? is supplied, any? is used.
84
85==== array-handler-iterate-while
86<procedure>(array-handler-iterate-while [item?] ok? fn start)</procedure>
87iterates function fn, starting with start of type item?, as long as fn's
88result passes the ok? test, to make a new array-handler closure.
89If no item? is supplied, any? is used.
90
91==== array-handler-iterate-until
92<procedure>(array-handler-iterate-until [item?] ok? fn start)</procedure>
93iterates function fn, starting with start of type item?, as long as fn's
94result doesn't pass the ok? test, to make a new array-handler closure.
95If no item? is supplied, any? is used.
96
97==== array-handler-messages
98<procedure>(array-handler-messages)</procedure>
99returns the list of messages, accepted by the array-handler closure.
100
101==== nary
102<procedure>(nary binop)</procedure>
103helper procedure, which makes a binary operator nary.
104
105==== nary?
106<procedure>(nary? bincmp?)</procedure>
107helper procedure, which makes a binary comparison procedure nary.
108
109==== assert*
110<macro>(assert* loc . xprs)</macro>
111checks xprs in sequence in the procedure loc.
112
113=== The module arrays
114
115==== arrays
116<procedure>(arrays [sym])</procedure>
117documentation procedure.
118
119==== array?
120<procedure>(array? xpr)</procedure>
121type predicate.
122
123==== array-null?
124<procedure>(array-null? xpr)</procedure>
125checks, if xpr evaluates to an empty array.
126
127==== make-array
128<procedure>(make-array [item?])</procedure>
129fundamental constructor. Returns an empty array with item type item?
130which defaults to any?
131
132==== array
133<procedure>(array [item?] . args)</procedure>
134The argument list args, which must be nonempty, is transformed to an arry.
135
136==== list->array
137<procedure>(list->array [item?] lst)</procedure>
138The argument list is transformed to a new arry.
139item? defaults to any?
140
141==== vector->array
142<procedure>(vector->array [item?] vec)</procedure>
143The argument vector is transformed to a new array.
144item? defaults to any?
145
146==== array-repeat
147<procedure>(array-repeat [item?] cnt item)</procedure>
148stores item cnt times in a new array.
149If no item? is supplied, any? is used.
150
151==== array-iterate
152<procedure>(array-iterate [item?] cnt fn start)</procedure>
153iterates function fn cnt times, starting with start of type item?,
154to make a new array.
155If no item? is supplied, any? is used.
156
157==== array-iterate-while
158<procedure>(array-iterate-while [item?] ok? fn start)</procedure>
159iterates function fn, starting with start of type item?, as long as fn's
160result passes the ok? test, to make a new array.
161If no item? is supplied, any? is used.
162
163==== array-iterate-until
164<procedure>(array-iterate-until [item?] ok? fn start)</procedure>
165iterates function fn, starting with start of type item?, as long as fn's
166result doesn't pass the ok? test, to make a new array.
167If no item? is supplied, any? is used.
168
169==== array-copy
170<procedure>(array-copy arr)</procedure>
171creates a fresh copy of its array argument.
172
173==== array->list
174<procedure>(array->list arr)</procedure>
175transforms its array argument to a list.
176
177==== array->vector
178<procedure>(array->vector arr)</procedure>
179transforms its array argument to a vector.
180
181==== array-cursor-start!
182<procedure>(array-cursor-start! arr)</procedure>
183begins a travere of its array argument.
184Positions the cursor to the left of the lowest index.
185
186==== array-cursor-next!
187<procedure>(array-cursor-next! arr)</procedure>
188continues a travere of its array argument.
189To access an item, at least one move after array-cursor-start! must have
190happened.
191
192==== array-cursor-goto!
193<procedure>(array-cursor-goto! ok? arr)</procedure>
194traverses the array util its cursor-item passes the ok? predicate.
195
196==== array-cursor-finished?
197<procedure>(array-cursor-finished? arr)</procedure>
198checks, if the cursor has reached the end of the traverse.
199
200==== array-cursor-item
201<procedure>(array-cursor-item arr)</procedure>
202returns the current item of the cursor.
203
204==== array-cursor-index
205<procedure>(array-cursor-index arr)</procedure>
206returns the current index of the cursor.
207
208==== array-memp
209<procedure>(array-memp ok? arr)</procedure>
210drops the first array items, which don't pass ok?.
211Returns #f if no item passes ok?
212
213==== array-member
214<procedure>(array-member item arr)</procedure>
215same as (array-memp (cut equal? <> item) arr)
216
217==== array-memq
218<procedure>(array-memq item arr)</procedure>
219same as (array-memp (cut eq? <> item) arr)
220
221==== array-memv
222<procedure>(array-memv item arr)</procedure>
223same as (array-memp (cut eqv? <> item) arr)
224
225==== array-handler
226<procedure>(array-handler arr)</procedure>
227returns the underlying array-handler of the array.
228
229==== array-first
230<procedure>(array-first arr)</procedure>
231returns the array item at index 0.
232
233==== array-rest
234<procedure>(array-rest arr)</procedure>
235drops the array item at index 0.
236
237==== array-last
238<procedure>(array-last arr)</procedure>
239returns the array item with highest index.
240
241==== array-butlast
242<procedure>(array-butlast arr)</procedure>
243takes all the array items except that with highest index.
244
245==== array-add!
246<procedure>(array-add! item arr)</procedure>
247adds an item after the highest index position.
248
249==== array-update!
250<procedure>(array-update! index new arr)</procedure>
251updates the item at index position with a new item.
252
253==== array-prune!
254<procedure>(array-prune! arr)</procedure>
255removes the item at the highest index position.
256
257==== array-apply
258<procedure>(array-apply fn . args)</procedure>
259applies procedure fn to args, which must be a nonempty list, whose last
260item is an array.
261
262==== array-reverse
263<procedure>(array-reverse arr)</procedure>
264creates a new array with items in reverse order.
265
266==== array-reverse!
267<procedure>(array-reverse! arr)</procedure>
268reverses the array destructively in place.
269
270==== array-swap!
271<procedure>(array-swap! k l arr)</procedure>
272exchanges the array items at positions k and l.
273
274==== array-length
275<procedure>(array-length arr)</procedure>
276the length of its argument array.
277
278==== array-count
279<procedure>(array-count arr)</procedure>
280the number of items stored in the array's handler.
281
282==== array-range
283<procedure>(array-range from upto arr)</procedure>
284returns the subarray starting at index from (included) upto index upto
285(excluded).
286
287==== array-item
288<procedure>(array-item k arr)</procedure>
289returns the item at index position k.
290
291==== array-at
292<procedure>(array-at k arr)</procedure>
293alias to array-item.
294
295==== array-split-at
296<procedure>(array-split-at k arr)</procedure>
297splits the array at index position k, returning two values.
298
299==== array-split-with
300<procedure>(array-split-with ok? arr)</procedure>
301splits the array at the first index position, whose item passes ok?, returning two values.
302
303==== array-drop
304<procedure>(array-drop k arr)</procedure>
305drops the first k items.
306
307==== array-drop-while
308<procedure>(array-drop-while ok? arr)</procedure>
309drops the first items as long as they pass ok?.
310
311==== array-take
312<procedure>(array-take k arr)</procedure>
313takes the first k items.
314
315==== array-take-while
316<procedure>(array-take-while ok? arr)</procedure>
317takes the first items as long as they pass ok?.
318
319==== array-append
320<procedure>(array-append . arrs)</procedure>
321creates a new array by appending all of its argument arrays, provided
322they all have the same item type.
323
324==== array-append!
325<procedure>(array-append! . arrs)</procedure>
326appends destructively the arrays of (cdr args) to (car args).
327All arrays must have the same item type.
328
329==== array-map
330<procedure>(array-map [item?] fn . arrs)</procedure>
331maps the array arguments to a new array with item? (or any? if not
332provided) by means of function fn. The length of the new array is the
333minimum of the lengthes of arrs.
334
335==== array-mappend
336<procedure>(array-mappend fn . arrs)</procedure>
337combination of map and append:
338The same as (array-apply array-append (apply array-map fn arrs))
339
340==== array-for-each
341<procedure>(array-for-each proc . arrs)</procedure>
342applies procedure proc to the array arguments, until the first array
343argument reaches its end.
344
345==== array-filter
346<procedure>(array-filter ok? arr)</procedure>
347filters the array argument with respect to the predicate ok?
348Returns two values, the array of those items, which passed the test, and
349the array of those which don't.
350
351==== array-equ?
352<procedure>(array-equ? equ? . arrs)</procedure>
353checks if the array arguments are equal, where the items are compared
354with equ?. Moreover all array arguments must be of the same length and
355have the same item type.
356
357==== array-equal?
358<procedure>(array-equal? . arrs)</procedure>
359the same as (array-equ? equal? . arrs)
360
361==== array-eqv?
362<procedure>(array-eqv? . arrs)</procedure>
363the same as (array-equ? eqv? . arrs)
364
365==== array-eq?
366<procedure>(array-eq? . arrs)</procedure>
367the same as (array-equ? eq? . arrs)
368
369==== array-remp
370<procedure>(array-remp ok? arr)</procedure>
371removes all items of arr which pass the ok? test.
372Second value of array-filter.
373
374==== array-remove
375<procedure>(array-remove item arr)</procedure>
376the same as (array-remp (cut equal? <> item) arr).
377
378==== array-remq
379<procedure>(array-remq item arr)</procedure>
380the same as (array-remp (cut eq? <> item) arr).
381
382==== array-remv
383<procedure>(array-remv item arr)</procedure>
384the same as (array-remp (cut eqv? <> item) arr).
385
386==== array-remove-dups
387<procedure>(array-remove-dups equ? arr)</procedure>
388removes all duplicates of arr according to comparison wiht equ?
389
390==== array-fold-left
391<procedure>(array-fold-left op base . arrs)</procedure>
392folds the arrays arrs from the left with op, starting at base.
393
394==== array-fold-right
395<procedure>(array-fold-right op base . arrs)</procedure>
396folds the arrays arrs from the right with op, starting at base.
397
398==== array-sorted?
399<procedure>(array-sorted? <? arr)</procedure>
400checks, if the array arr is sorted with respect to <?
401
402==== array-sort!
403<procedure>(array-sort! <? arr)</procedure>
404destructively sorts the array argument in place with a combination of
405insertion- and quick-sort.
406
407==== array-zip
408<procedure>(array-zip arr0 arr1)</procedure>
409combines two arrays to one, by taking items alternately from both.
410Both arrays must have equal item type.
411
412==== array-unzip
413<procedure>(array-unzip arr)</procedure>
414splits an array into two by populating its two array values alternately.
415
416==== array-interpose
417<procedure>(array-interpose sep arr)</procedure>
418creates a new array by separating the items of its array argument with
419the separator sep.
420
421==== array-every?
422<procedure>(array-every? ok? arr)</procedure>
423checks, if every item of arr passes the ok? test.
424
425==== array-some?
426<procedure>(array-some? ok? arr)</procedure>
427checks, if some item of arr passes the ok? test.
428
429==== array-in?
430<procedure>(array-in? =? arr0 arr1)</procedure>
431checks if arr0 a subrange of arr1.
432
433==== array-bind
434<macro>(array-bind (x ... . xs) arr xpr . xprs)</macro>
435This macro allows for general pattern matching of arrays.
436Binds x ... to the first items of arr and xs to the remaining subarray
437and executes the body xpr . xprs in this context.
438
439A more featurefull solution would be to use the bindings module:
440
441<enscript highlight=scheme>
442(import bindings)
443(bind-seq-db array?
444             (lambda (arr item) (array-item item arr))
445             (lambda (arr item) (array-drop item arr)))
446</enscript>
447
448Then you can use bind and friends and freely mix arrays with other
449sequence types.
450
451
452=== The module array-sets
453
454==== array-sets
455<procedure>(array-sets [sym])</procedure>
456documentation procedure.
457
458==== set?
459<procedure>(set? xpr)</procedure>
460type predicate.
461
462==== set-null?
463<procedure>(set-null? xpr)</procedure>
464checks, if xpr evaluates to an empty set.
465
466==== make-set
467<procedure>(make-set [equ?])</procedure>
468creates a new empty set, whose items are compared with equ?, which
469defaults to eqv?
470
471==== set-iterate
472<procedure>(set-iterate [equ?] n fn start)</procedure>
473iterates function fn cnt times, starting with start to be compared with equ?,
474to make a new array.
475If no equ? is supplied, eqv? is used.
476
477==== set-iterate-while
478<procedure>(set-iterate-while [equ?] ok? fn start)</procedure>
479iterates function fn, starting with start to be compared with equ?,
480as long as fn's result passes the ok? test, to make a new array.
481If no equ? is supplied, eqv? is used.
482
483==== set-iterate-until
484<procedure>(set-iterate-until [equ?] ok? fn start)</procedure>
485iterates function fn, starting with start to be compared with
486equ?, as long as fn's result doesn't pass the ok? test, to make a new array.
487If no equ? is supplied, eqv? is used.
488
489==== list->set
490<procedure>(list->set [equ?] lst)</procedure>
491transforms a list into a set, whose items are compared with equ?
492If no equ? is supplied, eqv? is used.
493
494==== vector->set
495<procedure>(vector->set [equ?] vec)</procedure>
496transforms a vector into a set, whose items are compared with equ?
497If no equ? is supplied, eqv? is used.
498
499==== set
500<procedure>(set [equ?] . args)</procedure>
501creates a new set with items from args compared with equ?.
502If no equ? is supplied, eqv? is used.
503
504==== set->list
505<procedure>(set->list st)</procedure>
506transforms a set into a list.
507
508==== set->vector
509<procedure>(set->vector st)</procedure>
510transforms a set into a vector.
511
512==== set-in
513<procedure>(set-in item st)</procedure>
514checks, if item is in the set st; if so, returns its index, otherwise #f.
515
516==== set<=
517<procedure>(set<= set0 set1)</procedure>
518checks, if the set set0 contained in the set set1.
519
520==== set=
521<procedure>(set= set0 set1)</procedure>
522checks, if the sets set0 and set1 are equal, i.e. contain the same
523alements.
524
525==== set>=
526<procedure>(set>= set0 set1)</procedure>
527checks, if the set set0 contains the set set1.
528
529==== set-filter
530<procedure>(set-filter ok? st)</procedure>
531filters the set st with respect to the predicate ok?
532Returns two values, the set of those items, which passed the test, and
533the set of those which don't.
534
535==== set-map
536<procedure>(set-map [equ?] fn . sets)</procedure>
537maps the sets with respect to the function fn to a set, whose items are
538compared with equ?
539The cardinality of the result is the minimum of the cardinalities of the
540arguments.
541If no equ? is supplied, eqv? is used.
542
543==== set-for-each
544<procedure>(set-for-each proc . sets)</procedure>
545applies procedure proc to sets until the first argument is null.
546
547==== set-add!
548<procedure>(set-add! item st)</procedure>
549adds item to the set st.
550
551==== set-remove!
552<procedure>(set-remove! item st)</procedure>
553removes the item from the set st.
554
555==== set-count
556<procedure>(set-count st)</procedure>
557the cardinality of the set st.
558
559==== set-copy
560<procedure>(set-copy st)</procedure>
561creates a copy of the set st.
562
563==== set-difference
564<procedure>(set-difference set0 set1)</procedure>
565creates a new set by removing all items of set0, which are contained in
566set1.
567The comparison procedure of both sets must be the same.
568
569==== set-union
570<procedure>(set-union . sets)</procedure>
571creates a new set, which contains all items of all set arguments.
572The comparison procedure of all set arguments must be the same.
573
574==== set-intersection
575<procedure>(set-intersection . sets)</procedure>
576creates a new set, which contains only those items which are in all of its set arguments.
577The comparison procedure of all set arguments must be the same.
578
579==== set-every?
580<procedure>(set-every? ok? st)</procedure>
581checks, if every item of st passes the ok? test.
582
583==== set-some?
584<procedure>(set-some? ok? st)</procedure>
585checks, if some item of st passes the ok? test.
586
587==== set-apply
588<procedure>(set-apply fn . args)</procedure>
589applies procedure fn to the arguments args, which must be nonempty and
590whose last value is an array.
591
592==== set-handler
593<procedure>(set-handler st)</procedure>
594returns the handler closure of the set st.
595
596==== set-equ?
597<procedure>(set-equ? st)</procedure>
598returns the comparison-procedure of the set st.
599
600==== set-item?
601<procedure>(set-item? st)</procedure>
602returns the item? predicate of the set st, computed from its comparison
603procedure.
604
605=== Usage of cursors
606
607The metaphor for using cursors can in most cases be patterned after the
608following array-copy implementation:
609
610<enscript highlight=scheme>
611(define (array-copy arr)
612  (let ((result (make-array (array-item? arr))))
613    (array-cursor-start! arr)
614    (let loop ()
615      (array-cursor-next! arr)
616      (cond
617        ((array-cursor-finished? arr)
618         result)
619        (else
620          (array-add! (array-cursor-item arr) result)
621          (loop))))))
622</enscript>
623
624Using the handler closure directly, the pattern looks like this:
625
626<enscript highlight=scheme>
627(define (set-copy st)
628  (let ((result (make-set (set-equ? st))))
629    (if (set-null? st)
630      result
631      (let ((handler (set-handler st)))
632        ((handler 'cursor-start!))
633        (let loop ()
634          ((handler 'cursor-next!))
635          (cond
636            (((handler 'cursor-finished?)) result)
637            (else
638              (set-add! (handler 'cursor-item) result)
639              (loop))))))))
640</enscript>
641
642Note, that you mustn't use the array-handler closure in arrays directly,
643since the closure has no idea of fields from and upto. Those are added
644in the wrapper record.
645
646=== Requirements
647
648None
649
650== Last update
651
652Mar 18, 2019
653
654== Author
655
656[[/users/juergen-lorenz|Juergen Lorenz]]
657
658== License
659
660 Copyright (c) 2014-2019, Juergen Lorenz
661 All rights reserved.
662
663 Redistribution and use in source and binary forms, with or without
664 modification, are permitted provided that the following conditions are
665 met:
666 
667 Redistributions of source code must retain the above copyright
668 notice, this list of conditions and the following disclaimer.
669 
670 Redistributions in binary form must reproduce the above copyright
671 notice, this list of conditions and the following disclaimer in the
672 documentation and/or other materials provided with the distribution.
673 Neither the name of the author nor the names of its contributors may be
674 used to endorse or promote products derived from this software without
675 specific prior written permission.
676   
677 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
678 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
679 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
680 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
681 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
682 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
683 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
684 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
685 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
686 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
687 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
688
689== Version History
690
691; 1.0 : port from chicken-4
692
693
Note: See TracBrowser for help on using the repository browser.