Compound Data Types
===================

This chapter describes Guile's compound data types.  By compound we mean that the primary purpose of these data types is to act as containers for other kinds of data (including other compound objects). For instance, a (non-uniform) vector with length 5 is a container that can hold five arbitrary Scheme objects.

The various kinds of container object differ from each other in how their memory is allocated, how they are indexed, and how particular values can be looked up within them.

Pairs
-----

Pairs are used to combine two Scheme objects into one compound object. Hence the name: A pair stores a pair of objects.

The data type pair is extremely important in Scheme, just like in any other Lisp dialect.  The reason is that pairs are not only used to make two values available as one object, but that pairs are used for constructing lists of values.  Because lists are so important in Scheme, they are described in a section of their own (see Lists).

Pairs can literally get entered in source code or at the REPL, in the so-called dotted list syntax.  This syntax consists of an opening parentheses, the first element of the pair, a dot, the second element and a closing parentheses.  The following example shows how a pair consisting of the two numbers 1 and 2, and a pair containing the symbols foo and bar can be entered.  It is very important to write the whitespace before and after the dot, because otherwise the Scheme parser would not be able to figure out where to split the tokens.

     (1 . 2)
     (foo . bar)

But beware, if you want to try out these examples, you have to quote the expressions.  More information about quotation is available in the section (REFFIXME).  The correct way to try these examples is as follows.

     '(1 . 2)
     =>
     (1 . 2)
     '(foo . bar)
     =>
     (foo . bar)

A new pair is made by calling the procedure cons with two arguments.  Then the argument values are stored into a newly allocated pair, and the pair is returned.  The name cons stands for "construct".  Use the procedure pair? to test whether a given Scheme object is a pair or not.

 -- Scheme Procedure: cons x y
 -- C Function: scm_cons (x, y)
     Return a newly allocated pair whose car is X and whose cdr is Y.  The pair is guaranteed to be different (in the sense of eq?) from every previously existing object.

 -- Scheme Procedure: pair? x
 -- C Function: scm_pair_p (x)
     Return #t if X is a pair; otherwise return #f.

 -- C Function: int scm_is_pair (SCM x)
     Return 1 when X is a pair; otherwise return 0.

The two parts of a pair are traditionally called car and cdr.  They can be retrieved with procedures of the same name (car and cdr), and can be modified with the procedures set-car! and set-cdr!.  Since a very common operation in Scheme programs is to access the car of a pair, or the car of the cdr of a pair, etc., the procedures called caar, cadr and so on are also predefined.

 -- Scheme Procedure: car pair
 -- Scheme Procedure: cdr pair
 -- C Function: scm_car (pair)
 -- C Function: scm_cdr (pair)
     Return the car or the cdr of PAIR, respectively.

 -- Scheme Procedure: cddr pair
 -- Scheme Procedure: cdar pair
 -- Scheme Procedure: cadr pair
 -- Scheme Procedure: caar pair
 -- Scheme Procedure: cdddr pair
 -- Scheme Procedure: cddar pair
 -- Scheme Procedure: cdadr pair
 -- Scheme Procedure: cdaar pair
 -- Scheme Procedure: caddr pair
 -- Scheme Procedure: cadar pair
 -- Scheme Procedure: caadr pair
 -- Scheme Procedure: caaar pair
 -- Scheme Procedure: cddddr pair
 -- Scheme Procedure: cdddar pair
 -- Scheme Procedure: cddadr pair
 -- Scheme Procedure: cddaar pair
 -- Scheme Procedure: cdaddr pair
 -- Scheme Procedure: cdadar pair
 -- Scheme Procedure: cdaadr pair
 -- Scheme Procedure: cdaaar pair
 -- Scheme Procedure: cadddr pair
 -- Scheme Procedure: caddar pair
 -- Scheme Procedure: cadadr pair
 -- Scheme Procedure: cadaar pair
 -- Scheme Procedure: caaddr pair
 -- Scheme Procedure: caadar pair
 -- Scheme Procedure: caaadr pair
 -- Scheme Procedure: caaaar pair
 -- C Function: scm_cddr (pair)
 -- C Function: scm_cdar (pair)
 -- C Function: scm_cadr (pair)
 -- C Function: scm_caar (pair)
 -- C Function: scm_cdddr (pair)
 -- C Function: scm_cddar (pair)
 -- C Function: scm_cdadr (pair)
 -- C Function: scm_cdaar (pair)
 -- C Function: scm_caddr (pair)
 -- C Function: scm_cadar (pair)
 -- C Function: scm_caadr (pair)
 -- C Function: scm_caaar (pair)
 -- C Function: scm_cddddr (pair)
 -- C Function: scm_cdddar (pair)
 -- C Function: scm_cddadr (pair)
 -- C Function: scm_cddaar (pair)
 -- C Function: scm_cdaddr (pair)
 -- C Function: scm_cdadar (pair)
 -- C Function: scm_cdaadr (pair)
 -- C Function: scm_cdaaar (pair)
 -- C Function: scm_cadddr (pair)
 -- C Function: scm_caddar (pair)
 -- C Function: scm_cadadr (pair)
 -- C Function: scm_cadaar (pair)
 -- C Function: scm_caaddr (pair)
 -- C Function: scm_caadar (pair)
 -- C Function: scm_caaadr (pair)
 -- C Function: scm_caaaar (pair)
     These procedures are compositions of car and cdr, where for example caddr could be defined by

          (define caddr (lambda (x) (car (cdr (cdr x)))))

 -- Scheme Procedure: set-car! pair value
 -- C Function: scm_set_car_x (pair, value)
     Stores VALUE in the car field of PAIR.  The value returned by set-car! is unspecified.

 -- Scheme Procedure: set-cdr! pair value
 -- C Function: scm_set_cdr_x (pair, value)
     Stores VALUE in the cdr field of PAIR.  The value returned by set-cdr! is unspecified.

Lists
-----

A very important data type in Scheme---as well as in all other Lisp dialects---is the data type list. (Strictly speaking, Scheme does not have a real datatype list.  Lists are made up of chained pairs, and only exist by definition---a list is a chain of pairs which looks like a list.)

This is the short definition of what a list is:

  * Either the empty list (),

  * or a pair which has a list in its cdr.

List Read Syntax
................

The syntax for lists is an opening parentheses, then all the elements of the list (separated by whitespace) and finally a closing parentheses. (Note that there is no separation character between the list elements, like a comma or a semicolon.).

     (1 2 3)            ; a list of the numbers 1, 2 and 3
     ("foo" bar 3.1415) ; a string, a symbol and a real number
     ()                 ; the empty list

