chickadee » arrays

TOC »

Functional arrays

Functional arrays are like vectors, insofar as they are mutable and allow fast access to items stored at a particular position. Fast here means O(log n).

Contrary to vectors functional arrays are unbounded, they can expand and shrink as needed. Adding and removing at the end, i.e. pruning, is cheap. Moreover, arrays can be typed: adding and updating items works only, if the item passes an item? predicate supplied with the constructor. If no such predicate is supplied, any? is assumed.

In this implementation, a functional array is internally represented by a procedure closed over a completely balanced tree which acts via message passing. To arrive at an index position simply devide the position argument recursively by 2 until it reaches 1 and inspect quotient and remainder: If the latter is zero, follow the left, otherwise the right subtree.

Besides the operations like item, update! add! and prune!, which operate on individual indexes we need operations, which operate on the array as a whole, like searching, copying or mapping. Of course, one could use the individual operations looping along the range of indexes. But this is slow, because if we had to go from index 365, say, to 366, we had to repeat the whole path in the local search tree except the last step. To avoid this we maintain a local cursor which allows to process the array by stepping successively along each tree level in the correct order.

Since access, adding and pruning is fast, arrays can ideally be used to implement sets. For example, to remove an item, simply swap! it to the end and prune! it. This doesn't work for arrays, since they are ordered by its indices, but it doesn't harm sets, which are unorderd.

Module structure

We'll separate the library into three modules. The first contains the actual closure, named array-handler, which does most of the dirty work.

The second is a record, which contains the array-handler as a field as well as two index positions, from (included) and upto (excluded) which allow fast subarray operations by simply sharing structure as in the pointer arithmetic of C-arrays. But note, that updating a subarray updates the original array as well. The same happens with the standard list procedure list-tail (but not with subvectors, which are freshly constructed).

The third is the set implementation, a record as well, containing the handler and an equality-predicate, from which an item-predicate can be deduced. There is no point to consider ranges, since sets are unordered. But equality is needed, otherwise we don't know, if an item is already in the set.

The module array-handlers

array-handlers

(array-handlers [sym]) procedure

documentation procedure.

array-handler?

(array-handler? xpr) procedure

type predicate.

make-array-handler

(make-array-handler [item?]) procedure

creates a new empty array-handler closure, which accepts items of type item?. If no item? is supplied, any? is used.

array-handler-repeat

(array-handler-repeat [item?] cnt item) procedure

stores item of type item? cnt times in a new empty array-handler closure. If no item? is supplied, any? is used.

array-handler-iterate

(array-handler-iterate [item?] cnt fn start) procedure

iterates function fn cnt times, starting with start of type item?, to make a new array-handler closure. If no item? is supplied, any? is used.

array-handler-iterate-while

(array-handler-iterate-while [item?] ok? fn start) procedure

iterates function fn, starting with start of type item?, as long as fn's result passes the ok? test, to make a new array-handler closure. If no item? is supplied, any? is used.

array-handler-iterate-until

(array-handler-iterate-until [item?] ok? fn start) procedure

iterates function fn, starting with start of type item?, as long as fn's result doesn't pass the ok? test, to make a new array-handler closure. If no item? is supplied, any? is used.

array-handler-messages

(array-handler-messages) procedure

returns the list of messages, accepted by the array-handler closure.

nary

(nary binop) procedure

helper procedure, which makes a binary operator nary.

nary?

(nary? bincmp?) procedure

helper procedure, which makes a binary comparison procedure nary.

assert*

(assert* loc . xprs) syntax

checks xprs in sequence in the procedure loc.

The module arrays

arrays

(arrays [sym]) procedure

documentation procedure.

array?

(array? xpr) procedure

type predicate.

array-null?

(array-null? xpr) procedure

checks, if xpr evaluates to an empty array.

make-array

(make-array [item?]) procedure

fundamental constructor. Returns an empty array with item type item? which defaults to any?

array

(array [item?] . args) procedure

The argument list args, which must be nonempty, is transformed to an arry.

list->array

(list->array [item?] lst) procedure

The argument list is transformed to a new arry. item? defaults to any?

vector->array

(vector->array [item?] vec) procedure

The argument vector is transformed to a new array. item? defaults to any?

