Functional arrays

Functional arrays
Last update
Author
Repository
License
Version History

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

[procedure] (array-handlers [sym])

documentation procedure.

array-handler?

[procedure] (array-handler? xpr)

type predicate.

make-array-handler

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

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

array-handler-repeat

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

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

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

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

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

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

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

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

[procedure] (array-handler-messages)

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

nary

[procedure] (nary binop)

helper procedure, which makes a binary operator nary.

nary?

[procedure] (nary? bincmp?)

helper procedure, which makes a binary comparison procedure nary.

assert*

[syntax] (assert* loc . xprs)

checks xprs in sequence in the procedure loc.

The module arrays

arrays

[procedure] (arrays [sym])

documentation procedure.

array?

[procedure] (array? xpr)

type predicate.

array-null?

[procedure] (array-null? xpr)

checks, if xpr evaluates to an empty array.

make-array

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

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

array

[procedure] (array [item?] . args)

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

list->array

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

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

vector->array

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

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

array-repeat

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

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

array-iterate

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

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

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

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

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

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

[procedure] (array-copy arr)

creates a fresh copy of its array argument.

array->list

[procedure] (array->list arr)

transforms its array argument to a list.

array->vector

[procedure] (array->vector arr)

transforms its array argument to a vector.

array-cursor-start!

[procedure] (array-cursor-start! arr)

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

array-cursor-next!

[procedure] (array-cursor-next! arr)

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!

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

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

array-cursor-finished?

[procedure] (array-cursor-finished? arr)

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

array-cursor-item

[procedure] (array-cursor-item arr)

returns the current item of the cursor.

array-cursor-index

[procedure] (array-cursor-index arr)

returns the current index of the cursor.

array-memp

[procedure] (array-memp ok? arr)

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

array-member

[procedure] (array-member item arr)

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

array-memq

[procedure] (array-memq item arr)

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

array-memv

[procedure] (array-memv item arr)

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

array-handler

[procedure] (array-handler arr)

returns the underlying array-handler of the array.

array-first

[procedure] (array-first arr)

returns the array item at index 0.

array-rest

[procedure] (array-rest arr)

drops the array item at index 0.

array-last

[procedure] (array-last arr)

returns the array item with highest index.

array-butlast

[procedure] (array-butlast arr)

takes all the array items except that with highest index.

array-add!

[procedure] (array-add! item arr)

adds an item after the highest index position.

array-update!

[procedure] (array-update! index new arr)

updates the item at index position with a new item.

array-prune!

[procedure] (array-prune! arr)

removes the item at the highest index position.

array-apply

[procedure] (array-apply fn . args)

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

array-reverse

[procedure] (array-reverse arr)

creates a new array with items in reverse order.

array-reverse!

[procedure] (array-reverse! arr)

reverses the array destructively in place.

array-swap!

[procedure] (array-swap! k l arr)

exchanges the array items at positions k and l.

array-length

[procedure] (array-length arr)

the length of its argument array.

array-count

[procedure] (array-count arr)

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

array-range

[procedure] (array-range from upto arr)

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

array-item

[procedure] (array-item k arr)

returns the item at index position k.

array-at

[procedure] (array-at k arr)

alias to array-item.

array-split-at

[procedure] (array-split-at k arr)

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

array-split-with

[procedure] (array-split-with ok? arr)

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

array-drop

[procedure] (array-drop k arr)

drops the first k items.

array-drop-while

[procedure] (array-drop-while ok? arr)

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

array-take

[procedure] (array-take k arr)

takes the first k items.

array-take-while

[procedure] (array-take-while ok? arr)

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

array-append

[procedure] (array-append . arrs)

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

array-append!

[procedure] (array-append! . arrs)

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

array-map

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

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

[procedure] (array-mappend fn . arrs)

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

array-for-each

[procedure] (array-for-each proc . arrs)

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

array-filter

[procedure] (array-filter ok? arr)

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?

[procedure] (array-equ? equ? . arrs)

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?

[procedure] (array-equal? . arrs)

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

array-eqv?

[procedure] (array-eqv? . arrs)

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

array-eq?

[procedure] (array-eq? . arrs)

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

array-remp

[procedure] (array-remp ok? arr)

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

array-remove

[procedure] (array-remove item arr)

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

array-remq

[procedure] (array-remq item arr)

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

array-remv

[procedure] (array-remv item arr)

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

array-remove-dups

[procedure] (array-remove-dups equ? arr)

removes all duplicates of arr according to comparison wiht equ?

array-fold-left

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

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

array-fold-right

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

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

array-sorted?

[procedure] (array-sorted? <? arr)

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

array-sort!

[procedure] (array-sort! <? arr)

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

array-zip

[procedure] (array-zip arr0 arr1)

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

array-unzip

[procedure] (array-unzip arr)

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

array-interpose

[procedure] (array-interpose sep arr)

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

array-every?

[procedure] (array-every? ok? arr)

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

array-some?

[procedure] (array-some? ok? arr)

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

array-in?

[procedure] (array-in? =? arr0 arr1)

checks if arr0 a subrange of arr1.

array-bind

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

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

[procedure] (array-sets [sym])

documentation procedure.

set?

[procedure] (set? xpr)

type predicate.

set-null?

[procedure] (set-null? xpr)

checks, if xpr evaluates to an empty set.

make-set

[procedure] (make-set [equ?])

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

set-iterate

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

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

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

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

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

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

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

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

vector->set

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

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

set

[procedure] (set [equ?] . args)

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

set->list

[procedure] (set->list st)

transforms a set into a list.

set->vector

[procedure] (set->vector st)

transforms a set into a vector.

set-in

[procedure] (set-in item st)

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

set<=

[procedure] (set<= set0 set1)

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

set=

[procedure] (set= set0 set1)

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

set>=

[procedure] (set>= set0 set1)

checks, if the set set0 contains the set set1.

set-filter

[procedure] (set-filter ok? st)

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

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

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

[procedure] (set-for-each proc . sets)

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

set-add!

[procedure] (set-add! item st)

adds item to the set st.

set-remove!

[procedure] (set-remove! item st)

removes the item from the set st.

set-count

[procedure] (set-count st)

the cardinality of the set st.

set-copy

[procedure] (set-copy st)

creates a copy of the set st.

set-difference

[procedure] (set-difference set0 set1)

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

[procedure] (set-union . sets)

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

[procedure] (set-intersection . sets)

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?

[procedure] (set-every? ok? st)

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

set-some?

[procedure] (set-some? ok? st)

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

set-apply

[procedure] (set-apply fn . args)

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

set-handler

[procedure] (set-handler st)

returns the handler closure of the set st.

set-equ?

[procedure] (set-equ? st)

returns the comparison-procedure of the set st.

set-item?

[procedure] (set-item? st)

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