The last example needs a bit more explanation.  A list with no elements, called the empty list, is special in some ways.  It is used for terminating lists by storing it into the cdr of the last pair that makes up a list.  An example will clear that up:

     (car '(1))
     =>
     1
     (cdr '(1))
     =>
     ()

This example also shows that lists have to be quoted (REFFIXME) when written, because they would otherwise be mistakingly taken as procedure applications (see Simple Invocation).

List Predicates
...............

Often it is useful to test whether a given Scheme object is a list or not.  List-processing procedures could use this information to test whether their input is valid, or they could do different things depending on the datatype of their arguments.

 -- Scheme Procedure: list? x
 -- C Function: scm_list_p (x)
     Return #t iff X is a proper list, else #f.

The predicate null? is often used in list-processing code to tell whether a given list has run out of elements.  That is, a loop somehow deals with the elements of a list until the list satisfies null?.  Then, the algorithm terminates.

 -- Scheme Procedure: null? x
 -- C Function: scm_null_p (x)
     Return #t iff X is the empty list, else #f.

 -- C Function: int scm_is_null (SCM x)
     Return 1 when X is the empty list; otherwise return 0.

List Constructors
.................

This section describes the procedures for constructing new lists. list simply returns a list where the elements are the arguments, cons* is similar, but the last argument is stored in the cdr of the last pair of the list.

 -- Scheme Procedure: list elem1 ... elemN
 -- C Function: scm_list_1 (elem1)
 -- C Function: scm_list_2 (elem1, elem2)
 -- C Function: scm_list_3 (elem1, elem2, elem3)
 -- C Function: scm_list_4 (elem1, elem2, elem3, elem4)
 -- C Function: scm_list_5 (elem1, elem2, elem3, elem4, elem5)
 -- C Function: scm_list_n (elem1, ..., elemN, SCM_UNDEFINED)
     Return a new list containing elements ELEM1 to ELEMN.

     scm_list_n takes a variable number of arguments, terminated by the special SCM_UNDEFINED.  That final SCM_UNDEFINED is not included in the list.  None of ELEM1 to ELEMN can themselves be SCM_UNDEFINED, or scm_list_n will terminate at that point.

 -- Scheme Procedure: cons* arg1 arg2 ...
     Like list, but the last arg provides the tail of the constructed list, returning (cons ARG1 (cons ARG2 (cons ... ARGN))).  Requires at least one argument.  If given one argument, that argument is returned as result.  This function is called list* in some other Schemes and in Common LISP.

 -- Scheme Procedure: list-copy lst
 -- C Function: scm_list_copy (lst)
     Return a (newly-created) copy of LST.

 -- Scheme Procedure: make-list n [init]
     Create a list containing of N elements, where each element is initialized to INIT.  INIT defaults to the empty list () if not given.

Note that list-copy only makes a copy of the pairs which make up the spine of the lists.  The list elements are not copied, which means that modifying the elements of the new list also modifies the elements of the old list.  On the other hand, applying procedures like set-cdr! or delv! to the new list will not alter the old list.  If you also need to copy the list elements (making a deep copy), use the procedure copy-tree (see Copying).

List Selection
..............

These procedures are used to get some information about a list, or to retrieve one or more elements of a list.

 -- Scheme Procedure: length lst
 -- C Function: scm_length (lst)
     Return the number of elements in list LST.

 -- Scheme Procedure: last-pair lst
 -- C Function: scm_last_pair (lst)
     Return the last pair in LST, signalling an error if LST is circular.

 -- Scheme Procedure: list-ref list k
 -- C Function: scm_list_ref (list, k)
     Return the Kth element from LIST.

 -- Scheme Procedure: list-tail lst k
 -- Scheme Procedure: list-cdr-ref lst k
 -- C Function: scm_list_tail (lst, k)
     Return the "tail" of LST beginning with its Kth element. The first element of the list is considered to be element 0.

     list-tail and list-cdr-ref are identical.  It may help to think of list-cdr-ref as accessing the Kth cdr of the list, or returning the results of cdring K times down LST.

 -- Scheme Procedure: list-head lst k
 -- C Function: scm_list_head (lst, k)
     Copy the first K elements from LST into a new list, and return it.

Append and Reverse
..................

append and append! are used to concatenate two or more lists in order to form a new list.  reverse and reverse! return lists with the same elements as their arguments, but in reverse order.  The procedure variants with an ! directly modify the pairs which form the list, whereas the other procedures create new pairs.  This is why you should be careful when using the side-effecting variants.

 -- Scheme Procedure: append lst1 ... lstN
 -- Scheme Procedure: append! lst1 ... lstN
 -- C Function: scm_append (lstlst)
 -- C Function: scm_append_x (lstlst)
     Return a list comprising all the elements of lists LST1 to LSTN.

          (append '(x) '(y))          =>  (x y)
          (append '(a) '(b c d))      =>  (a b c d)
          (append '(a (b)) '((c)))    =>  (a (b) (c))

     The last argument LSTN may actually be any object; an improper list results if the last argument is not a proper list.

          (append '(a b) '(c . d))    =>  (a b c . d)
          (append '() 'a)             =>  a

     append doesn't modify the given lists, but the return may share structure with the final LSTN.  append! modifies the given lists to form its return.

     For scm_append and scm_append_x, LSTLST is a list of the list operands LST1 ... LSTN.  That LSTLST itself is not modified or used in the return.

 -- Scheme Procedure: reverse lst
 -- Scheme Procedure: reverse! lst [newtail]
 -- C Function: scm_reverse (lst)
 -- C Function: scm_reverse_x (lst, newtail)
     Return a list comprising the elements of LST, in reverse order.

     reverse constructs a new list, reverse! modifies LST in constructing its return.

     For reverse!, the optional NEWTAIL is appended to to the result.  NEWTAIL isn't reversed, it simply becomes the list tail.  For scm_reverse_x, the NEWTAIL parameter is mandatory, but can be SCM_EOL if no further tail is required.

List Modification
.................

The following procedures modify an existing list, either by changing elements of the list, or by changing the list structure itself.

 -- Scheme Procedure: list-set! list k val
 -- C Function: scm_list_set_x (list, k, val)
     Set the Kth element of LIST to VAL.

 -- Scheme Procedure: list-cdr-set! list k val
 -- C Function: scm_list_cdr_set_x (list, k, val)
     Set the Kth cdr of LIST to VAL.

 -- Scheme Procedure: delq item lst
 -- C Function: scm_delq (item, lst)
     Return a newly-created copy of LST with elements eq? to ITEM removed.  This procedure mirrors memq: delq compares elements of LST against ITEM with eq?.

 -- Scheme Procedure: delv item lst
 -- C Function: scm_delv (item, lst)
     Return a newly-created copy of LST with elements eqv?  to ITEM removed.  This procedure mirrors memv: delv compares elements of LST against ITEM with eqv?.

 -- Scheme Procedure: delete item lst
 -- C Function: scm_delete (item, lst)
     Return a newly-created copy of LST with elements equal?  to ITEM removed.  This procedure mirrors member: delete compares elements of LST against ITEM with equal?.

 -- Scheme Procedure: delq! item lst
 -- Scheme Procedure: delv! item lst
 -- Scheme Procedure: delete! item lst
 -- C Function: scm_delq_x (item, lst)
 -- C Function: scm_delv_x (item, lst)
 -- C Function: scm_delete_x (item, lst)
     These procedures are destructive versions of delq, delv and delete: they modify the pointers in the existing LST rather than creating a new list.  Caveat evaluator: Like other destructive list functions, these functions cannot modify the binding of LST, and so cannot be used to delete the first element of LST destructively.

 -- Scheme Procedure: delq1! item lst
 -- C Function: scm_delq1_x (item, lst)
     Like delq!, but only deletes the first occurrence of ITEM from LST.  Tests for equality using eq?.  See also delv1! and delete1!.

 -- Scheme Procedure: delv1! item lst
 -- C Function: scm_delv1_x (item, lst)
     Like delv!, but only deletes the first occurrence of ITEM from LST.  Tests for equality using eqv?.  See also delq1! and delete1!.

 -- Scheme Procedure: delete1! item lst
 -- C Function: scm_delete1_x (item, lst)
     Like delete!, but only deletes the first occurrence of ITEM from LST.  Tests for equality using equal?.  See also delq1! and delv1!.

 -- Scheme Procedure: filter pred lst
 -- Scheme Procedure: filter! pred lst
     Return a list containing all elements from LST which satisfy the predicate PRED.  The elements in the result list have the same order as in LST.  The order in which PRED is applied to the list elements is not specified.

     filter! is allowed, but not required to modify the structure of

List Searching
..............

The following procedures search lists for particular elements.  They use different comparison predicates for comparing list elements with the object to be searched.  When they fail, they return #f, otherwise they return the sublist whose car is equal to the search object, where equality depends on the equality predicate used.

 -- Scheme Procedure: memq x lst
 -- C Function: scm_memq (x, lst)
     Return the first sublist of LST whose car is eq? to X where the sublists of LST are the non-empty lists returned by (list-tail LST K) for K less than the length of LST.  If X does not occur in LST, then #f (not the empty list) is returned.

 -- Scheme Procedure: memv x lst
 -- C Function: scm_memv (x, lst)
     Return the first sublist of LST whose car is eqv? to X where the sublists of LST are the non-empty lists returned by (list-tail LST K) for K less than the length of LST.  If X does not occur in LST, then #f (not the empty list) is returned.

 -- Scheme Procedure: member x lst
 -- C Function: scm_member (x, lst)
     Return the first sublist of LST whose car is equal? to X where the sublists of LST are the non-empty lists returned by (list-tail LST K) for K less than the length of LST.  If X does not occur in LST, then #f (not the empty list) is returned.

List Mapping
............

List processing is very convenient in Scheme because the process of iterating over the elements of a list can be highly abstracted.  The procedures in this section are the most basic iterating procedures for lists.  They take a procedure and one or more lists as arguments, and apply the procedure to each element of the list.  They differ in their return value.

 -- Scheme Procedure: map proc arg1 arg2 ...
 -- Scheme Procedure: map-in-order proc arg1 arg2 ...
 -- C Function: scm_map (proc, arg1, args)
     Apply PROC to each element of the list ARG1 (if only two arguments are given), or to the corresponding elements of the argument lists (if more than two arguments are given).  The result(s) of the procedure applications are saved and returned in a list.  For map, the order of procedure applications is not specified, map-in-order applies the procedure from left to right to the list elements.

 -- Scheme Procedure: for-each proc arg1 arg2 ...
     Like map, but the procedure is always applied from left to right, and the result(s) of the procedure applications are thrown away.  The return value is not specified.

Vectors
-------

Vectors are sequences of Scheme objects.  Unlike lists, the length of a vector, once the vector is created, cannot be changed.  The advantage of vectors over lists is that the time required to access one element of a vector given its position (synonymous with index), a zero-origin number, is constant, whereas lists have an access time linear to the position of the accessed element in the list.

Vectors can contain any kind of Scheme object; it is even possible to have different types of objects in the same vector.  For vectors containing vectors, you may wish to use arrays, instead.  Note, too, that vectors are the special case of non-uniform, one-dimensional, zero-origin arrays and that most array procedures operate happily on vectors (see Arrays).

Read Syntax for Vectors
.......................

Vectors can literally be entered in source code, just like strings, characters or some of the other data types.  The read syntax for vectors is as follows: A sharp sign (#), followed by an opening parentheses, all elements of the vector in their respective read syntax, and finally a closing parentheses.  The following are examples of the read syntax for vectors; where the first vector only contains numbers and the second three different object types: a string, a symbol and a number in hexadecimal notation.

     #(1 2 3)
     #("Hello" foo #xdeadbeef)

Like lists, vectors have to be quoted (REFFIXME):

     '#(a b c) => #(a b c)

Dynamic Vector Creation and Validation
......................................

Instead of creating a vector implicitly by using the read syntax just described, you can create a vector dynamically by calling one of the vector and list->vector primitives with the list of Scheme values that you want to place into a vector.  The size of the vector thus created is determined implicitly by the number of arguments given.

 -- Scheme Procedure: vector . l
 -- Scheme Procedure: list->vector l
 -- C Function: scm_vector (l)
     Return a newly allocated vector composed of the given arguments.  Analogous to list.

          (vector 'a 'b 'c) => #(a b c)

(As an aside, an interesting implementation detail is that the Guile reader reads the #(...) syntax by reading everything but the initial # as a list, and then passing the list that results to list->vector.  Notice how neatly this fits with the similarity between the read (and print) syntaxes for lists and vectors.)

The inverse operation is vector->list:

 -- Scheme Procedure: vector->list v
 -- C Function: scm_vector_to_list (v)
     Return a newly allocated list composed of the elements of V.

          (vector->list '#(dah dah didah)) =>  (dah dah didah)
          (list->vector '(dididit dah)) =>  #(dididit dah)

To allocate a vector with an explicitly specified size, use make-vector.  With this primitive you can also specify an initial value for the vector elements (the same value for all elements, that is):

 -- Scheme Procedure: make-vector k [fill]
 -- C Function: scm_make_vector (k, fill)
     Return a newly allocated vector of K elements.  If a second argument is given, then each position is initialized to FILL.  Otherwise the initial contents of each position is unspecified.

To check whether an arbitrary Scheme value is a vector, use the vector? primitive:

 -- Scheme Procedure: vector? obj
 -- C Function: scm_vector_p (obj)
     Return #t if OBJ is a vector, otherwise return #f.

Accessing and Modifying Vector Contents
.......................................

vector-length and vector-ref return information about a given vector, respectively its size and the elements that are contained in the vector.

 -- Scheme Procedure: vector-length vector
 -- C Function: scm_vector_length vector
     Return the number of elements in VECTOR as an exact integer.

 -- Scheme Procedure: vector-ref vector k
 -- C Function: scm_vector_ref vector k
     Return the contents of position K of VECTOR. K must be a valid index of VECTOR.

          (vector-ref '#(1 1 2 3 5 8 13 21) 5) => 8
          (vector-ref '#(1 1 2 3 5 8 13 21)
              (let ((i (round (* 2 (acos -1)))))
                (if (inexact? i)
                  (inexact->exact i)
                     i))) => 13

A vector created by one of the dynamic vector constructor procedures (see Vector Creation) can be modified using the following procedures.

NOTE: According to R5RS, it is an error to use any of these procedures on a literally read vector, because such vectors should be considered as constants.  Currently, however, Guile does not detect this error.

 -- Scheme Procedure: vector-set! vector k obj
 -- C Function: scm_vector_set_x vector k obj
     Store OBJ in position K of VECTOR. K must be a valid index of VECTOR. The value returned by vector-set! is unspecified.

          (let ((vec (vector 0 '(2 2 2 2) "Anna")))
            (vector-set! vec 1 '("Sue" "Sue"))
            vec) =>  #(0 ("Sue" "Sue") "Anna")

 -- Scheme Procedure: vector-fill! v fill
 -- C Function: scm_vector_fill_x (v, fill)
     Store FILL in every position of VECTOR.  The value returned by vector-fill! is unspecified.

 -- Scheme Procedure: vector-move-left! vec1 start1 end1 vec2 start2
 -- C Function: scm_vector_move_left_x (vec1, start1, end1, vec2, start2)
     Copy elements from VEC1, positions START1 to END1, to VEC2 starting at position START2.  START1 and START2 are inclusive indices; END1 is exclusive.

     vector-move-left! copies elements in leftmost order. Therefore, in the case where VEC1 and VEC2 refer to the same vector, vector-move-left! is usually appropriate when START1 is greater than START2.

 -- Scheme Procedure: vector-move-right! vec1 start1 end1 vec2 start2
 -- C Function: scm_vector_move_right_x (vec1, start1, end1, vec2, start2)
     Copy elements from VEC1, positions START1 to END1, to VEC2 starting at position START2.  START1 and START2 are inclusive indices; END1 is exclusive.

     vector-move-right! copies elements in rightmost order. Therefore, in the case where VEC1 and VEC2 refer to the same vector, vector-move-right! is usually appropriate when START1 is less than START2.

Uniform Vectors
---------------

A uniform vector is a vector elements are all of a single type.  Guile offers uniform vectors for signed and unsigned 8-bit, 16-bit, 32-bit, and 64-bit integers and for two sizes of floating point values.

Strings could be regarded as uniform vectors of characters, see Strings.  Likewise, bit vectors could be regarded as uniform vectors of bits, see Bit Vectors.  Both are sufficiently different that the procedures described here do not apply to these two data types. However, both strings and bit vectors are arrays, see Arrays.

Uniform vectors are the special case of one-dimensional, uniform, zero-origin array.

Uniform vectors can be useful since they consume less memory than the non-uniform, general vectors.  Also, since the types they can store correspond directly to C types, it is easier to work with them efficiently on a low level.  Consider image processing as an example, where you want to apply a filter to some image.  While you could store the pixels of an image in a general vector and write a general convolution function, things are much more efficient with uniform vectors: the convolution function knows that all pixels are unsigned 8-bit values (say), and can use a very tight inner loop.  (That is, when it is written in C.)

Procedures similar to the vector procedures (see Vectors) are provided for handling these homogeneous vectors, but they are distinct datatypes and the two cannot be inter-mixed.

One set of these procedures is a generic one: it works with all types of uniform vectors.  In addition to that, there is a set of procedures for each type that only works with that type.  Unless you really need to the generality of the first set, it is best to use the more specific functions.  They might not be that much faster, but their use can serve as a kind of declaration and makes it easier to optimize later on.

(Functions for efficiently working with uniform vectors from C are listed at the end of this section.)

The generic set of procedures uses uniform-vector in its names, the specific ones use the tag from the following table.

u8
     unsigned 8-bit integers

s8
     signed 8-bit integers

u16
     unsigned 16-bit integers

s16
     signed 16-bit integers

u32
     unsigned 32-bit integers

s32
     signed 32-bit integers

u64
     unsigned 64-bit integers

s64
     signed 64-bit integers

f32
     the C type float

f64
     the C type double

The external representation (ie. read syntax) for these vectors is similar to normal Scheme vectors, but with an additional tag from the tabel above indiciating the vector's type.  For example,

     #u16(1 2 3)
     #f64(3.1415 2.71)

Note that the read syntax for floating-point here conflicts with #f for false.  In Standard Scheme one can write (1 #f3) for a three element list (1 #f 3), but for Guile (1 #f3) is invalid.  (1 #f 3) is almost certainly what one should write anyway to make the intention clear, so this is rarely a problem.

 -- Scheme Procedure: uniform-vector? obj
 -- Scheme Procedure: u8vector? obj
 -- Scheme Procedure: s8vector? obj
 -- Scheme Procedure: u16vector? obj
 -- Scheme Procedure: s16vector? obj
 -- Scheme Procedure: u32vector? obj
 -- Scheme Procedure: s32vector? obj
 -- Scheme Procedure: u64vector? obj
 -- Scheme Procedure: s64vector? obj
 -- Scheme Procedure: f32vector? obj
 -- Scheme Procedure: f64vector? obj
 -- C Function: scm_uniform_vector_p obj
 -- C Function: scm_u8vector_p obj
 -- C Function: scm_s8vector_p obj
 -- C Function: scm_u16vector_p obj
 -- C Function: scm_s16vector_p obj
 -- C Function: scm_u32vector_p obj
 -- C Function: scm_s32vector_p obj
 -- C Function: scm_u64vector_p obj
 -- C Function: scm_s64vector_p obj
 -- C Function: scm_f32vector_p obj
 -- C Function: scm_f64vector_p obj
     Return #t if OBJ is a homogeneous numeric vector of the indicated type.

 -- Scheme Procedure: make-u8vector n [value]
 -- Scheme Procedure: make-s8vector n [value]
 -- Scheme Procedure: make-u16vector n [value]
 -- Scheme Procedure: make-s16vector n [value]
 -- Scheme Procedure: make-u32vector n [value]
 -- Scheme Procedure: make-s32vector n [value]
 -- Scheme Procedure: make-u64vector n [value]
 -- Scheme Procedure: make-s64vector n [value]
 -- Scheme Procedure: make-f32vector n [value]
 -- Scheme Procedure: make-f64vector n [value]
 -- C Function: scm_make_u8vector n [value]
 -- C Function: scm_make_s8vector n [value]
 -- C Function: scm_make_u16vector n [value]
 -- C Function: scm_make_s16vector n [value]
 -- C Function: scm_make_u32vector n [value]
 -- C Function: scm_make_s32vector n [value]
 -- C Function: scm_make_u64vector n [value]
 -- C Function: scm_make_s64vector n [value]
 -- C Function: scm_make_f32vector n [value]
 -- C Function: scm_make_f64vector n [value]
     Return a newly allocated homogeneous numeric vector holding N elements of the indicated type.  If VALUE is given, the vector is initialized with that value, otherwise the contents are unspecified.

 -- Scheme Procedure: u8vector value ...
 -- Scheme Procedure: s8vector value ...
 -- Scheme Procedure: u16vector value ...
 -- Scheme Procedure: s16vector value ...
 -- Scheme Procedure: u32vector value ...
 -- Scheme Procedure: s32vector value ...
 -- Scheme Procedure: u64vector value ...
 -- Scheme Procedure: s64vector value ...
 -- Scheme Procedure: f32vector value ...
 -- Scheme Procedure: f64vector value ...
 -- C Function: scm_u8vector values
 -- C Function: scm_s8vector values
 -- C Function: scm_u16vector valus
 -- C Function: scm_s16vector valus
 -- C Function: scm_u32vector valus
 -- C Function: scm_s32vector valus
 -- C Function: scm_u64vector valus
 -- C Function: scm_s64vector valus
 -- C Function: scm_f32vector valus
 -- C Function: scm_f64vector valus
     Return a newly allocated homogeneous numeric vector of the indicated type, holding the given parameter VALUEs.  The vector length is the number of parameters given.

 -- Scheme Procedure: uniform-vector-length vec
 -- Scheme Procedure: u8vector-length vec
 -- Scheme Procedure: s8vector-length vec
 -- Scheme Procedure: u16vector-length vec
 -- Scheme Procedure: s16vector-length vec
 -- Scheme Procedure: u32vector-length vec
 -- Scheme Procedure: s32vector-length vec
 -- Scheme Procedure: u64vector-length vec
 -- Scheme Procedure: s64vector-length vec
 -- Scheme Procedure: f32vector-length vec
 -- Scheme Procedure: f64vector-length vec
 -- C Function: scm_uniform_vector_length vec
 -- C Function: scm_u8vector_length vec
 -- C Function: scm_s8vector_length vec
 -- C Function: scm_u16vector_length vec
 -- C Function: scm_s16vector_length vec
 -- C Function: scm_u32vector_length vec
 -- C Function: scm_s32vector_length vec
 -- C Function: scm_u64vector_length vec
 -- C Function: scm_s64vector_length vec
 -- C Function: scm_f32vector_length vec
 -- C Function: scm_f64vector_length vec
     Return the number of elements in VEC.

 -- Scheme Procedure: uniform-vector-ref vec i
 -- Scheme Procedure: u8vector-ref vec i
 -- Scheme Procedure: s8vector-ref vec i
 -- Scheme Procedure: u16vector-ref vec i
 -- Scheme Procedure: s16vector-ref vec i
 -- Scheme Procedure: u32vector-ref vec i
 -- Scheme Procedure: s32vector-ref vec i
 -- Scheme Procedure: u64vector-ref vec i
 -- Scheme Procedure: s64vector-ref vec i
 -- Scheme Procedure: f32vector-ref vec i
 -- Scheme Procedure: f64vector-ref vec i
 -- C Function: scm_uniform_vector_ref vec i
 -- C Function: scm_u8vector_ref vec i
 -- C Function: scm_s8vector_ref vec i
 -- C Function: scm_u16vector_ref vec i
 -- C Function: scm_s16vector_ref vec i
 -- C Function: scm_u32vector_ref vec i
 -- C Function: scm_s32vector_ref vec i
 -- C Function: scm_u64vector_ref vec i
 -- C Function: scm_s64vector_ref vec i
 -- C Function: scm_f32vector_ref vec i
 -- C Function: scm_f64vector_ref vec i
     Return the element at index I in VEC.  The first element in VEC is index 0.

 -- Scheme Procedure: uniform-vector-set! vec i value
 -- Scheme Procedure: u8vector-set! vec i value
 -- Scheme Procedure: s8vector-set! vec i value
 -- Scheme Procedure: u16vector-set! vec i value
 -- Scheme Procedure: s16vector-set! vec i value
 -- Scheme Procedure: u32vector-set! vec i value
 -- Scheme Procedure: s32vector-set! vec i value
 -- Scheme Procedure: u64vector-set! vec i value
 -- Scheme Procedure: s64vector-set! vec i value
 -- Scheme Procedure: f32vector-set! vec i value
 -- Scheme Procedure: f64vector-set! vec i value
 -- C Function: scm_uniform_vector_set_x vec i value
 -- C Function: scm_u8vector_set_x vec i value
 -- C Function: scm_s8vector_set_x vec i value
 -- C Function: scm_u16vector_set_x vec i value
 -- C Function: scm_s16vector_set_x vec i value
 -- C Function: scm_u32vector_set_x vec i value
 -- C Function: scm_s32vector_set_x vec i value
 -- C Function: scm_u64vector_set_x vec i value
 -- C Function: scm_s64vector_set_x vec i value
 -- C Function: scm_f32vector_set_x vec i value
 -- C Function: scm_f64vector_set_x vec i value
     Set the element at index I in VEC to VALUE.  The first element in VEC is index 0.  The return value is unspecified.

 -- Scheme Procedure: uniform-vector->list vec
 -- Scheme Procedure: u8vector->list vec
 -- Scheme Procedure: s8vector->list vec
 -- Scheme Procedure: u16vector->list vec
 -- Scheme Procedure: s16vector->list vec
 -- Scheme Procedure: u32vector->list vec
 -- Scheme Procedure: s32vector->list vec
 -- Scheme Procedure: u64vector->list vec
 -- Scheme Procedure: s64vector->list vec
 -- Scheme Procedure: f32vector->list vec
 -- Scheme Procedure: f64vector->list vec
 -- C Function: scm_uniform_vector_to_list vec
 -- C Function: scm_u8vector_to_list vec
 -- C Function: scm_s8vector_to_list vec
 -- C Function: scm_u16vector_to_list vec
 -- C Function: scm_s16vector_to_list vec
 -- C Function: scm_u32vector_to_list vec
 -- C Function: scm_s32vector_to_list vec
 -- C Function: scm_u64vector_to_list vec
 -- C Function: scm_s64vector_to_list vec
 -- C Function: scm_f32vector_to_list vec
 -- C Function: scm_f64vector_to_list vec
     Return a newly allocated list holding all elements of VEC.

 -- Scheme Procedure: list->u8vector lst
 -- Scheme Procedure: list->s8vector lst
 -- Scheme Procedure: list->u16vector lst
 -- Scheme Procedure: list->s16vector lst
 -- Scheme Procedure: list->u32vector lst
 -- Scheme Procedure: list->s32vector lst
 -- Scheme Procedure: list->u64vector lst
 -- Scheme Procedure: list->s64vector lst
 -- Scheme Procedure: list->f32vector lst
 -- Scheme Procedure: list->f64vector lst
 -- C Function: scm_list_to_u8vector lst
 -- C Function: scm_list_to_s8vector lst
 -- C Function: scm_list_to_u16vector lst
 -- C Function: scm_list_to_s16vector lst
 -- C Function: scm_list_to_u32vector lst
 -- C Function: scm_list_to_s32vector lst
 -- C Function: scm_list_to_u64vector lst
 -- C Function: scm_list_to_s64vector lst
 -- C Function: scm_list_to_f32vector lst
 -- C Function: scm_list_to_f64vector lst
     Return a newly allocated homogeneous numeric vector of the indicated type, initialized with the elements of the list LST.

 -- C Function: int scm_is_uniform_vector (SCM uvec)
     Return 1 when UVEC is a uniform vector, 0 otherwise.

 -- C Function: void * scm_uniform_vector_elements (SCM uvec)
 -- C Function: scm_t_uint8 * scm_u8vector_elements (SCM uvec)
 -- C Function: scm_t_int8 * scm_s8vector_elements (SCM uvec)
 -- C Function: scm_t_uint16 * scm_u16vector_elements (SCM uvec)
 -- C Function: scm_t_int16 * scm_s16vector_elements (SCM uvec)
 -- C Function: scm_t_uint32 * scm_u32vector_elements (SCM uvec)
 -- C Function: scm_t_int32 * scm_s32vector_elements (SCM uvec)
 -- C Function: scm_t_uint64 * scm_u64vector_elements (SCM uvec)
 -- C Function: scm_t_int64 * scm_s64vector_elements (SCM uvec)
 -- C Function: float * scm_f32vector_elements (SCM uvec)
 -- C Function: double * scm_f64vector_elements (SCM uvec)
     Return a pointer to the elements of a uniform vector.  For each call to one of these functions, you must call scm_uniform_vector_release and after that call the pointer to the elements becomes invalid.

 -- C Function: void scm_uniform_vector_release (SCM uvec)
     Finish the access to the elements of a uniform vector, as exlained above.

 -- C Function: size_t scm_c_uniform_vector_length (SCM uvec)
     Return the number of elements of UVEC as a size_t.

 -- C Function: size_t scm_c_uniform_vector_element_size (SCM uvec)
     Return the number of bytes of one element of UVEC.

 -- C Function: size_t scm_c_uniform_vector_size (SCM uvec)
     Return the number of bytes used by all elements of UVEC.  This is just scm_c_uniform_vector_length (UVEC) * scm_c_uniform_vector_element_size (UVEC).

Bit Vectors
-----------

Bit vectors are a specific type of uniform array: an array of booleans with a single zero-based index.

They are displayed as a sequence of 0s and 1s prefixed by #*, e.g.,

     (make-uniform-vector 8 #t #f) =>
     #*00000000

 -- Scheme Procedure: bit-count bool bitvector
 -- C Function: scm_bit_count (bool, bitvector)
     Return a count of how many entries in BITVECTOR are equal to BOOL.  For example,

          (bit-count #f #*000111000)  => 6

 -- Scheme Procedure: bit-position bool bitvector start
 -- C Function: scm_bit_position (bool, bitvector, start)
     Return the index of the first occurrance of BOOL in BITVECTOR, starting from START.  If there is no BOOL entry between START and the end of BITVECTOR, then return #f.  For example,

          (bit-position #t #*000101 0)  => 3
          (bit-position #f #*0001111 3) => #f

 -- Scheme Procedure: bit-invert! bitvector
 -- C Function: scm_bit_invert_x (bitvector)
     Modify BITVECTOR by replacing each element with its negation.

 -- Scheme Procedure: bit-set*! bitvector uvec bool
 -- C Function: scm_bit_set_star_x (bitvector, uvec, bool)
     Set entries of BITVECTOR to BOOL, with UVEC selecting the entries to change.  The return value is unspecified.

     If UVEC is a bit vector, then those entries where it has #t are the ones in BITVECTOR which are set to BOOL. UVEC and BITVECTOR must be the same length.  When BOOL is #t it's like UVEC is OR'ed into BITVECTOR.  Or when BOOL is #f it can be seen as an ANDNOT.

          (define bv #*01000010)
          (bit-set*! bv #*10010001 #t)
          bv
          => #*11010011

     If UVEC is a uniform vector of unsigned long integers, then they're indexes into BITVECTOR which are set to BOOL.

          (define bv #*01000010)
          (bit-set*! bv #u(5 2 7) #t)
          bv
          => #*01100111

 -- Scheme Procedure: bit-count* bitvector uvec bool
 -- C Function: scm_bit_count_star (bitvector, uvec, bool)
     Return a count of how many entries in BITVECTOR are equal to BOOL, with UVEC selecting the entries to consider.

     UVEC is interpreted in the same way as for bit-set*! above.  Namely, if UVEC is a bit vector then entries which have #t there are considered in BITVECTOR.  Or if UVEC is a uniform vector of unsigned long integers then it's the indexes in BITVECTOR to consider.

     For example,

          (bit-count* #*01110111 #*11001101 #t) => 3
          (bit-count* #*01110111 #u(7 0 4) #f)  => 2

Arrays
------

Conventional Arrays
...................

Conventional arrays are a collection of cells organized into an arbitrary number of dimensions.  Each cell can hold any kind of Scheme value and can be accessed in constant time by supplying an index for each dimension.

This contrasts with uniform arrays, which use memory more efficiently but can hold data of only a single type.  It contrasts also with lists where inserting and deleting cells is more efficient, but more time is usually required to access a particular cell.

A conventional array is displayed as # followed by the rank (number of dimensions) followed by the cells, organized into dimensions using parentheses.  The nesting depth of the parentheses is equal to the rank.

When an array is created, the range of each dimension must be specified, e.g., to create a 2 cross3 array with a zero-based index:

     (make-array 'ho 2 3) => #2((ho ho ho) (ho ho ho))

The range of each dimension can also be given explicitly, e.g., another way to create the same array:

     (make-array 'ho '(0 1) '(0 2)) => #2((ho ho ho) (ho ho ho))

A conventional array with one dimension based at zero is identical to a vector:

     (make-array 'ho 3) => #(ho ho ho)

The following procedures can be used with conventional arrays (or vectors).  An argument shown as IDX... means one parameter for each dimension in the array.  Or a IDXLIST is a list of such values, one for each dimension.

 -- Scheme Procedure: array? obj [prot]
 -- C Function: scm_array_p (obj, prot)
     Return #t if the OBJ is an array, and #f if not.

     The PROT argument is used with uniform arrays (see Uniform Arrays).  If given then the return is #t if OBJ is an array and of that prototype.

 -- Scheme Procedure: make-array initial-value bound ...
     Create and return an array that has as many dimensions as there are BOUNDs and fill it with INITIAL-VALUE.

     Each BOUND may be a positive non-zero integer N, in which case the index for that dimension can range from 0 through N-1; or an explicit index range specifier in the form (LOWER UPPER), where both LOWER and UPPER are integers, possibly less than zero, and possibly the same number (however, LOWER cannot be greater than UPPER). See examples above.

 -- Scheme Procedure: array-ref array idx ...
 -- Scheme Procedure: uniform-vector-ref vec args
 -- C Function: scm_uniform_vector_ref (vec, args)
     Return the element at (idx ...) in ARRAY.

          (define a (make-array 999 '(1 2) '(3 4)))
          (array-ref a 2 4) => 999

 -- Scheme Procedure: array-in-bounds? array idx ...
 -- C Function: scm_array_in_bounds_p (array, idxlist)
     Return #t if the given index would be acceptable to array-ref.

          (define a (make-array #f '(1 2) '(3 4)))
          (array-in-bounds? a 2 3) => #f
          (array-in-bounds? a 0 0) => #f

 -- Scheme Procedure: array-set! array obj idx ...
 -- Scheme Procedure: uniform-array-set1! array obj idxlist
 -- C Function: scm_array_set_x (array, obj, idxlist)
     Set the element at (idx ...) in ARRAY to OBJ. The return value is unspecified.

          (define a (make-array #f '(0 1) '(0 1)))
          (array-set! a #t 1 1)
          a => #2((#f #f) (#f #t))

 -- Scheme Procedure: make-shared-array oldarray mapfunc bound ...
 -- C Function: scm_make_shared_array (oldarray, mapfunc, boundlist)
     make-shared-array can be used to create shared subarrays of other arrays.  The MAPPER is a function that translates coordinates in the new array into coordinates in the old array.  A MAPPER must be linear, and its range must stay within the bounds of the old array, but it can be otherwise arbitrary.  A simple example:

          (define fred (make-array #f 8 8))
          (define freds-diagonal
            (make-shared-array fred (lambda (i) (list i i)) 8))
          (array-set! freds-diagonal 'foo 3)
          (array-ref fred 3 3) => foo
          (define freds-center
            (make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j))) 2 2))
          (array-ref freds-center 0 0) => foo

 -- Scheme Procedure: shared-array-increments array
 -- C Function: scm_shared_array_increments (array)
     For each dimension, return the distance between elements in the root vector.

 -- Scheme Procedure: shared-array-offset array
 -- C Function: scm_shared_array_offset (array)
     Return the root vector index of the first element in the array.

 -- Scheme Procedure: shared-array-root array
 -- C Function: scm_shared_array_root (array)
     Return the root vector of a shared array.

 -- Scheme Procedure: transpose-array array dim1 ...
 -- C Function: scm_transpose_array (array, dimlist)
     Return an array sharing contents with ARRAY, but with dimensions arranged in a different order.  There must be one DIM argument for each dimension of ARRAY. DIM1, DIM2, ... should be integers between 0 and the rank of the array to be returned.  Each integer in that range must appear at least once in the argument list.

     The values of DIM1, DIM2, ... correspond to dimensions in the array to be returned, and their positions in the argument list to dimensions of ARRAY.  Several DIMs may have the same value, in which case the returned array will have smaller rank than ARRAY.

          (transpose-array '#2((a b) (c d)) 1 0) => #2((a c) (b d))
          (transpose-array '#2((a b) (c d)) 0 0) => #1(a d)
          (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) =>
                          #2((a 4) (b 5) (c 6))

 -- Scheme Procedure: enclose-array array dim1 ...
 -- C Function: scm_enclose_array (array, dimlist)
     DIM1, DIM2 ... should be nonnegative integers less than the rank of ARRAY.  enclose-array returns an array resembling an array of shared arrays.  The dimensions of each shared array are the same as the DIMth dimensions of the original array, the dimensions of the outer array are the same as those of the original array that did not match a DIM.

     An enclosed array is not a general Scheme array.  Its elements may not be set using array-set!.  Two references to the same element of an enclosed array will be equal? but will not in general be eq?.  The value returned by array-prototype when given an enclosed array is unspecified.

     For example,

          (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1)
          =>
          #<enclosed-array (#1(a d) #1(b e) #1(c f)) (#1(1 4) #1(2 5) #1(3 6))>

          (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 0)
          =>
          #<enclosed-array #2((a 1) (d 4)) #2((b 2) (e 5)) #2((c 3) (f 6))>

 -- Scheme Procedure: array-shape array
 -- Scheme Procedure: array-dimensions array
 -- C Function: scm_array_dimensions (array)
     Return a list of the bounds for each dimenson of ARRAY.

     array-shape gives (LOWER UPPER) for each dimension.  array-dimensions instead returns just UPPER+1 for dimensions with a 0 lower bound.  Both are suitable as input to make-array.

     For example,

          (define a (make-array 'foo '(-1 3) 5))
          (array-shape a)      => ((-1 3) (0 4))
          (array-dimensions a) => ((-1 3) 5)

 -- Scheme Procedure: array-rank obj
 -- C Function: scm_array_rank (obj)
     Return the number of dimensions of an array OBJ, or if OBJ is not an array then return 0.

 -- Scheme Procedure: array->list array
 -- C Function: scm_array_to_list (array)
     Return a list consisting of all the elements, in order, of ARRAY.

 -- Scheme Procedure: array-copy! src dst
 -- Scheme Procedure: array-copy-in-order! src dst
 -- C Function: scm_array_copy_x (src, dst)
     Copy every element from vector or array SRC to the corresponding element of DST.  DST must have the same rank as SRC, and be at least as large in each dimension.  The return value is unspecified.

 -- Scheme Procedure: array-fill! array fill
 -- C Function: scm_array_fill_x (array, fill)
     Store FILL in every element of ARRAY.  The value returned is unspecified.

 -- Scheme Procedure: array-equal? array1 array2 ...
     Return #t if all arguments are arrays with the same shape, the same type, and have corresponding elements which are either equal? or array-equal?.  This function differs from equal? in that a one dimensional shared array may be ARRAY-EQUAL? but not EQUAL? to a vector or uniform vector.

 -- Scheme Procedure: array-contents array [strict]
 -- C Function: scm_array_contents (array, strict)
     If ARRAY may be unrolled into a one dimensional shared array without changing their order (last subscript changing fastest), then array-contents returns that shared array, otherwise it returns #f.  All arrays made by make-array and make-uniform-array may be unrolled, some arrays made by make-shared-array may not be.

     If the optional argument STRICT is provided, a shared array will be returned only if its elements are stored internally contiguous in memory.

Array Mapping
.............

 -- Scheme Procedure: array-map! dst proc src1 ... srcN
 -- Scheme Procedure: array-map-in-order! dst proc src1 ... srcN
 -- C Function: scm_array_map_x (dst, proc, srclist)
     Set each element of the DST array to values obtained from calls to PROC.  The value returned is unspecified.

     Each call is (PROC ELEM1 ... ELEMN), where each ELEM is from the corresponding SRC array, at the DST index.  array-map-in-order! makes the calls in row-major order, array-map! makes them in an unspecified order.

     The SRC arrays must have the same number of dimensions as DST, and must have a range for each dimension which covers the range in DST.  This ensures all DST indices are valid in each SRC.

 -- Scheme Procedure: array-for-each proc src1 ... srcN
 -- C Function: scm_array_for_each (proc, src1, srclist)
     Apply PROC to each tuple of elements of SRC1 ... SRCN, in row-major order.  The value returned is unspecified.

 -- Scheme Procedure: array-index-map! dst proc
 -- C Function: scm_array_index_map_x (dst, proc)
     Set each element of the DST array to values returned by calls to PROC.  The value returned is unspecified.

     Each call is (PROC I1 ... IN), where I1...IN is the destination index, one parameter for each dimension.  The order in which the calls are made is unspecified.

     For example, to create a 4\times4, 4x4 matrix representing a cyclic group,

              / 0 1 2 3 \
              | 1 2 3 0 |
              | 2 3 0 1 |
              \ 3 0 1 2 /

          (define a (make-array #f 4 4))
          (array-index-map! a (lambda (i j)
                                (modulo (+ i j) 4)))

Uniform Arrays
..............

Uniform arrays have elements all of the same type and occupy less storage than conventional arrays.  Uniform arrays with a single zero-based dimension are also known as uniform vectors.  The procedures in this section can also be used on conventional arrays, vectors, bit-vectors and strings.

When creating a uniform array, the type of data to be stored is indicated with a PROTOTYPE argument.  The following table lists the types available and example prototypes:

     prototype           type                       printing character

     #t             boolean (bit-vector)                    b
     #\a            char (string)                           a
     #\nul          byte (integer)                          y
     's             short (integer)                         h
     1              unsigned long (integer)                 u
     -1             signed long (integer)                   e
     'l             signed long long (integer)              l
     1.0            float (single precision)                s
     1/3            double (double precision float)         i
     0+i            complex (double precision)              c
     ()             conventional vector

Note that with the introduction of exact fractions in Guile 1.8, 1/3 here is now a fraction, where previously such an expression was a double 0.333....  For most normal usages this should be source code compatible.

Unshared uniform arrays of characters with a single zero-based dimension are identical to strings:

     (make-uniform-array #\a 3) =>
     "aaa"

Unshared uniform arrays of booleans with a single zero-based dimension are identical to bit-vectors.

     (make-uniform-array #t 3) =>
     #*111

Other uniform vectors are written in a form similar to that of vectors, except that a single character from the above table is put between # and (.  For example, a uniform vector of signed long integers is displayed in the form '#e(3 5 9).

 -- Scheme Procedure: make-uniform-array prototype bound1 bound2 ...
     Create and return a uniform array of type corresponding to PROTOTYPE that has as many dimensions as there are BOUNDs and fill it with PROTOTYPE.

 -- Scheme Procedure: array-prototype ra
 -- C Function: scm_array_prototype (ra)
     Return an object that would produce an array of the same type as ARRAY, if used as the PROTOTYPE for make-uniform-array.

 -- Scheme Procedure: list->uniform-array ndim prot lst
 -- Scheme Procedure: list->uniform-vector prot lst
 -- C Function: scm_list_to_uniform_array (ndim, prot, lst)
     Return a uniform array of the type indicated by prototype PROT with elements the same as those of LST. Elements must be of the appropriate type, no coercions are done.

 -- Scheme Procedure: uniform-vector-fill! uve fill
     Store FILL in every element of UVE.  The value returned is unspecified.

 -- Scheme Procedure: uniform-vector-length v
 -- C Function: scm_uniform_vector_length (v)
     Return the number of elements in UVE.

 -- Scheme Procedure: dimensions->uniform-array dims prot [fill]
 -- Scheme Procedure: make-uniform-vector length prototype [fill]
 -- C Function: scm_dimensions_to_uniform_array (dims, prot, fill)
     Create and return a uniform array or vector of type corresponding to PROTOTYPE with dimensions DIMS or length LENGTH.  If FILL is supplied, it's used to fill the array, otherwise PROTOTYPE is used.

 -- Scheme Procedure: uniform-array-read! ra [port_or_fd [start [end]]]
 -- Scheme Procedure: uniform-vector-read! uve [port-or-fdes] [start] [end]
 -- C Function: scm_uniform_array_read_x (ra, port_or_fd, start, end)
     Attempt to read all elements of URA, in lexicographic order, as binary objects from PORT-OR-FDES. If an end of file is encountered, the objects up to that point are put into URA (starting at the beginning) and the remainder of the array is unchanged.

     The optional arguments START and END allow a specified region of a vector (or linearized array) to be read, leaving the remainder of the vector unchanged.

     uniform-array-read! returns the number of objects read. PORT-OR-FDES may be omitted, in which case it defaults to the value returned by (current-input-port).

 -- Scheme Procedure: uniform-array-write v [port_or_fd [start [end]]]
 -- Scheme Procedure: uniform-vector-write uve [port-or-fdes] [start] [end]
 -- C Function: scm_uniform_array_write (v, port_or_fd, start, end)
     Writes all elements of URA as binary objects to PORT-OR-FDES.

     The optional arguments START and END allow a specified region of a vector (or linearized array) to be written.

     The number of objects actually written is returned. PORT-OR-FDES may be omitted, in which case it defaults to the value returned by (current-output-port).

Records
-------

A record type is a first class object representing a user-defined data type.  A record is an instance of a record type.

 -- Scheme Procedure: record? obj
     Return #t if OBJ is a record of any type and #f otherwise.

     Note that record? may be true of any Scheme value; there is no promise that records are disjoint with other Scheme types.

 -- Scheme Procedure: make-record-type type-name field-names
     Return a record-type descriptor, a value representing a new data type disjoint from all others.  The TYPE-NAME argument must be a string, but is only used for debugging purposes (such as the printed representation of a record of the new type).  The FIELD-NAMES argument is a list of symbols naming the fields of a record of the new type.  It is an error if the list contains any duplicates.  It is unspecified how record-type descriptors are represented.

 -- Scheme Procedure: record-constructor rtd [field-names]
     Return a procedure for constructing new members of the type represented by RTD.  The returned procedure accepts exactly as many arguments as there are symbols in the given list, FIELD-NAMES; these are used, in order, as the initial values of those fields in a new record, which is returned by the constructor procedure.  The values of any fields not named in that list are unspecified.  The FIELD-NAMES argument defaults to the list of field names in the call to make-record-type that created the type represented by RTD; if the FIELD-NAMES argument is provided, it is an error if it contains any duplicates or any symbols not in the default list.

 -- Scheme Procedure: record-predicate rtd
     Return a procedure for testing membership in the type represented by RTD.  The returned procedure accepts exactly one argument and returns a true value if the argument is a member of the indicated record type; it returns a false value otherwise.

 -- Scheme Procedure: record-accessor rtd field-name
     Return a procedure for reading the value of a particular field of a member of the type represented by RTD.  The returned procedure accepts exactly one argument which must be a record of the appropriate type; it returns the current value of the field named by the symbol FIELD-NAME in that record.  The symbol FIELD-NAME must be a member of the list of field-names in the call to make-record-type that created the type represented by RTD.

 -- Scheme Procedure: record-modifier rtd field-name
     Return a procedure for writing the value of a particular field of a member of the type represented by RTD.  The returned procedure accepts exactly two arguments: first, a record of the appropriate type, and second, an arbitrary Scheme value; it modifies the field named by the symbol FIELD-NAME in that record to contain the given value. The returned value of the modifier procedure is unspecified.  The symbol FIELD-NAME must be a member of the list of field-names in the call to make-record-type that created the type represented by RTD.

 -- Scheme Procedure: record-type-descriptor record
     Return a record-type descriptor representing the type of the given record.  That is, for example, if the returned descriptor were passed to record-predicate, the resulting predicate would return a true value when passed the given record.  Note that it is not necessarily the case that the returned descriptor is the one that was passed to record-constructor in the call that created the constructor procedure that created the given record.

 -- Scheme Procedure: record-type-name rtd
     Return the type-name associated with the type represented by rtd.  The returned value is eqv? to the TYPE-NAME argument given in the call to make-record-type that created the type represented by RTD.

 -- Scheme Procedure: record-type-fields rtd
     Return a list of the symbols naming the fields in members of the type represented by RTD.  The returned value is equal? to the field-names argument given in the call to make-record-type that created the type represented by RTD.

Structures
----------

[FIXME: this is pasted in from Tom Lord's original guile.texi and should be reviewed]

A structure type is a first class user-defined data type.  A structure is an instance of a structure type.  A structure type is itself a structure.

Structures are less abstract and more general than traditional records. In fact, in Guile Scheme, records are implemented using structures.

Structure Concepts
..................

A structure object consists of a handle, structure data, and a vtable. The handle is a Scheme value which points to both the vtable and the structure's data.  Structure data is a dynamically allocated region of memory, private to the structure, divided up into typed fields.  A vtable is another structure used to hold type-specific data.  Multiple structures can share a common vtable.

Three concepts are key to understanding structures.

  * layout specifications

     Layout specifications determine how memory allocated to structures is divided up into fields.  Programmers must write a layout specification whenever a new type of structure is defined.

  * structural accessors

     Structure access is by field number.   There is only one set of accessors common to all structure objects.

  * vtables

     Vtables, themselves structures, are first class representations of
     disjoint sub-types of structures in general.   In most cases, when a
     new structure is created, programmers must specify a vtable for the
     new structure.   Each vtable has a field describing the layout of its
     instances.   Vtables can have additional, user-defined fields as well.

Structure Layout
................

When a structure is created, a region of memory is allocated to hold its state.  The layout of the structure's type determines how that memory is divided into fields.

Each field has a specified type.  There are only three types allowed, each corresponding to a one letter code.  The allowed types are:

  * 'u' -- unprotected

     The field holds binary data that is not GC protected.

  * 'p' -- protected

     The field holds a Scheme value and is GC protected.

  * 's' -- self

     The field holds a Scheme value and is GC protected.  When a structure is created with this type of field, the field is initialized to refer to the structure's own handle.  This kind of field is mainly useful when mixing Scheme and C code in which the C code may need to compute a structure's handle given only the address of its malloc'd data.

Each field also has an associated access protection.   There are only three kinds of protection, each corresponding to a one letter code. The allowed protections are:

  * 'w' -- writable

     The field can be read and written.

  * 'r' -- readable

     The field can be read, but not written.

  * 'o' -- opaque

     The field can be neither read nor written.   This kind of protection is for fields useful only to built-in routines.

A layout specification is described by stringing together pairs of letters: one to specify a field type and one to specify a field protection.    For example, a traditional cons pair type object could be described as:

     ; cons pairs have two writable fields of Scheme data
     "pwpw"

A pair object in which the first field is held constant could be:

     "prpw"

Binary fields, (fields of type "u"), hold one word each.  The size of a word is a machine dependent value defined to be equal to the value of the C expression: sizeof (long).

The last field of a structure layout may specify a tail array. A tail array is indicated by capitalizing the field's protection code ('W', 'R' or 'O').   A tail-array field is replaced by a read-only binary data field containing an array size.   The array size is determined at the time the structure is created.  It is followed by a corresponding number of fields of the type specified for the tail array.   For example, a conventional Scheme vector can be described as:

     ; A vector is an arbitrary number of writable fields holding Scheme
     ; values:
     "pW"

In the above example, field 0 contains the size of the vector and fields beginning at 1 contain the vector elements.

A kind of tagged vector (a constant tag followed by conventional vector elements) might be:

     "prpW"

Structure layouts are represented by specially interned symbols whose name is a string of type and protection codes.  To create a new structure layout, use this procedure:

 -- Scheme Procedure: make-struct-layout fields
 -- C Function: scm_make_struct_layout (fields)
     Return a new structure layout object.

     FIELDS must be a string made up of pairs of characters strung together.  The first character of each pair describes a field type, the second a field protection.  Allowed types are 'p' for GC-protected Scheme data, 'u' for unprotected binary data, and 's' for a field that points to the structure itself.    Allowed protections are 'w' for mutable fields, 'r' for read-only fields, and 'o' for opaque fields.  The last field protection specification may be capitalized to indicate that the field is a tail-array.

Structure Basics
................

This section describes the basic procedures for creating and accessing structures.

 -- Scheme Procedure: make-struct vtable tail_array_size . init
 -- C Function: scm_make_struct (vtable, tail_array_size, init)
     Create a new structure.

     TYPE must be a vtable structure (see Vtables).

     TAIL-ELTS must be a non-negative integer.  If the layout specification indicated by TYPE includes a tail-array, this is the number of elements allocated to that array.

     The INIT1, ... are optional arguments describing how successive fields of the structure should be initialized.  Only fields with protection 'r' or 'w' can be initialized, except for fields of type 's', which are automatically initialized to point to the new structure itself; fields with protection 'o' can not be initialized by Scheme programs.

     If fewer optional arguments than initializable fields are supplied, fields of type 'p' get default value #f while fields of type 'u' are initialized to 0.

     Structs are currently the basic representation for record-like data structures in Guile.  The plan is to eventually replace them with a new representation which will at the same time be easier to use and more powerful.

     For more information, see the documentation for make-vtable-vtable.

 -- Scheme Procedure: struct? x
 -- C Function: scm_struct_p (x)
     Return #t iff X is a structure object, else #f.

 -- Scheme Procedure: struct-ref handle pos
 -- Scheme Procedure: struct-set! struct n value
 -- C Function: scm_struct_ref (handle, pos)
 -- C Function: scm_struct_set_x (struct, n, value)
     Access (or modify) the Nth field of STRUCT.

     If the field is of type 'p', then it can be set to an arbitrary value.

     If the field is of type 'u', then it can only be set to a non-negative integer value small enough to fit in one machine word.

Vtables
.......

Vtables are structures that are used to represent structure types.  Each vtable contains a layout specification in field vtable-index-layout -- instances of the type are laid out according to that specification.  Vtables contain additional fields which are used only internally to libguile.  The variable vtable-offset-user is bound to a field number.  Vtable fields at that position or greater are user definable.

 -- Scheme Procedure: struct-vtable handle
 -- C Function: scm_struct_vtable (handle)
     Return the vtable structure that describes the type of STRUCT.

 -- Scheme Procedure: struct-vtable? x
 -- C Function: scm_struct_vtable_p (x)
     Return #t iff X is a vtable structure.

If you have a vtable structure, V, you can create an instance of the type it describes by using (make-struct V ...).  But where does V itself come from?  One possibility is that V is an instance of a user-defined vtable type, V', so that V is created by using (make-struct V' ...).  Another possibility is that V is an instance of the type it itself describes.  Vtable structures of the second sort are created by this procedure:

 -- Scheme Procedure: make-vtable-vtable user_fields tail_array_size . init
 -- C Function: scm_make_vtable_vtable (user_fields, tail_array_size, init)
     Return a new, self-describing vtable structure.

     USER-FIELDS is a string describing user defined fields of the vtable beginning at index vtable-offset-user (see make-struct-layout).

     TAIL-SIZE specifies the size of the tail-array (if any) of this vtable.

     INIT1, ... are the optional initializers for the fields of the vtable.

     Vtables have one initializable system field---the struct printer. This field comes before the user fields in the initializers passed to make-vtable-vtable and make-struct, and thus works as a third optional argument to make-vtable-vtable and a fourth to make-struct when creating vtables:

     If the value is a procedure, it will be called instead of the standard printer whenever a struct described by this vtable is printed. The procedure will be called with arguments STRUCT and PORT.

     The structure of a struct is described by a vtable, so the vtable is in essence the type of the struct.  The vtable is itself a struct with a vtable.  This could go on forever if it weren't for the vtable-vtables which are self-describing vtables, and thus terminate the chain.

     There are several potential ways of using structs, but the standard one is to use three kinds of structs, together building up a type sub-system: one vtable-vtable working as the root and one or several "types", each with a set of "instances".  (The vtable-vtable should be compared to the class <class> which is the class of itself.)

          (define ball-root (make-vtable-vtable "pr" 0))

          (define (make-ball-type ball-color)
            (make-struct ball-root 0
          	       (make-struct-layout "pw")
                         (lambda (ball port)
                           (format port "#<a ~A ball owned by ~A>"
                                   (color ball)
                                   (owner ball)))
                         ball-color))
          (define (color ball) (struct-ref (struct-vtable ball) vtable-offset-user))
          (define (owner ball) (struct-ref ball 0))

          (define red (make-ball-type 'red))
          (define green (make-ball-type 'green))

          (define (make-ball type owner) (make-struct type 0 owner))

          (define ball (make-ball green 'Nisse))
          ball => #<a green ball owned by Nisse>

 -- Scheme Procedure: struct-vtable-name vtable
 -- C Function: scm_struct_vtable_name (vtable)
     Return the name of the vtable VTABLE.

 -- Scheme Procedure: set-struct-vtable-name! vtable name
 -- C Function: scm_set_struct_vtable_name_x (vtable, name)
     Set the name of the vtable VTABLE to NAME.

 -- Scheme Procedure: struct-vtable-tag handle
 -- C Function: scm_struct_vtable_tag (handle)
     Return the vtable tag of the structure HANDLE.

Dictionary Types
----------------

A dictionary object is a data structure used to index information in a user-defined way.  In standard Scheme, the main aggregate data types are lists and vectors.  Lists are not really indexed at all, and vectors are indexed only by number (e.g. (vector-ref foo 5)).  Often you will find it useful to index your data on some other type; for example, in a library catalog you might want to look up a book by the name of its author.  Dictionaries are used to help you organize information in such a way.

An association list (or alist for short) is a list of key-value pairs.  Each pair represents a single quantity or object; the car of the pair is a key which is used to identify the object, and the cdr is the object's value.

A hash table also permits you to index objects with arbitrary keys, but in a way that makes looking up any one object extremely fast.  A well-designed hash system makes hash table lookups almost as fast as conventional array or vector references.

Alists are popular among Lisp programmers because they use only the language's primitive operations (lists, car, cdr and the equality primitives).  No changes to the language core are necessary.  Therefore, with Scheme's built-in list manipulation facilities, it is very convenient to handle data stored in an association list.  Also, alists are highly portable and can be easily implemented on even the most minimal Lisp systems.

However, alists are inefficient, especially for storing large quantities of data.  Because we want Guile to be useful for large software systems as well as small ones, Guile provides a rich set of tools for using either association lists or hash tables.

Association Lists
-----------------

An association list is a conventional data structure that is often used to implement simple key-value databases.  It consists of a list of entries in which each entry is a pair.  The key of each entry is the car of the pair and the value of each entry is the cdr.

     ASSOCIATION LIST ::=  '( (KEY1 . VALUE1)
                              (KEY2 . VALUE2)
                              (KEY3 . VALUE3)
                              ...
                            )

Association lists are also known, for short, as alists.

The structure of an association list is just one example of the infinite number of possible structures that can be built using pairs and lists. As such, the keys and values in an association list can be manipulated using the general list structure procedures cons, car, cdr, set-car!, set-cdr! and so on.  However, because association lists are so useful, Guile also provides specific procedures for manipulating them.

Alist Key Equality
..................

All of Guile's dedicated association list procedures, apart from acons, come in three flavours, depending on the level of equality that is required to decide whether an existing key in the association list is the same as the key that the procedure call uses to identify the required entry.

  * Procedures with assq in their name use eq? to determine key equality.

  * Procedures with assv in their name use eqv? to determine key equality.

  * Procedures with assoc in their name use equal? to determine key equality.

acons is an exception because it is used to build association lists which do not require their entries' keys to be unique.

Adding or Setting Alist Entries
...............................

acons adds a new entry to an association list and returns the combined association list.  The combined alist is formed by consing the new entry onto the head of the alist specified in the acons procedure call.  So the specified alist is not modified, but its contents become shared with the tail of the combined alist that acons returns.

In the most common usage of acons, a variable holding the original association list is updated with the combined alist:

     (set! address-list (acons name address address-list))

In such cases, it doesn't matter that the old and new values of address-list share some of their contents, since the old value is usually no longer independently accessible.

Note that acons adds the specified new entry regardless of whether the alist may already contain entries with keys that are, in some sense, the same as that of the new entry.  Thus acons is ideal for building alists where there is no concept of key uniqueness.

     (set! task-list (acons 3 "pay gas bill" '()))
     task-list
     =>
     ((3 . "pay gas bill"))

     (set! task-list (acons 3 "tidy bedroom" task-list))
     task-list
     =>
     ((3 . "tidy bedroom") (3 . "pay gas bill"))

assq-set!, assv-set! and assoc-set! are used to add or replace an entry in an association list where there is a concept of key uniqueness.  If the specified association list already contains an entry whose key is the same as that specified in the procedure call, the existing entry is replaced by the new one. Otherwise, the new entry is consed onto the head of the old association list to create the combined alist.  In all cases, these procedures return the combined alist.

assq-set! and friends may destructively modify the structure of the old association list in such a way that an existing variable is correctly updated without having to set! it to the value returned:

     address-list
     =>
     (("mary" . "34 Elm Road") ("james" . "16 Bow Street"))

     (assoc-set! address-list "james" "1a London Road")
     =>
     (("mary" . "34 Elm Road") ("james" . "1a London Road"))

     address-list
     =>
     (("mary" . "34 Elm Road") ("james" . "1a London Road"))

Or they may not:

     (assoc-set! address-list "bob" "11 Newington Avenue")
     =>
     (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
      ("james" . "1a London Road"))

     address-list
     =>
     (("mary" . "34 Elm Road") ("james" . "1a London Road"))

The only safe way to update an association list variable when adding or replacing an entry like this is to set! the variable to the returned value:

     (set! address-list
           (assoc-set! address-list "bob" "11 Newington Avenue"))
     address-list
     =>
     (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
      ("james" . "1a London Road"))

Because of this slight inconvenience, you may find it more convenient to use hash tables to store dictionary data.  If your application will not be modifying the contents of an alist very often, this may not make much difference to you.

If you need to keep the old value of an association list in a form independent from the list that results from modification by acons, assq-set!, assv-set! or assoc-set!, use list-copy to copy the old association list before modifying it.

 -- Scheme Procedure: acons key value alist
 -- C Function: scm_acons (key, value, alist)
     Add a new key-value pair to ALIST.  A new pair is created whose car is KEY and whose cdr is VALUE, and the pair is consed onto ALIST, and the new list is returned.  This function is not destructive; ALIST is not modified.

 -- Scheme Procedure: assq-set! alist key val
 -- Scheme Procedure: assv-set! alist key value
 -- Scheme Procedure: assoc-set! alist key value
 -- C Function: scm_assq_set_x (alist, key, val)
 -- C Function: scm_assv_set_x (alist, key, val)
 -- C Function: scm_assoc_set_x (alist, key, val)
     Reassociate KEY in ALIST with VALUE: find any existing ALIST entry for KEY and associate it with the new VALUE.  If ALIST does not contain an entry for KEY, add a new one.  Return the (possibly new) alist.

     These functions do not attempt to verify the structure of ALIST, and so may cause unusual results if passed an object that is not an association list.

Retrieving Alist Entries
........................

assq, assv and assoc take an alist and a key as arguments and return the entry for that key if an entry exists, or #f if there is no entry for that key.  Note that, in the cases where an entry exists, these procedures return the complete entry, that is (KEY . VALUE), not just the value.

 -- Scheme Procedure: assq key alist
 -- Scheme Procedure: assv key alist
 -- Scheme Procedure: assoc key alist
 -- C Function: scm_assq (key, alist)
 -- C Function: scm_assv (key, alist)
 -- C Function: scm_assoc (key, alist)
     Fetch the entry in ALIST that is associated with KEY.  To decide whether the argument KEY matches a particular entry in ALIST, assq compares keys with eq?, assv uses eqv? and assoc uses equal?.  If KEY cannot be found in ALIST (according to whichever equality predicate is in use), then return #f.  These functions return the entire alist entry found (i.e. both the key and the value).

assq-ref, assv-ref and assoc-ref, on the other hand, take an alist and a key and return just the value for that key, if an entry exists.  If there is no entry for the specified key, these procedures return #f.

This creates an ambiguity: if the return value is #f, it means either that there is no entry with the specified key, or that there is an entry for the specified key, with value #f. Consequently, assq-ref and friends should only be used where it is known that an entry exists, or where the ambiguity doesn't matter for some other reason.

 -- Scheme Procedure: assq-ref alist key
 -- Scheme Procedure: assv-ref alist key
 -- Scheme Procedure: assoc-ref alist key
 -- C Function: scm_assq_ref (alist, key)
 -- C Function: scm_assv_ref (alist, key)
 -- C Function: scm_assoc_ref (alist, key)
     Like assq, assv and assoc, except that only the value associated with KEY in ALIST is returned.  These functions are equivalent to

          (let ((ent (ASSOCIATOR KEY ALIST)))
            (and ent (cdr ent)))

     where ASSOCIATOR is one of assq, assv or assoc.

Removing Alist Entries
......................

To remove the element from an association list whose key matches a specified key, use assq-remove!, assv-remove! or assoc-remove! (depending, as usual, on the level of equality required between the key that you specify and the keys in the association list).

As with assq-set! and friends, the specified alist may or may not be modified destructively, and the only safe way to update a variable containing the alist is to set! it to the value that assq-remove! and friends return.

     address-list
     =>
     (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
      ("james" . "1a London Road"))

     (set! address-list (assoc-remove! address-list "mary"))
     address-list
     =>
     (("bob" . "11 Newington Avenue") ("james" . "1a London Road"))

Note that, when assq/v/oc-remove! is used to modify an association list that has been constructed only using the corresponding assq/v/oc-set!, there can be at most one matching entry in the alist, so the question of multiple entries being removed in one go does not arise.  If assq/v/oc-remove! is applied to an association list that has been constructed using acons, or an assq/v/oc-set! with a different level of equality, or any mixture of these, it removes only the first matching entry from the alist, even if the alist might contain further matching entries.  For example:

     (define address-list '())
     (set! address-list (assq-set! address-list "mary" "11 Elm Street"))
     (set! address-list (assq-set! address-list "mary" "57 Pine Drive"))
     address-list
     =>
     (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street"))

     (set! address-list (assoc-remove! address-list "mary"))
     address-list
     =>
     (("mary" . "11 Elm Street"))

In this example, the two instances of the string "mary" are not the same when compared using eq?, so the two assq-set! calls add two distinct entries to address-list.  When compared using equal?, both "mary"s in address-list are the same as the "mary" in the assoc-remove! call, but assoc-remove! stops after removing the first matching entry that it finds, and so one of the "mary" entries is left in place.

 -- Scheme Procedure: assq-remove! alist key
 -- Scheme Procedure: assv-remove! alist key
 -- Scheme Procedure: assoc-remove! alist key
 -- C Function: scm_assq_remove_x (alist, key)
 -- C Function: scm_assv_remove_x (alist, key)
 -- C Function: scm_assoc_remove_x (alist, key)
     Delete the first entry in ALIST associated with KEY, and return the resulting alist.

Sloppy Alist Functions
......................

sloppy-assq, sloppy-assv and sloppy-assoc behave like the corresponding non-sloppy- procedures, except that they return #f when the specified association list is not well-formed, where the non-sloppy- versions would signal an error.

Specifically, there are two conditions for which the non-sloppy- procedures signal an error, which the sloppy- procedures handle instead by returning #f.  Firstly, if the specified alist as a whole is not a proper list:

     (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
     =>
     ERROR: In procedure assoc in expression (assoc "mary" (quote #)):
     ERROR: Wrong type argument in position 2 (expecting association list): ((1 . 2) ("key" . "door") . "open sesame")

     (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
     =>
     #f

Secondly, if one of the entries in the specified alist is not a pair:

     (assoc 2 '((1 . 1) 2 (3 . 9)))
     =>
     ERROR: In procedure assoc in expression (assoc 2 (quote #)):
     ERROR: Wrong type argument in position 2 (expecting association list): ((1 . 1) 2 (3 . 9))

     (sloppy-assoc 2 '((1 . 1) 2 (3 . 9)))
     =>
     #f

Unless you are explicitly working with badly formed association lists, it is much safer to use the non-sloppy- procedures, because they help to highlight coding and data errors that the sloppy- versions would silently cover up.

 -- Scheme Procedure: sloppy-assq key alist
 -- C Function: scm_sloppy_assq (key, alist)
     Behaves like assq but does not do any error checking. Recommended only for use in Guile internals.

 -- Scheme Procedure: sloppy-assv key alist
 -- C Function: scm_sloppy_assv (key, alist)
     Behaves like assv but does not do any error checking. Recommended only for use in Guile internals.

 -- Scheme Procedure: sloppy-assoc key alist
 -- C Function: scm_sloppy_assoc (key, alist)
     Behaves like assoc but does not do any error checking. Recommended only for use in Guile internals.

Alist Example
.............

Here is a longer example of how alists may be used in practice.

     (define capitals '(("New York" . "Albany")
                        ("Oregon"   . "Salem")
                        ("Florida"  . "Miami")))

     ;; What's the capital of Oregon?
     (assoc "Oregon" capitals)       => ("Oregon" . "Salem")
     (assoc-ref capitals "Oregon")   => "Salem"

     ;; We left out South Dakota.
     (set! capitals
           (assoc-set! capitals "South Dakota" "Pierre"))
     capitals
     => (("South Dakota" . "Pierre")
         ("New York" . "Albany")
         ("Oregon" . "Salem")
         ("Florida" . "Miami"))

     ;; And we got Florida wrong.
     (set! capitals
           (assoc-set! capitals "Florida" "Tallahassee"))
     capitals
     => (("South Dakota" . "Pierre")
         ("New York" . "Albany")
         ("Oregon" . "Salem")
         ("Florida" . "Tallahassee"))

     ;; After Oregon secedes, we can remove it.
     (set! capitals
           (assoc-remove! capitals "Oregon"))
     capitals
     => (("South Dakota" . "Pierre")
         ("New York" . "Albany")
         ("Florida" . "Tallahassee"))

Hash Tables
-----------

Hash tables are dictionaries which offer similar functionality as association lists: They provide a mapping from keys to values.  The difference is that association lists need time linear in the size of elements when searching for entries, whereas hash tables can normally search in constant time.  The drawback is that hash tables require a little bit more memory, and that you can not use the normal list procedures (see Lists) for working with them.

Hash Table Examples
...................

For demonstration purposes, this section gives a few usage examples of some hash table procedures, together with some explanation what they do.

First we start by creating a new hash table with 31 slots, and populate it with two key/value pairs.

     (define h (make-hash-table 31))

     (hashq-create-handle! h 'foo "bar")
     =>
     (foo . "bar")

     (hashq-create-handle! h 'braz "zonk")
     =>
     (braz . "zonk")

     (hashq-create-handle! h 'frob #f)
     =>
     (frob . #f)

You can get the value for a given key with the procedure hashq-ref, but the problem with this procedure is that you cannot reliably determine whether a key does exists in the table.  The reason is that the procedure returns #f if the key is not in the table, but it will return the same value if the key is in the table and just happens to have the value #f, as you can see in the following examples.

     (hashq-ref h 'foo)
     =>
     "bar"

     (hashq-ref h 'frob)
     =>
     #f

     (hashq-ref h 'not-there)
     =>
     #f

Better is to use the procedure hashq-get-handle, which makes a distinction between the two cases.  Just like assq, this procedure returns a key/value-pair on success, and #f if the key is not found.

     (hashq-get-handle h 'foo)
     =>
     (foo . "bar")

     (hashq-get-handle h 'not-there)
     =>
     #f

There is no procedure for calculating the number of key/value-pairs in a hash table, but hash-fold can be used for doing exactly that.

     (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h)
     =>
     3

Hash Table Reference
....................

Like the association list functions, the hash table functions come in several varieties, according to the equality test used for the keys. Plain hash- functions use equal?, hashq- functions use eq?, hashv- functions use eqv?, and the hashx- functions use an application supplied test.

A single make-hash-table creates a hash table suitable for use with any set of functions, but it's imperative that just one set is then used consistently, or results will be unpredictable.

Hash tables are implemented as a vector indexed by a hash value formed from the key, with an association list of key/value pairs for each bucket in case distinct keys hash together.  Direct access to the pairs in those lists is provided by the -handle- functions.

When the number of table entries goes above a threshold the vector is increased and the entries rehashed, to prevent the bucket lists becoming too long and slowing down accesses.  When the number of entries goes below a threshold the vector is decreased to save space.

For the hashx- ``extended'' routines, an application supplies a HASH function producing an integer index like hashq etc below, and an ASSOC alist search function like assq etc (see Retrieving Alist Entries).  Here's an example of such functions implementing case-insensitive hashing of string keys,

     (use-modules (srfi srfi-1)
                  (srfi srfi-13))

     (define (my-hash str size)
       (remainder (string-hash-ci str) size))
     (define (my-assoc str alist)
       (find (lambda (pair) (string-ci=? str (car pair))) alist))

     (define my-table (make-hash-table))
     (hashx-set! my-hash my-assoc my-table "foo" 123)

     (hashx-ref my-hash my-assoc my-table "FOO")
     => 123

In a hashx- HASH function the aim is to spread keys across the vector, so bucket lists don't become long.  But the actual values are arbitrary as long as they're in the range 0 to SIZE-1.  Helpful functions for forming a hash value, in addition to hashq etc below, include symbol-hash (see Symbol Keys), string-hash and string-hash-ci (see String Comparison), and char-set-hash (see Character Set Predicates/Comparison).

Note that currently, unfortunately, there's no hashx-remove! function, which rather limits the usefulness of the hashx- routines.

 -- Scheme Procedure: make-hash-table [size]
     Create a new hash table, with an optional minimum vector SIZE.

     When SIZE is given, the table vector will still grow and shrink automatically, as described above, but with SIZE as a minimum. If an application knows roughly how many entries the table will hold then it can use SIZE to avoid rehashing when initial entries are added.

 -- Scheme Procedure: hash-table? obj
 -- C Function: scm_hash_table_p (obj)
     Return #t if OBJ is a hash table.

 -- Scheme Procedure: hash-clear! table
 -- C Function: scm_hash_clear_x (table)
     Remove all items from TABLE (without triggering a resize).

 -- Scheme Procedure: hash-ref table key [dflt]
 -- Scheme Procedure: hashq-ref table key [dflt]
 -- Scheme Procedure: hashv-ref table key [dflt]
 -- Scheme Procedure: hashx-ref hash assoc table key [dflt]
 -- C Function: scm_hash_ref (table, key, dflt)
 -- C Function: scm_hashq_ref (table, key, dflt)
 -- C Function: scm_hashv_ref (table, key, dflt)
 -- C Function: scm_hashx_ref (hash, assoc, table, key, dflt)
     Lookup KEY in the given hash TABLE, and return the associated value.  If KEY is not found, return DFLT, or #f if DFLT is not given.

 -- Scheme Procedure: hash-set! table key val
 -- Scheme Procedure: hashq-set! table key val
 -- Scheme Procedure: hashv-set! table key val
 -- Scheme Procedure: hashx-set! hash assoc table key val
 -- C Function: scm_hash_set_x (table, key, val)
 -- C Function: scm_hashq_set_x (table, key, val)
 -- C Function: scm_hashv_set_x (table, key, val)
 -- C Function: scm_hashx_set_x (hash, assoc, table, key, val)
     Associate VAL with KEY in the given hash TABLE.  If KEY is already present then it's associated value is changed. If it's not present then a new entry is created.

 -- Scheme Procedure: hash-remove! table key
 -- Scheme Procedure: hashq-remove! table key
 -- Scheme Procedure: hashv-remove! table key
 -- C Function: scm_hash_remove_x (table, key)
 -- C Function: scm_hashq_remove_x (table, key)
 -- C Function: scm_hashv_remove_x (table, key)
     Remove any association for KEY in the given hash TABLE. If KEY is not in TABLE then nothing is done.

 -- Scheme Procedure: hash key size
 -- Scheme Procedure: hashq key size
 -- Scheme Procedure: hashv key size
 -- C Function: scm_hash (key, size)
 -- C Function: scm_hashq (key, size)
 -- C Function: scm_hashv (key, size)
     Return a hash value for KEY.  This is a number in the range 0 to SIZE-1, which is suitable for use in a hash table of the given SIZE.

     Note that hashq and hashv may use internal addresses of objects, so if an object is garbage collected and re-created it can have a different hash value, even when the two are notionally eq?.  For instance with symbols,

          (hashq 'something 123)   => 19
          (gc)
          (hashq 'something 123)   => 62

     In normal use this is not a problem, since an object entered into a hash table won't be garbage collected until removed.  It's only if hashing calculations are somehow separated from normal references that its lifetime needs to be considered.

 -- Scheme Procedure: hash-get-handle table key
 -- Scheme Procedure: hashq-get-handle table key
 -- Scheme Procedure: hashv-get-handle table key
 -- Scheme Procedure: hashx-get-handle hash assoc table key
 -- C Function: scm_hash_get_handle (table, key)
 -- C Function: scm_hashq_get_handle (table, key)
 -- C Function: scm_hashv_get_handle (table, key)
 -- C Function: scm_hashx_get_handle (hash, assoc, table, key)
     Return the (KEY . VALUE) pair for KEY in the given hash TABLE, or #f if KEY is not in TABLE.

 -- Scheme Procedure: hash-create-handle! table key init
 -- Scheme Procedure: hashq-create-handle! table key init
 -- Scheme Procedure: hashv-create-handle! table key init
 -- Scheme Procedure: hashx-create-handle! hash assoc table key init
 -- C Function: scm_hash_create_handle_x (table, key, init)
 -- C Function: scm_hashq_create_handle_x (table, key, init)
 -- C Function: scm_hashv_create_handle_x (table, key, init)
 -- C Function: scm_hashx_create_handle_x (hash, assoc, table, key, init)
     Return the (KEY . VALUE) pair for KEY in the given hash TABLE.  If KEY is not in TABLE then create an entry for it with INIT as the value, and return that pair.

 -- Scheme Procedure: hash-map->list proc table
 -- Scheme Procedure: hash-for-each proc table
 -- C Function: scm_hash_map_to_list (proc, table)
 -- C Function: scm_hash_for_each (proc, table)
     Apply PROC to the entries in the given hash TABLE.  Each call is (PROC KEY VALUE).  hash-map->list returns a list of the results from these calls, hash-for-each discards the results and returns an unspecified value.

     Calls are made over the table entries in an unspecified order, and for hash-map->list the order of the values in the returned list is unspecified.  Results will be unpredictable if TABLE is modified while iterating.

     For example the following returns a new alist comprising all the entries from mytable, in no particular order.

          (hash-map->list cons mytable)

 -- Scheme Procedure: hash-for-each-handle proc table
 -- C Function: scm_hash_for_each_handle (proc, table)
     Apply PROC to the entries in the given hash TABLE.  Each call is (PROC HANDLE), where HANDLE is a (KEY . VALUE) pair. Return an unspecified value.

     hash-for-each-handle differs from hash-for-each only in the argument list of PROC.

 -- Scheme Procedure: hash-fold proc init table
 -- C Function: scm_hash_fold (proc, init, table)
     Accumulate a result by applying PROC to the elements of the given hash TABLE.  Each call is (PROC KEY VALUE PRIOR-RESULT), where KEY and VALUE are from the TABLE and PRIOR-RESULT is the return from the previous PROC call.  For the first call, PRIOR-RESULT is the given INIT value.

     Calls are made over the table entries in an unspecified order. Results will be unpredictable if TABLE is modified while hash-fold is running.

     For example, the following returns a count of how many keys in mytable are strings.

          (hash-fold (lambda (key value prior)
                       (if (string? key) (1+ prior) prior))
                     0 mytable)