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 #!optional symprocedure

documentation procedure.

array-handler?

array-handler? xprprocedure

type predicate.

make-array-handler

make-array-handler #!optional 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-messagesprocedure

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

nary

nary binopprocedure

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 #!optional symprocedure

documentation procedure.

array?

array? xprprocedure

type predicate.

array-null?

array-null? xprprocedure

checks, if xpr evaluates to an empty array.

make-array

make-array #!optional 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 arrprocedure

creates a fresh copy of its array argument.

array->list

array->list arrprocedure

transforms its array argument to a list.

array->vector

array->vector arrprocedure

transforms its array argument to a vector.

array-cursor-start!

array-cursor-start! arrprocedure

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

array-cursor-next!

array-cursor-next! arrprocedure

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? arrprocedure

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

array-cursor-finished?

array-cursor-finished? arrprocedure

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

array-cursor-item

array-cursor-item arrprocedure

returns the current item of the cursor.

array-cursor-index

array-cursor-index arrprocedure

returns the current index of the cursor.

array-memp

array-memp ok? arrprocedure

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

array-member

array-member item arrprocedure

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

array-memq

array-memq item arrprocedure

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

array-memv

array-memv item arrprocedure

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

array-handler

array-handler arrprocedure

returns the underlying array-handler of the array.

array-first

array-first arrprocedure

returns the array item at index 0.

array-rest

array-rest arrprocedure

drops the array item at index 0.

array-last

array-last arrprocedure

returns the array item with highest index.

array-butlast

array-butlast arrprocedure

takes all the array items except that with highest index.

array-add!

array-add! item arrprocedure

adds an item after the highest index position.

array-update!

array-update! index new arrprocedure

updates the item at index position with a new item.

array-prune!

array-prune! arrprocedure

removes the item at the highest index position.

array-apply

array-apply fn #!rest argsprocedure

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

array-reverse

array-reverse arrprocedure

creates a new array with items in reverse order.

array-reverse!

array-reverse! arrprocedure

reverses the array destructively in place.

array-swap!

array-swap! k l arrprocedure

exchanges the array items at positions k and l.

array-length

array-length arrprocedure

the length of its argument array.

array-count

array-count arrprocedure

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

array-range

array-range from upto arrprocedure

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

array-ref

array-ref arr kprocedure

returns the item at index position k.

array-item

array-item k arrprocedure

returns the item at index position k.

array-split-at

array-split-at k arrprocedure

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

array-split-with

array-split-with ok? arrprocedure

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

array-tail

array-tail arr kprocedure

drops the first k items.

array-drop

array-drop k arrprocedure

drops the first k items.

array-drop-while

array-drop-while ok? arrprocedure

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

array-take

array-take k arrprocedure

takes the first k items.

array-take-while

array-take-while ok? arrprocedure

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

array-append

array-append #!rest arrsprocedure

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

array-append!

array-append! #!rest arrsprocedure

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 #!rest arrsprocedure

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

array-for-each

array-for-each proc #!rest arrsprocedure

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

array-filter

array-filter ok? arrprocedure

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? #!rest arrsprocedure

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? #!rest arrsprocedure

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

array-eqv?

array-eqv? #!rest arrsprocedure

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

array-eq?

array-eq? #!rest arrsprocedure

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

array-remp

array-remp ok? arrprocedure

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

array-remove

array-remove item arrprocedure

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

array-remq

array-remq item arrprocedure

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

array-remv

array-remv item arrprocedure

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

array-remove-dups

array-remove-dups equ? arrprocedure

removes all duplicates of arr according to comparison wiht equ?

array-fold-left

array-fold-left op base #!rest arrsprocedure

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

array-fold-right

array-fold-right op base #!rest arrsprocedure

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

array-sorted?

array-sorted? <? arrprocedure

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

array-sort!

array-sort! <? arrprocedure

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

array-zip

array-zip arr0 arr1procedure

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

array-unzip

array-unzip arrprocedure

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

array-interpose

array-interpose sep arrprocedure

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

array-every?

array-every? ok? arrprocedure

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

array-some?

array-some? ok? arrprocedure

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

array-in?

array-in? =? arr0 arr1procedure

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 #!optional symprocedure

documentation procedure.

set?

set? xprprocedure

type predicate.

set-null?

set-null? xprprocedure

checks, if xpr evaluates to an empty set.

make-set

make-set #!optional 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 stprocedure

transforms a set into a list.

set->vector

set->vector stprocedure

transforms a set into a vector.

set-in

set-in item stprocedure

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

set<=

set<= set0 set1procedure

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

set=

set= set0 set1procedure

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

set>=

set>= set0 set1procedure

checks, if the set set0 contains the set set1.

set-filter

set-filter ok? stprocedure

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 #!rest setsprocedure

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

set-add!

set-add! item stprocedure

adds item to the set st.

set-remove!

set-remove! item stprocedure

removes the item from the set st.

set-count

set-count stprocedure

the cardinality of the set st.

set-copy

set-copy stprocedure

creates a copy of the set st.

set-difference

set-difference set0 set1procedure

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 #!rest setsprocedure

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 #!rest setsprocedure

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? stprocedure

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

set-some?

set-some? ok? stprocedure

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

set-apply

set-apply fn #!rest argsprocedure

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

set-handler

set-handler stprocedure

returns the handler closure of the set st.

set-equ?

set-equ? stprocedure

returns the comparison-procedure of the set st.

set-item?

set-item? stprocedure

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 »