array-repeat

(array-repeat [item?] cnt item) procedure

stores item cnt times in a new array. If no item? is supplied, any? is used.

array-iterate

(array-iterate [item?] cnt fn start) procedure

iterates function fn cnt times, starting with start of type item?, to make a new array. If no item? is supplied, any? is used.

array-iterate-while

(array-iterate-while [item?] ok? fn start) procedure

iterates function fn, starting with start of type item?, as long as fn's result passes the ok? test, to make a new array. If no item? is supplied, any? is used.

array-iterate-until

(array-iterate-until [item?] ok? fn start) procedure

iterates function fn, starting with start of type item?, as long as fn's result doesn't pass the ok? test, to make a new array. If no item? is supplied, any? is used.

array-copy

(array-copy arr) procedure

creates a fresh copy of its array argument.

array->list

(array->list arr) procedure

transforms its array argument to a list.

array->vector

(array->vector arr) procedure

transforms its array argument to a vector.

array-cursor-start!

(array-cursor-start! arr) procedure

begins a travere of its array argument. Positions the cursor to the left of the lowest index.

array-cursor-next!

(array-cursor-next! arr) procedure

continues a travere of its array argument. To access an item, at least one move after array-cursor-start! must have happened.

array-cursor-goto!

(array-cursor-goto! ok? arr) procedure

traverses the array util its cursor-item passes the ok? predicate.

array-cursor-finished?

(array-cursor-finished? arr) procedure

checks, if the cursor has reached the end of the traverse.

array-cursor-item

(array-cursor-item arr) procedure

returns the current item of the cursor.

array-cursor-index

(array-cursor-index arr) procedure

returns the current index of the cursor.

array-memp

(array-memp ok? arr) procedure

drops the first array items, which don't pass ok?. Returns #f if no item passes ok?

array-member

(array-member item arr) procedure

same as (array-memp (cut equal? <> item) arr)

array-memq

(array-memq item arr) procedure

same as (array-memp (cut eq? <> item) arr)

array-memv

(array-memv item arr) procedure

same as (array-memp (cut eqv? <> item) arr)

array-handler

(array-handler arr) procedure

returns the underlying array-handler of the array.

array-first

(array-first arr) procedure

returns the array item at index 0.

array-rest

(array-rest arr) procedure

drops the array item at index 0.

array-last

(array-last arr) procedure

returns the array item with highest index.

array-butlast

(array-butlast arr) procedure

takes all the array items except that with highest index.

array-add!

(array-add! item arr) procedure

adds an item after the highest index position.

array-update!

(array-update! index new arr) procedure

updates the item at index position with a new item.

array-prune!

(array-prune! arr) procedure

removes the item at the highest index position.

array-apply

(array-apply fn . args) procedure

applies procedure fn to args, which must be a nonempty list, whose last item is an array.

array-reverse

(array-reverse arr) procedure

creates a new array with items in reverse order.

array-reverse!

(array-reverse! arr) procedure

reverses the array destructively in place.

array-swap!

(array-swap! k l arr) procedure

exchanges the array items at positions k and l.

array-length

(array-length arr) procedure

the length of its argument array.

array-count

(array-count arr) procedure

the number of items stored in the array's handler.

array-range

(array-range from upto arr) procedure

returns the subarray starting at index from (included) upto index upto (excluded).

array-ref

(array-ref arr k) procedure

returns the item at index position k.

array-item

(array-item k arr) procedure

returns the item at index position k.

array-split-at

(array-split-at k arr) procedure

splits the array at index position k, returning two values.

array-split-with

(array-split-with ok? arr) procedure

splits the array at the first index position, whose item passes ok?, returning two values.

array-tail

(array-tail arr k) procedure

drops the first k items.

array-drop

(array-drop k arr) procedure

drops the first k items.

array-drop-while

(array-drop-while ok? arr) procedure

drops the first items as long as they pass ok?.

array-take

(array-take k arr) procedure

takes the first k items.

array-take-while

(array-take-while ok? arr) procedure

takes the first items as long as they pass ok?.

array-append

(array-append . arrs) procedure

creates a new array by appending all of its argument arrays, provided they all have the same item type.

array-append!

(array-append! . arrs) procedure

