(Hash Table Reference): Decribe rehashing, note

[bpt/guile.git] / doc / ref / scheme-compound.texi

@page
@node Compound Data Types
@chapter Compound Data Types

This chapter describes Guile's compound data types.  By @dfn{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.

@menu
* Pairs::                       Scheme's basic building block.
* Lists::                       Special list functions supported by Guile.
* Vectors::                     One-dimensional arrays of Scheme objects.
* Records::                     
* Structures::                  
* Arrays::                      Arrays of values.
* Association Lists and Hash Tables::  Dictionary data types.
@end menu


@node Pairs
@section Pairs
@tpindex 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 @dfn{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 (@pxref{Lists}).

Pairs can literally get entered in source code or at the REPL, in the
so-called @dfn{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
@code{foo} and @code{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.

@lisp
(1 . 2)
(foo . bar)
@end lisp

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

@lisp
'(1 . 2)
@result{}
(1 . 2)
'(foo . bar)
@result{}
(foo . bar)
@end lisp

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

@rnindex cons
@deffn {Scheme Procedure} cons x y
@deffnx {C Function} scm_cons (x, y)
Return a newly allocated pair whose car is @var{x} and whose
cdr is @var{y}.  The pair is guaranteed to be different (in the
sense of @code{eq?}) from every previously existing object.
@end deffn

@rnindex pair?
@deffn {Scheme Procedure} pair? x
@deffnx {C Function} scm_pair_p (x)
Return @code{#t} if @var{x} is a pair; otherwise return
@code{#f}.
@end deffn

The two parts of a pair are traditionally called @dfn{car} and
@dfn{cdr}.  They can be retrieved with procedures of the same name
(@code{car} and @code{cdr}), and can be modified with the procedures
@code{set-car!} and @code{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 @code{caar}, @code{cadr} and so on
are also predefined.

@rnindex car
@rnindex cdr
@deffn {Scheme Procedure} car pair
@deffnx {Scheme Procedure} cdr pair
Return the car or the cdr of @var{pair}, respectively.
@end deffn

@deffn {Scheme Procedure} caar pair
@deffnx {Scheme Procedure} cadr pair @dots{}
@deffnx {Scheme Procedure} cdddar pair
@deffnx {Scheme Procedure} cddddr pair
These procedures are compositions of @code{car} and @code{cdr}, where
for example @code{caddr} could be defined by

@lisp
(define caddr (lambda (x) (car (cdr (cdr x)))))
@end lisp
@end deffn

@rnindex set-car!
@deffn {Scheme Procedure} set-car! pair value
@deffnx {C Function} scm_set_car_x (pair, value)
Stores @var{value} in the car field of @var{pair}.  The value returned
by @code{set-car!} is unspecified.
@end deffn

@rnindex set-cdr!
@deffn {Scheme Procedure} set-cdr! pair value
@deffnx {C Function} scm_set_cdr_x (pair, value)
Stores @var{value} in the cdr field of @var{pair}.  The value returned
by @code{set-cdr!} is unspecified.
@end deffn


@node Lists
@section Lists
@tpindex Lists

A very important data type in Scheme---as well as in all other Lisp
dialects---is the data type @dfn{list}.@footnote{Strictly speaking,
Scheme does not have a real datatype @dfn{list}.  Lists are made up of
@dfn{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:

@itemize @bullet
@item
Either the empty list @code{()},

@item
or a pair which has a list in its cdr.
@end itemize

@c FIXME::martin: Describe the pair chaining in more detail.

@c FIXME::martin: What is a proper, what an improper list?
@c What is a circular list?

@c FIXME::martin: Maybe steal some graphics from the Elisp reference 
@c manual?

@menu
* List Syntax::                 Writing literal lists.
* List Predicates::             Testing lists.
* List Constructors::           Creating new lists.
* List Selection::              Selecting from lists, getting their length.
* Append/Reverse::              Appending and reversing lists.
* List Modification::           Modifying existing lists.
* List Searching::              Searching for list elements
* List Mapping::                Applying procedures to lists.
@end menu

@node List Syntax
@subsection 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.@footnote{Note that there is no separation character between
the list elements, like a comma or a semicolon.}.

@lisp
(1 2 3)            ; @r{a list of the numbers 1, 2 and 3}
("foo" bar 3.1415) ; @r{a string, a symbol and a real number}
()                 ; @r{the empty list}
@end lisp

The last example needs a bit more explanation.  A list with no elements,
called the @dfn{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:

@lisp
(car '(1))
@result{}
1
(cdr '(1))
@result{}
()
@end lisp

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


@node List Predicates
@subsection 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.

@rnindex list?
@deffn {Scheme Procedure} list? x
@deffnx {C Function} scm_list_p (x)
Return @code{#t} iff @var{x} is a proper list, else @code{#f}.
@end deffn

The predicate @code{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
@code{null?}.  Then, the algorithm terminates.

@rnindex null?
@deffn {Scheme Procedure} null? x
@deffnx {C Function} scm_null_p (x)
Return @code{#t} iff @var{x} is the empty list, else @code{#f}.
@end deffn

@node List Constructors
@subsection List Constructors

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

@c  C Function scm_list(rest) used to be documented here, but it's a
@c  no-op since it does nothing but return the list the caller must
@c  have already created.
@c
@deffn {Scheme Procedure} list elem1 @dots{} elemN
@deffnx {C Function} scm_list_1 (elem1)
@deffnx {C Function} scm_list_2 (elem1, elem2)
@deffnx {C Function} scm_list_3 (elem1, elem2, elem3)
@deffnx {C Function} scm_list_4 (elem1, elem2, elem3, elem4)
@deffnx {C Function} scm_list_5 (elem1, elem2, elem3, elem4, elem5)
@deffnx {C Function} scm_list_n (elem1, @dots{}, elemN, @nicode{SCM_UNDEFINED})
@rnindex list
Return a new list containing elements @var{elem1} to @var{elemN}.

@code{scm_list_n} takes a variable number of arguments, terminated by
the special @code{SCM_UNDEFINED}.  That final @code{SCM_UNDEFINED} is
not included in the list.  None of @var{elem1} to @var{elemN} can
themselves be @code{SCM_UNDEFINED}, or @code{scm_list_n} will
terminate at that point.
@end deffn

@c  C Function scm_cons_star(arg1,rest) used to be documented here,
@c  but it's not really a useful interface, since it expects the
@c  caller to have already consed up all but the first argument
@c  already.
@c
@deffn {Scheme Procedure} cons* arg1 arg2 @dots{}
Like @code{list}, but the last arg provides the tail of the
constructed list, returning @code{(cons @var{arg1} (cons
@var{arg2} (cons @dots{} @var{argn})))}.  Requires at least one
argument.  If given one argument, that argument is returned as
result.  This function is called @code{list*} in some other
Schemes and in Common LISP.
@end deffn

@deffn {Scheme Procedure} list-copy lst
@deffnx {C Function} scm_list_copy (lst)
Return a (newly-created) copy of @var{lst}.
@end deffn

@deffn {Scheme Procedure} make-list n [init]
Create a list containing of @var{n} elements, where each element is
initialized to @var{init}.  @var{init} defaults to the empty list
@code{()} if not given.
@end deffn

Note that @code{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
@code{set-cdr!} or @code{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 @code{copy-tree} (@pxref{Copying}).

@node List Selection
@subsection List Selection

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

@rnindex length
@deffn {Scheme Procedure} length lst
@deffnx {C Function} scm_length (lst)
Return the number of elements in list @var{lst}.
@end deffn

@deffn {Scheme Procedure} last-pair lst
@deffnx {C Function} scm_last_pair (lst)
Return a pointer to the last pair in @var{lst}, signalling an error if
@var{lst} is circular.
@end deffn

@rnindex list-ref
@deffn {Scheme Procedure} list-ref list k
@deffnx {C Function} scm_list_ref (list, k)
Return the @var{k}th element from @var{list}.
@end deffn

@rnindex list-tail
@deffn {Scheme Procedure} list-tail lst k
@deffnx {Scheme Procedure} list-cdr-ref lst k
@deffnx {C Function} scm_list_tail (lst, k)
Return the "tail" of @var{lst} beginning with its @var{k}th element.
The first element of the list is considered to be element 0.

@code{list-tail} and @code{list-cdr-ref} are identical.  It may help to
think of @code{list-cdr-ref} as accessing the @var{k}th cdr of the list,
or returning the results of cdring @var{k} times down @var{lst}.
@end deffn

@deffn {Scheme Procedure} list-head lst k
@deffnx {C Function} scm_list_head (lst, k)
Copy the first @var{k} elements from @var{lst} into a new list, and
return it.
@end deffn

@node Append/Reverse
@subsection Append and Reverse

@code{append} and @code{append!} are used to concatenate two or more
lists in order to form a new list.  @code{reverse} and @code{reverse!}
return lists with the same elements as their arguments, but in reverse
order.  The procedure variants with an @code{!} 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.

@rnindex append
@deffn {Scheme Procedure} append lst1 @dots{} lstN
@deffnx {Scheme Procedure} append! lst1 @dots{} lstN
@deffnx {C Function} scm_append (lstlst)
@deffnx {C Function} scm_append_x (lstlst)
Return a list comprising all the elements of lists @var{lst1} to
@var{lstN}.

@lisp
(append '(x) '(y))          @result{}  (x y)
(append '(a) '(b c d))      @result{}  (a b c d)
(append '(a (b)) '((c)))    @result{}  (a (b) (c))
@end lisp

The last argument @var{lstN} may actually be any object; an improper
list results if the last argument is not a proper list.

@lisp
(append '(a b) '(c . d))    @result{}  (a b c . d)
(append '() 'a)             @result{}  a
@end lisp

@code{append} doesn't modify the given lists, but the return may share
structure with the final @var{lstN}.  @code{append!} modifies the
given lists to form its return.

For @code{scm_append} and @code{scm_append_x}, @var{lstlst} is a list
of the list operands @var{lst1} @dots{} @var{lstN}.  That @var{lstlst}
itself is not modified or used in the return.
@end deffn

@rnindex reverse
@deffn {Scheme Procedure} reverse lst
@deffnx {Scheme Procedure} reverse! lst [newtail]
@deffnx {C Function} scm_reverse (lst)
@deffnx {C Function} scm_reverse_x (lst, newtail)
Return a list comprising the elements of @var{lst}, in reverse order.

@code{reverse} constructs a new list, @code{reverse!} modifies
@var{lst} in constructing its return.

For @code{reverse!}, the optional @var{newtail} is appended to to the
result.  @var{newtail} isn't reversed, it simply becomes the list
tail.  For @code{scm_reverse_x}, the @var{newtail} parameter is
mandatory, but can be @code{SCM_EOL} if no further tail is required.
@end deffn

@node List Modification
@subsection List Modification

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

@deffn {Scheme Procedure} list-set! list k val
@deffnx {C Function} scm_list_set_x (list, k, val)
Set the @var{k}th element of @var{list} to @var{val}.
@end deffn

@deffn {Scheme Procedure} list-cdr-set! list k val
@deffnx {C Function} scm_list_cdr_set_x (list, k, val)
Set the @var{k}th cdr of @var{list} to @var{val}.
@end deffn

@deffn {Scheme Procedure} delq item lst
@deffnx {C Function} scm_delq (item, lst)
Return a newly-created copy of @var{lst} with elements
@code{eq?} to @var{item} removed.  This procedure mirrors
@code{memq}: @code{delq} compares elements of @var{lst} against
@var{item} with @code{eq?}.
@end deffn

@deffn {Scheme Procedure} delv item lst
@deffnx {C Function} scm_delv (item, lst)
Return a newly-created copy of @var{lst} with elements
@code{eqv?}  to @var{item} removed.  This procedure mirrors
@code{memv}: @code{delv} compares elements of @var{lst} against
@var{item} with @code{eqv?}.
@end deffn

@deffn {Scheme Procedure} delete item lst
@deffnx {C Function} scm_delete (item, lst)
Return a newly-created copy of @var{lst} with elements
@code{equal?}  to @var{item} removed.  This procedure mirrors
@code{member}: @code{delete} compares elements of @var{lst}
against @var{item} with @code{equal?}.
@end deffn

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

@deffn {Scheme Procedure} delq1! item lst
@deffnx {C Function} scm_delq1_x (item, lst)
Like @code{delq!}, but only deletes the first occurrence of
@var{item} from @var{lst}.  Tests for equality using
@code{eq?}.  See also @code{delv1!} and @code{delete1!}.
@end deffn

@deffn {Scheme Procedure} delv1! item lst
@deffnx {C Function} scm_delv1_x (item, lst)
Like @code{delv!}, but only deletes the first occurrence of
@var{item} from @var{lst}.  Tests for equality using
@code{eqv?}.  See also @code{delq1!} and @code{delete1!}.
@end deffn

@deffn {Scheme Procedure} delete1! item lst
@deffnx {C Function} scm_delete1_x (item, lst)
Like @code{delete!}, but only deletes the first occurrence of
@var{item} from @var{lst}.  Tests for equality using
@code{equal?}.  See also @code{delq1!} and @code{delv1!}.
@end deffn

@node List Searching
@subsection 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 @code{#f}, otherwise
they return the sublist whose car is equal to the search object, where
equality depends on the equality predicate used.

@rnindex memq
@deffn {Scheme Procedure} memq x lst
@deffnx {C Function} scm_memq (x, lst)
Return the first sublist of @var{lst} whose car is @code{eq?}
to @var{x} where the sublists of @var{lst} are the non-empty
lists returned by @code{(list-tail @var{lst} @var{k})} for
@var{k} less than the length of @var{lst}.  If @var{x} does not
occur in @var{lst}, then @code{#f} (not the empty list) is
returned.
@end deffn

@rnindex memv
@deffn {Scheme Procedure} memv x lst
@deffnx {C Function} scm_memv (x, lst)
Return the first sublist of @var{lst} whose car is @code{eqv?}
to @var{x} where the sublists of @var{lst} are the non-empty
lists returned by @code{(list-tail @var{lst} @var{k})} for
@var{k} less than the length of @var{lst}.  If @var{x} does not
occur in @var{lst}, then @code{#f} (not the empty list) is
returned.
@end deffn

@rnindex member
@deffn {Scheme Procedure} member x lst
@deffnx {C Function} scm_member (x, lst)
Return the first sublist of @var{lst} whose car is
@code{equal?} to @var{x} where the sublists of @var{lst} are
the non-empty lists returned by @code{(list-tail @var{lst}
@var{k})} for @var{k} less than the length of @var{lst}.  If
@var{x} does not occur in @var{lst}, then @code{#f} (not the
empty list) is returned.
@end deffn


@node List Mapping
@subsection 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.

@rnindex map
@c begin (texi-doc-string "guile" "map")
@deffn {Scheme Procedure} map proc arg1 arg2 @dots{}
@deffnx {Scheme Procedure} map-in-order proc arg1 arg2 @dots{}
@deffnx {C Function} scm_map (proc, arg1, args)
Apply @var{proc} to each element of the list @var{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
@code{map}, the order of procedure applications is not specified,
@code{map-in-order} applies the procedure from left to right to the list
elements.
@end deffn

@rnindex for-each
@c begin (texi-doc-string "guile" "for-each")
@deffn {Scheme Procedure} for-each proc arg1 arg2 @dots{}
Like @code{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.
@end deffn


@node Vectors
@section Vectors
@tpindex 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 @dfn{position} (synonymous with @dfn{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 some array
procedures operate happily on vectors (@pxref{Arrays}).

@menu
* Vector Syntax::               Read syntax for vectors.
* Vector Creation::             Dynamic vector creation and validation.
* Vector Accessors::            Accessing and modifying vector contents.
@end menu


@node Vector Syntax
@subsection 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 (@code{#}), 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.

@lisp
#(1 2 3)
#("Hello" foo #xdeadbeef)
@end lisp

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

@lisp
'#(a b c) @result{} #(a b c)
@end lisp

@node Vector Creation
@subsection 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
@code{vector} and @code{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.

@rnindex vector
@rnindex list->vector
@deffn {Scheme Procedure} vector . l
@deffnx {Scheme Procedure} list->vector l
@deffnx {C Function} scm_vector (l)
Return a newly allocated vector composed of the
given arguments.  Analogous to @code{list}.

@lisp
(vector 'a 'b 'c) @result{} #(a b c)
@end lisp
@end deffn

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

The inverse operation is @code{vector->list}:

@rnindex vector->list
@deffn {Scheme Procedure} vector->list v
@deffnx {C Function} scm_vector_to_list (v)
Return a newly allocated list composed of the elements of @var{v}.

@lisp
(vector->list '#(dah dah didah)) @result{}  (dah dah didah)
(list->vector '(dididit dah)) @result{}  #(dididit dah)
@end lisp
@end deffn

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

@rnindex make-vector
@deffn {Scheme Procedure} make-vector k [fill]
@deffnx {C Function} scm_make_vector (k, fill)
Return a newly allocated vector of @var{k} elements.  If a
second argument is given, then each position is initialized to
@var{fill}.  Otherwise the initial contents of each position is
unspecified.
@end deffn

To check whether an arbitrary Scheme value @emph{is} a vector, use the
@code{vector?} primitive:

@rnindex vector?
@deffn {Scheme Procedure} vector? obj
@deffnx {C Function} scm_vector_p (obj)
Return @code{#t} if @var{obj} is a vector, otherwise return
@code{#f}.
@end deffn


@node Vector Accessors
@subsection Accessing and Modifying Vector Contents

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

@rnindex vector-length
@deffn {Scheme Procedure} vector-length vector
@deffnx {C Function} scm_vector_length vector
Return the number of elements in @var{vector} as an exact integer.
@end deffn

@rnindex vector-ref
@deffn {Scheme Procedure} vector-ref vector k
@deffnx {C Function} scm_vector_ref vector k
Return the contents of position @var{k} of @var{vector}.
@var{k} must be a valid index of @var{vector}.
@lisp
(vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8
(vector-ref '#(1 1 2 3 5 8 13 21)
    (let ((i (round (* 2 (acos -1)))))
      (if (inexact? i)
        (inexact->exact i)
           i))) @result{} 13
@end lisp
@end deffn

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

@emph{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.

@rnindex vector-set!
@deffn {Scheme Procedure} vector-set! vector k obj
@deffnx {C Function} scm_vector_set_x vector k obj
Store @var{obj} in position @var{k} of @var{vector}.
@var{k} must be a valid index of @var{vector}.
The value returned by @samp{vector-set!} is unspecified.
@lisp
(let ((vec (vector 0 '(2 2 2 2) "Anna")))
  (vector-set! vec 1 '("Sue" "Sue"))
  vec) @result{}  #(0 ("Sue" "Sue") "Anna")
@end lisp
@end deffn

@rnindex vector-fill!
@deffn {Scheme Procedure} vector-fill! v fill
@deffnx {C Function} scm_vector_fill_x (v, fill)
Store @var{fill} in every position of @var{vector}.  The value
returned by @code{vector-fill!} is unspecified.
@end deffn

@deffn {Scheme Procedure} vector-move-left! vec1 start1 end1 vec2 start2
@deffnx {C Function} scm_vector_move_left_x (vec1, start1, end1, vec2, start2)
Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
to @var{vec2} starting at position @var{start2}.  @var{start1} and
@var{start2} are inclusive indices; @var{end1} is exclusive.

@code{vector-move-left!} copies elements in leftmost order.
Therefore, in the case where @var{vec1} and @var{vec2} refer to the
same vector, @code{vector-move-left!} is usually appropriate when
@var{start1} is greater than @var{start2}.
@end deffn

@deffn {Scheme Procedure} vector-move-right! vec1 start1 end1 vec2 start2
@deffnx {C Function} scm_vector_move_right_x (vec1, start1, end1, vec2, start2)
Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
to @var{vec2} starting at position @var{start2}.  @var{start1} and
@var{start2} are inclusive indices; @var{end1} is exclusive.

@code{vector-move-right!} copies elements in rightmost order.
Therefore, in the case where @var{vec1} and @var{vec2} refer to the
same vector, @code{vector-move-right!} is usually appropriate when
@var{start1} is less than @var{start2}.
@end deffn


@node Records
@section Records

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

@deffn {Scheme Procedure} record? obj
Return @code{#t} if @var{obj} is a record of any type and @code{#f}
otherwise.

Note that @code{record?} may be true of any Scheme value; there is no
promise that records are disjoint with other Scheme types.
@end deffn

@deffn {Scheme Procedure} make-record-type type-name field-names
Return a @dfn{record-type descriptor}, a value representing a new data
type disjoint from all others.  The @var{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 @var{field-names}
argument is a list of symbols naming the @dfn{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.
@end deffn

@deffn {Scheme Procedure} record-constructor rtd [field-names]
Return a procedure for constructing new members of the type represented
by @var{rtd}.  The returned procedure accepts exactly as many arguments
as there are symbols in the given list, @var{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 @var{field-names}
argument defaults to the list of field names in the call to
@code{make-record-type} that created the type represented by @var{rtd};
if the @var{field-names} argument is provided, it is an error if it
contains any duplicates or any symbols not in the default list.
@end deffn

@deffn {Scheme Procedure} record-predicate rtd
Return a procedure for testing membership in the type represented by
@var{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.
@end deffn

@deffn {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 @var{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
@var{field-name} in that record.  The symbol @var{field-name} must be a
member of the list of field-names in the call to @code{make-record-type}
that created the type represented by @var{rtd}.
@end deffn

@deffn {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 @var{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 @var{field-name} in that record to contain the given value.
The returned value of the modifier procedure is unspecified.  The symbol
@var{field-name} must be a member of the list of field-names in the call
to @code{make-record-type} that created the type represented by
@var{rtd}.
@end deffn

@deffn {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
@code{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
@code{record-constructor} in the call that created the constructor
procedure that created the given record.
@end deffn

@deffn {Scheme Procedure} record-type-name rtd
Return the type-name associated with the type represented by rtd.  The
returned value is @code{eqv?} to the @var{type-name} argument given in
the call to @code{make-record-type} that created the type represented by
@var{rtd}.
@end deffn

@deffn {Scheme Procedure} record-type-fields rtd
Return a list of the symbols naming the fields in members of the type
represented by @var{rtd}.  The returned value is @code{equal?} to the
field-names argument given in the call to @code{make-record-type} that
created the type represented by @var{rtd}.
@end deffn


@node Structures
@section Structures
@tpindex Structures

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

A @dfn{structure type} is a first class user-defined data type.  A
@dfn{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.

@menu
* Structure Concepts::          The structure of Structures
* Structure Layout::            Defining the layout of structure types
* Structure Basics::            make-, -ref and -set! procedures for structs
* Vtables::                     Accessing type-specific data
@end menu

@node  Structure Concepts
@subsection 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.

@itemize @bullet{}
@item @dfn{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.

@item @dfn{structural accessors}

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

@item @dfn{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.
@end itemize



@node  Structure Layout
@subsection Structure Layout

When a structure is created, a region of memory is allocated to hold its
state.  The @dfn{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:

@itemize @bullet{}
@item 'u' -- unprotected

The field holds binary data that is not GC protected.

@item 'p' -- protected

The field holds a Scheme value and is GC protected.

@item '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.
@end itemize


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:

@itemize @bullet{}
@item 'w' -- writable

The field can be read and written.

@item 'r' -- readable

The field can be read, but not written.

@item 'o' -- opaque

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

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:

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

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

@example
"prpw"
@end example

Binary fields, (fields of type "u"), hold one @dfn{word} each.  The
size of a word is a machine dependent value defined to be equal to the
value of the C expression: @code{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:

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

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:

@example
"prpW"
@end example


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:

@deffn {Scheme Procedure} make-struct-layout fields
@deffnx {C Function} scm_make_struct_layout (fields)
Return a new structure layout object.

@var{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.
@end deffn



@node Structure Basics
@subsection Structure Basics

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

@deffn {Scheme Procedure} make-struct vtable tail_array_size . init
@deffnx {C Function} scm_make_struct (vtable, tail_array_size, init)
Create a new structure.

@var{type} must be a vtable structure (@pxref{Vtables}).

@var{tail-elts} must be a non-negative integer.  If the layout
specification indicated by @var{type} includes a tail-array,
this is the number of elements allocated to that array.

The @var{init1}, @dots{} 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 @code{make-vtable-vtable}.
@end deffn

@deffn {Scheme Procedure} struct? x
@deffnx {C Function} scm_struct_p (x)
Return @code{#t} iff @var{x} is a structure object, else
@code{#f}.
@end deffn


@deffn {Scheme Procedure} struct-ref handle pos
@deffnx {Scheme Procedure} struct-set! struct n value
@deffnx {C Function} scm_struct_ref (handle, pos)
@deffnx {C Function} scm_struct_set_x (struct, n, value)
Access (or modify) the @var{n}th field of @var{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.
@end deffn



@node  Vtables
@subsection Vtables

Vtables are structures that are used to represent structure types.  Each
vtable contains a layout specification in field
@code{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
@code{vtable-offset-user} is bound to a field number.  Vtable fields
at that position or greater are user definable.

@deffn {Scheme Procedure} struct-vtable handle
@deffnx {C Function} scm_struct_vtable (handle)
Return the vtable structure that describes the type of @var{struct}.
@end deffn

@deffn {Scheme Procedure} struct-vtable? x
@deffnx {C Function} scm_struct_vtable_p (x)
Return @code{#t} iff @var{x} is a vtable structure.
@end deffn

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

@deffn {Scheme Procedure} make-vtable-vtable user_fields tail_array_size . init
@deffnx {C Function} scm_make_vtable_vtable (user_fields, tail_array_size, init)
Return a new, self-describing vtable structure.

@var{user-fields} is a string describing user defined fields of the
vtable beginning at index @code{vtable-offset-user}
(see @code{make-struct-layout}).

@var{tail-size} specifies the size of the tail-array (if any) of
this vtable.

@var{init1}, @dots{} 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 @code{make-vtable-vtable} and @code{make-struct}, and thus works as
a third optional argument to @code{make-vtable-vtable} and a fourth to
@code{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.)

@lisp
(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 @result{} #<a green ball owned by Nisse>
@end lisp
@end deffn

@deffn {Scheme Procedure} struct-vtable-name vtable
@deffnx {C Function} scm_struct_vtable_name (vtable)
Return the name of the vtable @var{vtable}.
@end deffn

@deffn {Scheme Procedure} set-struct-vtable-name! vtable name
@deffnx {C Function} scm_set_struct_vtable_name_x (vtable, name)
Set the name of the vtable @var{vtable} to @var{name}.
@end deffn

@deffn {Scheme Procedure} struct-vtable-tag handle
@deffnx {C Function} scm_struct_vtable_tag (handle)
Return the vtable tag of the structure @var{handle}.
@end deffn


@node Arrays
@section Arrays
@tpindex Arrays

@menu
* Conventional Arrays::         Arrays with arbitrary data.
* Array Mapping::               Applying a procedure to the contents of an array.
* Uniform Arrays::              Arrays with data of a single type.
* Bit Vectors::                 Vectors of bits.
@end menu

@node Conventional Arrays
@subsection Conventional Arrays

@dfn{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, and 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 @code{#} followed by the @dfn{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 number of dimensions and range of each
dimension must be specified, e.g., to create a 2x3 array with a
zero-based index:

@example
(make-array 'ho 2 3) @result{}
#2((ho ho ho) (ho ho ho))
@end example

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

@example
(make-array 'ho '(0 1) '(0 2)) @result{}
#2((ho ho ho) (ho ho ho))
@end example

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

@example
(make-array 'ho 3) @result{}
#(ho ho ho)
@end example

The following procedures can be used with conventional arrays (or vectors).

@deffn {Scheme Procedure} array? v [prot]
@deffnx {C Function} scm_array_p (v, prot)
Return @code{#t} if the @var{obj} is an array, and @code{#f} if
not.  The @var{prototype} argument is used with uniform arrays
and is described elsewhere.
@end deffn

@deffn {Scheme Procedure} make-array initial-value bound1 bound2 @dots{}
Create and return an array that has as many dimensions as there are
@var{bound}s and fill it with @var{initial-value}.  Each @var{bound}
may be a positive non-zero integer @var{N}, in which case the index for
that dimension can range from 0 through @var{N-1}; or an explicit index
range specifier in the form @code{(LOWER UPPER)}, where both @var{lower}
and @var{upper} are integers, possibly less than zero, and possibly the
same number (however, @var{lower} cannot be greater than @var{upper}).
@end deffn

@c array-ref's type is `compiled-closure'.  There's some weird stuff
@c going on in array.c, too.  Let's call it a primitive. -twp

@deffn {Scheme Procedure} uniform-vector-ref v args
@deffnx {Scheme Procedure} array-ref v . args
@deffnx {C Function} scm_uniform_vector_ref (v, args)
Return the element at the @code{(index1, index2)} element in
@var{array}.
@end deffn

@deffn {Scheme Procedure} array-in-bounds? v . args
@deffnx {C Function} scm_array_in_bounds_p (v, args)
Return @code{#t} if its arguments would be acceptable to
@code{array-ref}.
@end deffn

@c fixme: why do these sigs differ?  -ttn 2001/07/19 01:14:12
@deffn {Scheme Procedure} array-set! v obj . args
@deffnx {Scheme Procedure} uniform-array-set1! v obj args
@deffnx {C Function} scm_array_set_x (v, obj, args)
Set the element at the @code{(index1, index2)} element in @var{array} to
@var{new-value}.  The value returned by array-set! is unspecified.
@end deffn

@deffn {Scheme Procedure} make-shared-array oldra mapfunc . dims
@deffnx {C Function} scm_make_shared_array (oldra, mapfunc, dims)
@code{make-shared-array} can be used to create shared subarrays of other
arrays.  The @var{mapper} is a function that translates coordinates in
the new array into coordinates in the old array.  A @var{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:
@lisp
(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) @result{} foo
(define freds-center
  (make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j))) 2 2))
(array-ref freds-center 0 0) @result{} foo
@end lisp
@end deffn

@deffn {Scheme Procedure} shared-array-increments ra
@deffnx {C Function} scm_shared_array_increments (ra)
For each dimension, return the distance between elements in the root vector.
@end deffn

@deffn {Scheme Procedure} shared-array-offset ra
@deffnx {C Function} scm_shared_array_offset (ra)
Return the root vector index of the first element in the array.
@end deffn

@deffn {Scheme Procedure} shared-array-root ra
@deffnx {C Function} scm_shared_array_root (ra)
Return the root vector of a shared array.
@end deffn

@deffn {Scheme Procedure} transpose-array ra . args
@deffnx {C Function} scm_transpose_array (ra, args)
Return an array sharing contents with @var{array}, but with
dimensions arranged in a different order.  There must be one
@var{dim} argument for each dimension of @var{array}.
@var{dim0}, @var{dim1}, @dots{} 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 @var{dim0}, @var{dim1}, @dots{} correspond to
dimensions in the array to be returned, their positions in the
argument list to dimensions of @var{array}.  Several @var{dim}s
may have the same value, in which case the returned array will
have smaller rank than @var{array}.

@lisp
(transpose-array '#2((a b) (c d)) 1 0) @result{} #2((a c) (b d))
(transpose-array '#2((a b) (c d)) 0 0) @result{} #1(a d)
(transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) @result{}
                #2((a 4) (b 5) (c 6))
@end lisp
@end deffn

@deffn {Scheme Procedure} enclose-array ra . axes
@deffnx {C Function} scm_enclose_array (ra, axes)
@var{dim0}, @var{dim1} @dots{} should be nonnegative integers less than
the rank of @var{array}.  @var{enclose-array} returns an array
resembling an array of shared arrays.  The dimensions of each shared
array are the same as the @var{dim}th 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 @var{dim}.

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

examples:
@lisp
(enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1) @result{}
   #<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) @result{}
   #<enclosed-array #2((a 1) (d 4)) #2((b 2) (e 5)) #2((c 3) (f 6))>
@end lisp
@end deffn

@deffn {Scheme Procedure} array-shape array
Return a list of inclusive bounds of integers.
@example
(array-shape (make-array 'foo '(-1 3) 5)) @result{} ((-1 3) (0 4))
@end example
@end deffn

@deffn {Scheme Procedure} array-dimensions ra
@deffnx {C Function} scm_array_dimensions (ra)
@code{Array-dimensions} is similar to @code{array-shape} but replaces
elements with a @code{0} minimum with one greater than the maximum. So:
@lisp
(array-dimensions (make-array 'foo '(-1 3) 5)) @result{} ((-1 3) 5)
@end lisp
@end deffn

@deffn {Scheme Procedure} array-rank ra
@deffnx {C Function} scm_array_rank (ra)
Return the number of dimensions of @var{obj}.  If @var{obj} is
not an array, @code{0} is returned.
@end deffn

@deffn {Scheme Procedure} array->list v
@deffnx {C Function} scm_array_to_list (v)
Return a list consisting of all the elements, in order, of
@var{array}.
@end deffn

@deffn {Scheme Procedure} array-copy! src dst
@deffnx {Scheme Procedure} array-copy-in-order! src dst
@deffnx {C Function} scm_array_copy_x (src, dst)
Copy every element from vector or array @var{source} to the
corresponding element of @var{destination}.  @var{destination} must have
the same rank as @var{source}, and be at least as large in each
dimension.  The order is unspecified.
@end deffn

@deffn {Scheme Procedure} array-fill! ra fill
@deffnx {C Function} scm_array_fill_x (ra, fill)
Store @var{fill} in every element of @var{array}.  The value returned
is unspecified.
@end deffn

@c begin (texi-doc-string "guile" "array-equal?")
@deffn {Scheme Procedure} array-equal? ra0 ra1
Return @code{#t} iff all arguments are arrays with the same shape, the
same type, and have corresponding elements which are either
@code{equal?}  or @code{array-equal?}.  This function differs from
@code{equal?} in that a one dimensional shared array may be
@var{array-equal?} but not @var{equal?} to a vector or uniform vector.
@end deffn

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

If the optional argument @var{strict} is provided, a shared array will
be returned only if its elements are stored internally contiguous in
memory.
@end deffn

@node Array Mapping
@subsection Array Mapping

@c  FIXME: array-map! accepts no source arrays at all, and in that
@c  case makes calls "(proc)".  Is that meant to be a documented
@c  feature?
@c
@c  FIXME: array-for-each doesn't say what happens if the sources have
@c  different index ranges.  The code currently iterates over the
@c  indices of the first and expects the others to cover those.  That
@c  at least vaguely matches array-map!, but is is meant to be a
@c  documented feature?

@deffn {Scheme Procedure} array-map! dst proc src1 @dots{} srcN
@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
@deffnx {C Function} scm_array_map_x (dst, proc, srclist)
Set each element of the @var{dst} array to values obtained from calls
to @var{proc}.  The value returned is unspecified.

Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})},
where each @var{elem} is from the corresponding @var{src} array, at
the @var{dst} index.  @code{array-map-in-order!} makes the calls in
row-major order, @code{array-map!} makes them in an unspecified order.

The @var{src} arrays must have the same number of dimensions as
@var{dst}, and must have a range for each dimension which covers the
range in @var{dst}.  This ensures all @var{dst} indices are valid in
each @var{src}.
@end deffn

@deffn {Scheme Procedure} array-for-each proc src1 @dots{} srcN
@deffnx {C Function} scm_array_for_each (proc, src1, srclist)
Apply @var{proc} to each tuple of elements of @var{src1} @dots{}
@var{srcN}, in row-major order.  The value returned is unspecified.
@end deffn

@deffn {Scheme Procedure} array-index-map! dst proc
@deffnx {C Function} scm_array_index_map_x (dst, proc)
Set each element of the @var{dst} array to values returned by calls to
@var{proc}.  The value returned is unspecified.

Each call is @code{(@var{proc} @var{i1} @dots{} @var{iN})}, where
@var{i1}@dots{}@var{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 @m{4\times4, 4x4} matrix representing a
cyclic group,

@tex
\advance\leftskip by 2\lispnarrowing {
$\left(\matrix{%
0 & 1 & 2 & 3 \cr
1 & 2 & 3 & 0 \cr
2 & 3 & 0 & 1 \cr
3 & 0 & 1 & 2 \cr
}\right)$} \par
@end tex
@ifnottex
@example
    / 0 1 2 3 \
    | 1 2 3 0 |
    | 2 3 0 1 |
    \ 3 0 1 2 /
@end example
@end ifnottex

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

@node Uniform Arrays
@subsection Uniform Arrays
@tpindex Uniform Arrays

@noindent
@dfn{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 @dfn{uniform vectors}.  The procedures in
this section can also be used on conventional arrays, vectors,
bit-vectors and strings.

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

@example
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
@end example

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

@example
(make-uniform-array #\a 3) @result{}
"aaa"
@end example

@noindent
Unshared uniform arrays of booleans with a single zero-based dimension
are identical to @ref{Bit Vectors, bit-vectors}.

@example
(make-uniform-array #t 3) @result{}
#*111
@end example

@noindent
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
@code{#} and @code{(}.  For example, a uniform vector of signed
long integers is displayed in the form @code{'#e(3 5 9)}.

@deffn {Scheme Procedure} array? v [prot]
Return @code{#t} if the @var{obj} is an array, and @code{#f} if not.

The @var{prototype} argument is used with uniform arrays and is described
elsewhere.
@end deffn

@deffn {Scheme Procedure} make-uniform-array prototype bound1 bound2 @dots{}
Create and return a uniform array of type corresponding to
@var{prototype} that has as many dimensions as there are @var{bound}s
and fill it with @var{prototype}.
@end deffn

@deffn {Scheme Procedure} array-prototype ra
@deffnx {C Function} scm_array_prototype (ra)
Return an object that would produce an array of the same type
as @var{array}, if used as the @var{prototype} for
@code{make-uniform-array}.
@end deffn

@deffn {Scheme Procedure} list->uniform-array ndim prot lst
@deffnx {Scheme Procedure} list->uniform-vector prot lst
@deffnx {C Function} scm_list_to_uniform_array (ndim, prot, lst)
Return a uniform array of the type indicated by prototype
@var{prot} with elements the same as those of @var{lst}.
Elements must be of the appropriate type, no coercions are
done.
@end deffn

@deffn {Scheme Procedure} uniform-vector-fill! uve fill
Store @var{fill} in every element of @var{uve}.  The value returned is
unspecified.
@end deffn

@deffn {Scheme Procedure} uniform-vector-length v
@deffnx {C Function} scm_uniform_vector_length (v)
Return the number of elements in @var{uve}.
@end deffn

@deffn {Scheme Procedure} dimensions->uniform-array dims prot [fill]
@deffnx {Scheme Procedure} make-uniform-vector length prototype [fill]
@deffnx {C Function} scm_dimensions_to_uniform_array (dims, prot, fill)
Create and return a uniform array or vector of type
corresponding to @var{prototype} with dimensions @var{dims} or
length @var{length}.  If @var{fill} is supplied, it's used to
fill the array, otherwise @var{prototype} is used.
@end deffn

@c Another compiled-closure. -twp

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

The optional arguments @var{start} and @var{end} allow
a specified region of a vector (or linearized array) to be read,
leaving the remainder of the vector unchanged.

@code{uniform-array-read!} returns the number of objects read.
@var{port-or-fdes} may be omitted, in which case it defaults to the value
returned by @code{(current-input-port)}.
@end deffn

@deffn {Scheme Procedure} uniform-array-write v [port_or_fd [start [end]]]
@deffnx {Scheme Procedure} uniform-vector-write uve [port-or-fdes] [start] [end]
@deffnx {C Function} scm_uniform_array_write (v, port_or_fd, start, end)
Writes all elements of @var{ura} as binary objects to
@var{port-or-fdes}.

The optional arguments @var{start}
and @var{end} allow
a specified region of a vector (or linearized array) to be written.

The number of objects actually written is returned.
@var{port-or-fdes} may be
omitted, in which case it defaults to the value returned by
@code{(current-output-port)}.
@end deffn

@node Bit Vectors
@subsection Bit Vectors

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

@noindent
They are displayed as a sequence of @code{0}s and
@code{1}s prefixed by @code{#*}, e.g.,

@example
(make-uniform-vector 8 #t #f) @result{}
#*00000000

#b(#t #f #t) @result{}
#*101
@end example

@deffn {Scheme Procedure} bit-count b bitvector
@deffnx {C Function} scm_bit_count (b, bitvector)
Return the number of occurrences of the boolean @var{b} in
@var{bitvector}.
@end deffn

@deffn {Scheme Procedure} bit-position item v k
@deffnx {C Function} scm_bit_position (item, v, k)
Return the minimum index of an occurrence of @var{bool} in
@var{bv} which is at least @var{k}.  If no @var{bool} occurs
within the specified range @code{#f} is returned.
@end deffn

@deffn {Scheme Procedure} bit-invert! v
@deffnx {C Function} scm_bit_invert_x (v)
Modify @var{bv} by replacing each element with its negation.
@end deffn

@deffn {Scheme Procedure} bit-set*! v kv obj
@deffnx {C Function} scm_bit_set_star_x (v, kv, obj)
If uve is a bit-vector @var{bv} and uve must be of the same
length.  If @var{bool} is @code{#t}, uve is OR'ed into
@var{bv}; If @var{bool} is @code{#f}, the inversion of uve is
AND'ed into @var{bv}.

If uve is a unsigned long integer vector all the elements of uve
must be between 0 and the @code{length} of @var{bv}.  The bits
of @var{bv} corresponding to the indexes in uve are set to
@var{bool}.  The return value is unspecified.
@end deffn

@deffn {Scheme Procedure} bit-count* v kv obj
@deffnx {C Function} scm_bit_count_star (v, kv, obj)
Return
@lisp
(bit-count (bit-set*! (if bool bv (bit-invert! bv)) uve #t) #t).
@end lisp
@var{bv} is not modified.
@end deffn


@node Association Lists and Hash Tables
@section Association Lists and Hash Tables

This chapter discusses dictionary objects: data structures that are
useful for organizing and indexing large bodies of information.

@menu
* Dictionary Types::            About dictionary types; what they're good for.
* Association Lists::           List-based dictionaries.
* Hash Tables::                 Table-based dictionaries.
@end menu

@node Dictionary Types
@subsection Dictionary Types

A @dfn{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. @code{(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 @dfn{association list} (or @dfn{alist} for short) is a list of
key-value pairs.  Each pair represents a single quantity or
object; the @code{car} of the pair is a key which is used to
identify the object, and the @code{cdr} is the object's value.

A @dfn{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, @dfn{car}, @dfn{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.

@node Association Lists
@subsection Association Lists
@tpindex Association Lists
@tpindex Alist

@cindex Association List
@cindex Alist
@cindex Database

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 @dfn{key} of each entry is
the @code{car} of the pair and the @dfn{value} of each entry is the
@code{cdr}.

@example
ASSOCIATION LIST ::=  '( (KEY1 . VALUE1)
                         (KEY2 . VALUE2)
                         (KEY3 . VALUE3)
                         @dots{}
                       )
@end example

@noindent
Association lists are also known, for short, as @dfn{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 @code{cons}, @code{car},
@code{cdr}, @code{set-car!}, @code{set-cdr!} and so on.  However,
because association lists are so useful, Guile also provides specific
procedures for manipulating them.

@menu
* Alist Key Equality::
* Adding or Setting Alist Entries::
* Retrieving Alist Entries::
* Removing Alist Entries::
* Sloppy Alist Functions::
* Alist Example::
@end menu

@node Alist Key Equality
@subsubsection Alist Key Equality

All of Guile's dedicated association list procedures, apart from
@code{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.

@itemize @bullet
@item
Procedures with @dfn{assq} in their name use @code{eq?} to determine key
equality.

@item
Procedures with @dfn{assv} in their name use @code{eqv?} to determine
key equality.

@item
Procedures with @dfn{assoc} in their name use @code{equal?} to
determine key equality.
@end itemize

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

@node Adding or Setting Alist Entries
@subsubsection Adding or Setting Alist Entries

@code{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 @code{acons}
procedure call.  So the specified alist is not modified, but its
contents become shared with the tail of the combined alist that
@code{acons} returns.

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

@example
(set! address-list (acons name address address-list))
@end example

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

Note that @code{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 @code{acons} is
ideal for building alists where there is no concept of key uniqueness.

@example
(set! task-list (acons 3 "pay gas bill" '()))
task-list
@result{}
((3 . "pay gas bill"))

(set! task-list (acons 3 "tidy bedroom" task-list))
task-list
@result{}
((3 . "tidy bedroom") (3 . "pay gas bill"))
@end example

@code{assq-set!}, @code{assv-set!} and @code{assoc-set!} are used to add
or replace an entry in an association list where there @emph{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.

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

@example
address-list
@result{}
(("mary" . "34 Elm Road") ("james" . "16 Bow Street"))

(assoc-set! address-list "james" "1a London Road")
@result{}
(("mary" . "34 Elm Road") ("james" . "1a London Road"))

address-list
@result{}
(("mary" . "34 Elm Road") ("james" . "1a London Road"))
@end example

Or they may not:

@example
(assoc-set! address-list "bob" "11 Newington Avenue")
@result{}
(("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
 ("james" . "1a London Road"))

address-list
@result{}
(("mary" . "34 Elm Road") ("james" . "1a London Road"))
@end example

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

@example
(set! address-list
      (assoc-set! address-list "bob" "11 Newington Avenue"))
address-list
@result{}
(("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
 ("james" . "1a London Road"))
@end example

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
@code{acons}, @code{assq-set!}, @code{assv-set!} or @code{assoc-set!},
use @code{list-copy} to copy the old association list before modifying
it.

@deffn {Scheme Procedure} acons key value alist
@deffnx {C Function} scm_acons (key, value, alist)
Add a new key-value pair to @var{alist}.  A new pair is
created whose car is @var{key} and whose cdr is @var{value}, and the
pair is consed onto @var{alist}, and the new list is returned.  This
function is @emph{not} destructive; @var{alist} is not modified.
@end deffn

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

These functions do not attempt to verify the structure of @var{alist},
and so may cause unusual results if passed an object that is not an
association list.
@end deffn

@node Retrieving Alist Entries
@subsubsection Retrieving Alist Entries
@rnindex assq
@rnindex assv
@rnindex assoc

@code{assq}, @code{assv} and @code{assoc} take an alist and a key as
arguments and return the entry for that key if an entry exists, or
@code{#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 @code{(KEY . VALUE)}, not just the value.

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

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

This creates an ambiguity: if the return value is @code{#f}, it means
either that there is no entry with the specified key, or that there
@emph{is} an entry for the specified key, with value @code{#f}.
Consequently, @code{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.

@deffn {Scheme Procedure} assq-ref alist key
@deffnx {Scheme Procedure} assv-ref alist key
@deffnx {Scheme Procedure} assoc-ref alist key
@deffnx {C Function} scm_assq_ref (alist, key)
@deffnx {C Function} scm_assv_ref (alist, key)
@deffnx {C Function} scm_assoc_ref (alist, key)
Like @code{assq}, @code{assv} and @code{assoc}, except that only the
value associated with @var{key} in @var{alist} is returned.  These
functions are equivalent to

@lisp
(let ((ent (@var{associator} @var{key} @var{alist})))
  (and ent (cdr ent)))
@end lisp

where @var{associator} is one of @code{assq}, @code{assv} or @code{assoc}.
@end deffn

@node Removing Alist Entries
@subsubsection Removing Alist Entries

To remove the element from an association list whose key matches a
specified key, use @code{assq-remove!}, @code{assv-remove!} or
@code{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 @code{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 @code{set!} it to the value that
@code{assq-remove!} and friends return.

@example
address-list
@result{}
(("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
 ("james" . "1a London Road"))

(set! address-list (assoc-remove! address-list "mary"))
address-list
@result{}
(("bob" . "11 Newington Avenue") ("james" . "1a London Road"))
@end example

Note that, when @code{assq/v/oc-remove!} is used to modify an
association list that has been constructed only using the corresponding
@code{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 @code{assq/v/oc-remove!} is applied to an association
list that has been constructed using @code{acons}, or an
@code{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:

@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
@result{}
(("mary" . "57 Pine Drive") ("mary" . "11 Elm Street"))

(set! address-list (assoc-remove! address-list "mary"))
address-list
@result{}
(("mary" . "11 Elm Street"))
@end example

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

@deffn {Scheme Procedure} assq-remove! alist key
@deffnx {Scheme Procedure} assv-remove! alist key
@deffnx {Scheme Procedure} assoc-remove! alist key
@deffnx {C Function} scm_assq_remove_x (alist, key)
@deffnx {C Function} scm_assv_remove_x (alist, key)
@deffnx {C Function} scm_assoc_remove_x (alist, key)
Delete the first entry in @var{alist} associated with @var{key}, and return
the resulting alist.
@end deffn

@node Sloppy Alist Functions
@subsubsection Sloppy Alist Functions

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

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

@example
(assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
@result{}
ERROR: In procedure assoc in expression (assoc "mary" (quote #)):
ERROR: Wrong type argument in position 2 (expecting NULLP): "open sesame"
ABORT: (wrong-type-arg)

(sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
@result{}
#f
@end example

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

@example
(assoc 2 '((1 . 1) 2 (3 . 9)))
@result{}
ERROR: In procedure assoc in expression (assoc 2 (quote #)):
ERROR: Wrong type argument in position 2 (expecting CONSP): 2
ABORT: (wrong-type-arg)

(sloppy-assoc 2 '((1 . 1) 2 (3 . 9)))
@result{}
#f
@end example

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

@deffn {Scheme Procedure} sloppy-assq key alist
@deffnx {C Function} scm_sloppy_assq (key, alist)
Behaves like @code{assq} but does not do any error checking.
Recommended only for use in Guile internals.
@end deffn

@deffn {Scheme Procedure} sloppy-assv key alist
@deffnx {C Function} scm_sloppy_assv (key, alist)
Behaves like @code{assv} but does not do any error checking.
Recommended only for use in Guile internals.
@end deffn

@deffn {Scheme Procedure} sloppy-assoc key alist
@deffnx {C Function} scm_sloppy_assoc (key, alist)
Behaves like @code{assoc} but does not do any error checking.
Recommended only for use in Guile internals.
@end deffn

@node Alist Example
@subsubsection Alist Example

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

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

;; What's the capital of Oregon?
(assoc "Oregon" capitals)       @result{} ("Oregon" . "Salem")
(assoc-ref capitals "Oregon")   @result{} "Salem"

;; We left out South Dakota.
(set! capitals
      (assoc-set! capitals "South Dakota" "Pierre"))
capitals
@result{} (("South Dakota" . "Pierre")
    ("New York" . "Albany")
    ("Oregon" . "Salem")
    ("Florida" . "Miami"))

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

;; After Oregon secedes, we can remove it.
(set! capitals
      (assoc-remove! capitals "Oregon"))
capitals
@result{} (("South Dakota" . "Pierre")
    ("New York" . "Albany")
    ("Florida" . "Tallahassee"))
@end lisp

@node Hash Tables
@subsection Hash Tables
@tpindex Hash Tables

@c FIXME::martin: Review me!

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 (@pxref{Lists}) for working with them.

@menu
* Hash Table Examples::         Demonstration of hash table usage.
* Hash Table Reference::        Hash table procedure descriptions.
@end menu


@node Hash Table Examples
@subsubsection Hash Table Examples

@c FIXME::martin: Review me!

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.

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

(hashq-create-handle! h 'foo "bar")
@result{}
(foo . "bar")

(hashq-create-handle! h 'braz "zonk")
@result{}
(braz . "zonk")

(hashq-create-handle! h 'frob #f)
@result{}
(frob . #f)
@end lisp

You can get the value for a given key with the procedure
@code{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 @code{#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 @code{#f}, as you can see in
the following examples.

@lisp
(hashq-ref h 'foo)
@result{}
"bar"

(hashq-ref h 'frob)
@result{}
#f

(hashq-ref h 'not-there)
@result{}
#f
@end lisp

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

@lisp
(hashq-get-handle h 'foo)
@result{}
(foo . "bar")

(hashq-get-handle h 'not-there)
@result{}
#f
@end lisp

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

@lisp
(hash-fold (lambda (key value seed) (+ 1 seed)) 0 h)
@result{}
3
@end lisp

@node Hash Table Reference
@subsubsection Hash Table Reference

@c  FIXME: Describe in broad terms what happens for resizing, and what
@c  the initial size means for this.

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

A single @code{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.

@sp 1
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 @code{-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.

@sp 1
For the @code{hashx-} ``extended'' routines, an application supplies a
@var{hash} function producing an integer index like @code{hashq} etc
below, and an @var{assoc} alist search function like @code{assq} etc
(@pxref{Retrieving Alist Entries}).  Here's an example of such
functions implementing case-insensitive hashing of string keys,

@example
(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")
@result{} 123
@end example

In a @code{hashx-} @var{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
@math{@var{size}-1}.  Helpful functions for forming a hash value, in
addition to @code{hashq} etc below, include @code{symbol-hash}
(@pxref{Symbol Keys}), @code{string-hash} and @code{string-hash-ci}
(@pxref{SRFI-13 Comparison}), and @code{char-set-hash} (@pxref{SRFI-14
Predicates/Comparison}).

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

@sp 1
@deffn {Scheme Procedure} make-hash-table [size]
Create a new hash table, with an optional minimum vector @var{size}.

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

@deffn {Scheme Procedure} hash-ref table key [dflt]
@deffnx {Scheme Procedure} hashq-ref table key [dflt]
@deffnx {Scheme Procedure} hashv-ref table key [dflt]
@deffnx {Scheme Procedure} hashx-ref hash assoc table key [dflt]
@deffnx {C Function} scm_hash_ref (table, key, dflt)
@deffnx {C Function} scm_hashq_ref (table, key, dflt)
@deffnx {C Function} scm_hashv_ref (table, key, dflt)
@deffnx {C Function} scm_hashx_ref (hash, assoc, table, key, dflt)
Lookup @var{key} in the given hash @var{table}, and return the
associated value.  If @var{key} is not found, return @var{dflt}, or
@code{#f} if @var{dflt} is not given.  (For the C functions,
@var{dflt} must be given.)
@end deffn

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

@deffn {Scheme Procedure} hash-remove! table key
@deffnx {Scheme Procedure} hashq-remove! table key
@deffnx {Scheme Procedure} hashv-remove! table key
@deffnx {C Function} scm_hash_remove_x (table, key)
@deffnx {C Function} scm_hashq_remove_x (table, key)
@deffnx {C Function} scm_hashv_remove_x (table, key)
Remove any association for @var{key} in the given hash @var{table}.
If @var{key} is not in @var{table} then nothing is done.
@end deffn

@deffn {Scheme Procedure} hash key size
@deffnx {Scheme Procedure} hashq key size
@deffnx {Scheme Procedure} hashv key size
@deffnx {C Function} scm_hash (key, size)
@deffnx {C Function} scm_hashq (key, size)
@deffnx {C Function} scm_hashv (key, size)
Return a hash value for @var{key}.  This is a number in the range
@math{0} to @math{@var{size}-1}, which is suitable for use in a hash
table of the given @var{size}.

Note that @code{hashq} and @code{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
@code{eq?}.  For instance with symbols,

@example
(hashq 'something 123)   @result{} 19
(gc)
(hashq 'something 123)   @result{} 62
@end example

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.
@end deffn

@deffn {Scheme Procedure} hash-get-handle table key
@deffnx {Scheme Procedure} hashq-get-handle table key
@deffnx {Scheme Procedure} hashv-get-handle table key
@deffnx {Scheme Procedure} hashx-get-handle hash assoc table key
@deffnx {C Function} scm_hash_get_handle (table, key)
@deffnx {C Function} scm_hashq_get_handle (table, key)
@deffnx {C Function} scm_hashv_get_handle (table, key)
@deffnx {C Function} scm_hashx_get_handle (hash, assoc, table, key)
Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
given hash @var{table}, or @code{#f} if @var{key} is not in
@var{table}.
@end deffn

@deffn {Scheme Procedure} hash-create-handle! table key init
@deffnx {Scheme Procedure} hashq-create-handle! table key init
@deffnx {Scheme Procedure} hashv-create-handle! table key init
@deffnx {Scheme Procedure} hashx-create-handle! hash assoc table key init
@deffnx {C Function} scm_hash_create_handle_x (table, key, init)
@deffnx {C Function} scm_hashq_create_handle_x (table, key, init)
@deffnx {C Function} scm_hashv_create_handle_x (table, key, init)
@deffnx {C Function} scm_hashx_create_handle_x (hash, assoc, table, key, init)
Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
given hash @var{table}.  If @var{key} is not in @var{table} then
create an entry for it with @var{init} as the value, and return that
pair.
@end deffn

@deffn {Scheme Procedure} hash-map proc table
@deffnx {Scheme Procedure} hash-for-each proc table
@deffnx {C Function} scm_hash_map (proc, table)
@deffnx {C Function} scm_hash_for_each (proc, table)
Apply @var{proc} to the entries in the given hash @var{table}.  Each
call is @code{(@var{proc} @var{key} @var{value})}.  @code{hash-map}
returns a list of the results from these calls, @code{hash-for-each}
discards the results and returns an unspecified value.

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

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

@example
(hash-map cons mytable)
@end example
@end deffn

@deffn {Scheme Procedure} hash-fold proc init table
@deffnx {C Function} scm_hash_fold (proc, init, table)
Accumulate a result by applying @var{proc} to the elements of the
given hash @var{table}.  Each call is @code{(@var{proc} @var{key}
@var{value} @var{prior-result})}, where @var{key} and @var{value} are
from the @var{table} and @var{prior-result} is the return from the
previous @var{proc} call.  For the first call, @var{prior-result} is
the given @var{init} value.

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

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

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


@c Local Variables:
@c TeX-master: "guile.texi"
@c End: