arrays

TOC »

Functional arrays
Last update
Author
Repository
License
Version History

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 divide 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 #!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-item

array-item k arrprocedure: returns the item at index position k.

array-at

array-at k arrprocedure: alias to array-item.

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-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:

(import bindings)
(bind-listify* array?
               (lambda (arr) (array-at 0 arr))
               (lambda (arr) (array-drop 1 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.

If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.

License

Copyright (c) 2014-2019, 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

1.0: port from chicken-4

chickadee » arrays

Identifier search

TOC »

Contents »