appends destructively the arrays of (cdr args) to (car args). All arrays must have the same item type.

array-map

(array-map [item?] fn . arrs) procedure

maps the array arguments to a new array with item? (or any? if not provided) by means of function fn. The length of the new array is the minimum of the lengthes of arrs.

array-mappend

(array-mappend fn . arrs) procedure

combination of map and append: The same as (array-apply array-append (apply array-map fn arrs))

array-for-each

(array-for-each proc . arrs) procedure

applies procedure proc to the array arguments, until the first array argument reaches its end.

array-filter

(array-filter ok? arr) procedure

filters the array argument with respect to the predicate ok? Returns two values, the array of those items, which passed the test, and the array of those which don't.

array-equ?

(array-equ? equ? . arrs) procedure

checks if the array arguments are equal, where the items are compared with equ?. Moreover all array arguments must be of the same length and have the same item type.

array-equal?

(array-equal? . arrs) procedure

the same as (array-equ? equal? . arrs)

array-eqv?

(array-eqv? . arrs) procedure

the same as (array-equ? eqv? . arrs)

array-eq?

(array-eq? . arrs) procedure

the same as (array-equ? eq? . arrs)

array-remp

(array-remp ok? arr) procedure

removes all items of arr which pass the ok? test. Second value of array-filter.

array-remove

(array-remove item arr) procedure

the same as (array-remp (cut equal? <> item) arr).

array-remq

(array-remq item arr) procedure

the same as (array-remp (cut eq? <> item) arr).

array-remv

(array-remv item arr) procedure

the same as (array-remp (cut eqv? <> item) arr).

array-remove-dups

(array-remove-dups equ? arr) procedure

removes all duplicates of arr according to comparison wiht equ?

array-fold-left

(array-fold-left op base . arrs) procedure

folds the arrays arrs from the left with op, starting at base.

array-fold-right

(array-fold-right op base . arrs) procedure

folds the arrays arrs from the right with op, starting at base.

array-sorted?

(array-sorted? <? arr) procedure

checks, if the array arr is sorted with respect to <?

array-sort!

(array-sort! <? arr) procedure

destructively sorts the array argument in place with a combination of insertion- and quick-sort.

array-zip

(array-zip arr0 arr1) procedure

combines two arrays to one, by taking items alternately from both. Both arrays must have equal item type.

array-unzip

(array-unzip arr) procedure

splits an array into two by populating its two array values alternately.

array-interpose

(array-interpose sep arr) procedure

creates a new array by separating the items of its array argument with the separator sep.

array-every?

(array-every? ok? arr) procedure

checks, if every item of arr passes the ok? test.

array-some?

(array-some? ok? arr) procedure

checks, if some item of arr passes the ok? test.

array-in?

(array-in? =? arr0 arr1) procedure

checks if arr0 a subrange of arr1.

array-bind

(array-bind (x ... . xs) arr xpr . xprs) syntax

This macro allows for general pattern matching of arrays. Binds x ... to the first items of arr and xs to the remaining subarray and executes the body xpr . xprs in this context. A more featurefull solution would be to use the bindings module:

(use bindings)
(bind-table-add! array?
                 array-length
                 (lambda (arr item) (array-item item arr))
                 (lambda (arr item) (array-drop item arr)))

Then you can use bind and friends and freely mix arrays with other sequence types.

The module array-sets

array-sets

(array-sets [sym]) procedure

documentation procedure.

set?

(set? xpr) procedure

type predicate.

set-null?

(set-null? xpr) procedure

checks, if xpr evaluates to an empty set.

make-set

(make-set [equ?]) procedure

creates a new empty set, whose items are compared with equ?, which defaults to eqv?

set-iterate

(set-iterate [equ?] n fn start) procedure

iterates function fn cnt times, starting with start to be compared with equ?, to make a new array. If no equ? is supplied, eqv? is used.

set-iterate-while

(set-iterate-while [equ?] ok? fn start) procedure

iterates function fn, starting with start to be compared with equ?, as long as fn's result passes the ok? test, to make a new array. If no equ? is supplied, eqv? is used.

set-iterate-until

(set-iterate-until [equ?] ok? fn start) procedure

iterates function fn, starting with start to be compared with equ?, as long as fn's result doesn't pass the ok? test, to make a new array. If no equ? is supplied, eqv? is used.

list->set

(list->set [equ?] lst) procedure

transforms a list into a set, whose items are compared with equ? If no equ? is supplied, eqv? is used.

vector->set

(vector->set [equ?] vec) procedure

transforms a vector into a set, whose items are compared with equ? If no equ? is supplied, eqv? is used.

set

(set [equ?] . args) procedure

creates a new set with items from args compared with equ?. If no equ? is supplied, eqv? is used.

set->list

(set->list st) procedure

transforms a set into a list.

set->vector

(set->vector st) procedure

transforms a set into a vector.

set-in

(set-in item st) procedure

checks, if item is in the set st; if so, returns its index, otherwise #f.

set<=

(set<= set0 set1) procedure

checks, if the set set0 contained in the set set1.

set=

(set= set0 set1) procedure

checks, if the sets set0 and set1 are equal, i.e. contain the same alements.

set>=

(set>= set0 set1) procedure

checks, if the set set0 contains the set set1.

set-filter

(set-filter ok? st) procedure

filters the set st with respect to the predicate ok? Returns two values, the set of those items, which passed the test, and the set of those which don't.

set-map

(set-map [equ?] fn . sets) procedure

maps the sets with respect to the function fn to a set, whose items are compared with equ? The cardinality of the result is the minimum of the cardinalities of the arguments. If no equ? is supplied, eqv? is used.

set-for-each

(set-for-each proc . sets) procedure

applies procedure proc to sets until the first argument is null.

set-add!

(set-add! item st) procedure

adds item to the set st.

set-remove!

(set-remove! item st) procedure

removes the item from the set st.

set-count

(set-count st) procedure

the cardinality of the set st.

set-copy

(set-copy st) procedure

creates a copy of the set st.

set-difference

(set-difference set0 set1) procedure

creates a new set by removing all items of set0, which are contained in set1. The comparison procedure of both sets must be the same.

set-union

(set-union . sets) procedure

creates a new set, which contains all items of all set arguments. The comparison procedure of all set arguments must be the same.

set-intersection

(set-intersection . sets) procedure

creates a new set, which contains only those items which are in all of its set arguments. The comparison procedure of all set arguments must be the same.

set-every?

(set-every? ok? st) procedure

checks, if every item of st passes the ok? test.

set-some?

(set-some? ok? st) procedure

checks, if some item of st passes the ok? test.

set-apply

(set-apply fn . args) procedure

applies procedure fn to the arguments args, which must be nonempty and whose last value is an array.

set-handler

(set-handler st) procedure

returns the handler closure of the set st.

set-equ?

(set-equ? st) procedure

returns the comparison-procedure of the set st.

set-item?

(set-item? st) procedure

returns the item? predicate of the set st, computed from its comparison procedure.

Usage of cursors

The metaphor for using cursors can in most cases be patterned after the following array-copy implementation:

(define (array-copy arr)
  (let ((result (make-array (array-item? arr))))
    (array-cursor-start! arr)
    (let loop ()
      (array-cursor-next! arr)
      (cond
        ((array-cursor-finished? arr)
         result)
        (else
          (array-add! (array-cursor-item arr) result)
          (loop))))))

Using the handler closure directly, the pattern looks like this:

(define (set-copy st)
  (let ((result (make-set (set-equ? st))))
    (if (set-null? st)
      result
      (let ((handler (set-handler st)))
        ((handler 'cursor-start!))
        (let loop ()
          ((handler 'cursor-next!))
          (cond
            (((handler 'cursor-finished?)) result)
            (else
              (set-add! (handler 'cursor-item) result)
              (loop))))))))

Note, that you mustn't use the array-handler closure in arrays directly, since the closure has no idea of fields from and upto. Those are added in the wrapper record.

Requirements

None

Last update

Jul 24, 2016

Author

Juergen Lorenz

License

Copyright (c) 2014-2016, Juergen Lorenz
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
Neither the name of the author nor the names of its contributors may be
used to endorse or promote products derived from this software without
specific prior written permission. 
  
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Version History

: 0.3 : array-ref and array-tail added

0.2
set module renamed to array-sets
0.1
initial import

Contents »