-
0.6 Data Structures in Axiom
-
-
-
This chapter is an overview of some of the data structures provided
-by Axiom.
-
-
-
-
-
-
0.6.1 Lists
-
-
-
The Axiom List type constructor is used to create homogenous lists of
-finite size. The notation for lists and the names of the functions that
-operate over them are similar to those found in functional languages such
-as ML.
-
-
-
-
Lists can be created by placing a comma separated list of values inside
-square brackets or if a list with just one element is desired then the
-function list is available:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
The function append takes two lists as arguments and returns the list
-consisting of the second argument appended to the first. A single element
-can be added to the front of a list using cons:
-
-
-
-
-
-
-
-
append([1,2,3,5],[7,11])
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
cons(23,[65,42,19])
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
Lists are accessed sequentially so if Axiom is asked for the value of the
-twentieth element in the list it will move from the start of the list over
-nineteen elements before it reaches the desired element. Each element of a
-list is stored as a node consisting of the value of the element and a pointer
-to the rest of the list. As a result the two main operations on a list are
-called first and rest. Both of these functions take a second
-optional argument which specifies the length of the first part of the list:
-
-
-
-
-
-
-
-
first([1,5,6,2,3])
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
first([1,5,6,2,3],2)
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
rest([1,5,6,2,3],2)
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
Other functions are empty? which tests to see if a list contains no
-elements, member? which tests to see if the first argument is a member
-of the second, reverse which reverses the order of the list, sort
-which sorts a list, and removeDuplicates which removes any duplicates.
-The length of a list can be obtained using the `` #'' operator.
-
-
-
-
-
-
-
-
empty?([7,2,-1,2])
-
-
-
-
-
-
-
-
-
-
-Type: Boolean
-
-
-
-
-
-
-
-
-
member?(-1,[7,2,-1,2])
-
-
-
-
-
-
-
-
-
-
-Type: Boolean
-
-
-
-
-
-
-
-
-
reverse([7,2,-1,2])
-
-
-
-
-
-
-
-
-
-
-Type: List Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List Integer
-
-
-
-
-
-
-
-
-
removeDuplicates([1,5,3,5,1,1,2])
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
Lists in Axiom are mutable and so their contents (the elements and the links)
-can be modified in place. Functions that operator over lists in this way have
-names ending in the symbol ``!''. For example, concat! takes two lists
-as arguments and appends the second argument to the first (except when the
-first argument is an empty list) and setrest! changes the link
-emanating from the first argument to point to the second argument:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
concat!(u,[1,5,42]); u
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
endOfu := rest(u,4)
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
partOfu := rest(u,2)
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
setrest!(endOfu,partOfu); u
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
From this it can be seen that the lists returned by first and rest
-are pointers to the original list and not a copy. Thus great care must
-be taken when dealing with lists in Axiom.
-
-
-
-
Although the nth element of the list l can be obtained by
-applying the first function to applications of rest
-to l, Axiom provides a more useful access method in the form of
-the ``.'' operator:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
first rest rest u -- Same as u.3
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
The operation u.i is referred to as indexing into u or
-elting into u. The latter term comes from the elt function
-which is used to extract elements (the first element of the list is at
-index ).
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
If a list has no cycles then any attempt to access an element beyond the
-end of the list will generate an error. However, in the example above there
-was a cycle starting at the third element so the access to the sixth
-element wrapped around to give the third element. Since lists are mutable it
-is possible to modify elements directly:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
Other list operations are:
-
-
-
-
-
-
-
L := [9,3,4,7]; #L
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
Note that using the `` #'' operator on a list with cycles causes Axiom to
-enter an infinite loop.
-
-
-
-
Note that any operation on a list L that returns a list
-will, in general, be such that any changes to will have the
-side-effect of altering L. For example:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
Thus the only save way of copying lists is to copy each element from one to
-another and not use the assignment operator:
-
-
-
-
-
-
-
-
p := [i for i in n] -- Same as `p := copy(n)'
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
In the previous example a new way of constructing lists was given. This is
-a powerful method which gives the reader more information about the contents
-of the list than before and which is extremely flexible. The example
-
-
-
-
-
-
-
-
[i for i in 1..10]
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
should be read as
-
-
-
-
-
-
-
-
-
``Using the expression i, generate each element of the list by
-iterating the symbol i over the range of integers [1,10]''
-
-
-
-
-
-
-
-
-
To generate the list of the squares of the first ten elements we just use:
-
-
-
-
-
-
-
-
[i**2 for i in 1..10]
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
For more complex lists we can apply a condition to the elements that are to
-be placed into the list to obtain a list of even numbers between 0 and 11:
-
-
-
-
-
-
-
-
[i for i in 1..10 | even?(i)]
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
This example should be read as:
-
-
-
-
-
-
-
-
``Using the expression i, generate each element of the list
-by iterating the symbol i over the range of integers [1,10] such that
-i is even''
-
-
-
-
-
-
-
-
-
The following achieves the same result:
-
-
-
-
-
-
-
-
[i for i in 2..10 by 2]
-
-
-
-
-
-
-
-
-
-
-Type: List PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
0.6.2 Segmented Lists
-
-
-
A segmented list is one in which some of the elements are ranges of values.
-The expand function converts lists of this type into ordinary lists:
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List Segment PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: List Segment PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: List Integer
-
-
-
-
-
If the upper bound of a segment is omitted then a different type of
-segmented list is obtained and expanding it will produce a stream (which
-will be considered in the next section):
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List UniversalSegment PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: Stream Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
0.6.3 Streams
-
-
-
Streams are infinite lists which have the ability to calculate the next
-element should it be required. For example, a stream of positive integers
-and a list of prime numbers can be generated by:
-
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: Stream PositiveInteger
-
-
-
-
-
-
-
-
-
[i for i in 1.. | prime?(i)]
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: Stream PositiveInteger
-
-
-
-
-
In each case the first few elements of the stream are calculated for display
-purposes but the rest of the stream remains unevaluated. The value of items
-in a stream are only calculated when they are needed which gives rise to
-their alternative name of ``lazy lists''.
-
-
-
-
Another method of creating streams is to use the generate(f,a) function.
-This applies its first argument repeatedly onto its second to produce the
-stream . Given that the function
- nextPrime returns the lowest prime number greater than its argument we
-can generate a stream of primes as follows:
-
-
-
-
-
-
-
generate(nextPrime,2)$Stream Integer
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: Stream Integer
-
-
-
-
-
As a longer example a stream of Fibonacci numbers will be computed. The
-Fibonacci numbers start at and each following number is the addition
-of the two numbers that precede it so the Fibonacci sequence is:
-.
-
-
-
-
Since the generation of any Fibonacci number only relies on knowing the
-previous two numbers we can look at the series through a window of two
-elements. To create the series the window is placed at the start over
-the values and their sum obtained. The window is now shifted to
-the right by one position and the sum placed into the empty slot of the
-window; the process is then repeated. To implement this we require a
-function that takes a list of two elements (the current view of the window),
-adds them, and outputs the new window. The result is the function
- :
-
-
-
-
-
-
-
win : List Integer -> List Integer
-
-
-
-
-
-
-
-Type: Void
-
-
-
-
-
-
-
-
-
win(x) == [x.2, x.1 + x.2]
-
-
-
-
-
-
-
-Type: Void
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: List Integer
-
-
-
-
-
Thus it can be seen that repeatedly applying win to the results
-of the previous invocation each element of the series is obtained. Clearly
- win is an ideal function to construct streams using the generate
-function:
-
-
-
-
-
-
-
fibs := [generate(win,[1,1])]
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: Stream List Integer
-
-
-
-
-
This isn't quite what is wanted -- we need to extract the first element of
-each list and place that in our series:
-
-
-
-
-
-
-
fibs := [i.1 for i in [generate(win,[1,1])] ]
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: Stream Integer
-
-
-
-
-
Obtaining the 200th Fibonacci number is trivial:
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
One other function of interest is complete which expands a finite
-stream derived from an infinite one (and thus was still stored as an
-infinite stream) to form a finite stream.
-
-
-
-
-
-
-
-
-
-
-
-
0.6.4 Arrays, Vectors, Strings, and Bits
-
-
-
The simplest array data structure is the one-dimensional array which
-can be obtained by applying the oneDimensionalArray function to a list:
-
-
-
-
-
-
-
oneDimensionalArray([7,2,5,4,1,9])
-
-
-
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
One-dimensional array are homogenous (all elements must have the same type)
-and mutable (elements can be changed) like lists but unlike lists they are
-constant in size and have uniform access times (it is just as quick to read
-the last element of a one-dimensional array as it is to read the first; this
-is not true for lists).
-
-
-
-
Since these arrays are mutable all the warnings that apply to lists apply to
-arrays. That is, it is possible to modify an element in a copy of an array
-and change the original:
-
-
-
-
-
-
-
x := oneDimensionalArray([7,2,5,4,1,9])
-
-
-
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
Note that because these arrays are of fixed size the concat! function
-cannot be applied to them without generating an error. If arrays of this
-type are required use the FlexibleArray constructor.
-
-
-
-
One-dimensional arrays can be created using new which specifies the size
-of the array and the initial value for each of the elements. Other operations
-that can be applied to one-dimensional arrays are map! which applies
-a mapping onto each element, swap! which swaps two elements and
- copyInto!(a,b,c) which copies the array b onto a starting at
-position c.
-
-
-
-
-
-
-
a : ARRAY1 PositiveInteger := new(10,3)
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
(note that ARRAY1 is an abbreviation for the type
-OneDimensionalArray.) Other types based on one-dimensional arrays are
-Vector, String, and Bits.
-
-
-
-
-
-
-
-
map!(i +-> i+1,a); a
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
-
-
-
-
b := oneDimensionalArray([2,3,4,5,6])
-
-
-
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: OneDimensionalArray PositiveInteger
-
-
-
-
-
-
-
-
-
vector([1/2,1/3,1/14])
-
-
-
-
-
-
-
-
-
-
-Type: Vector Fraction Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: String
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: Bits
-
-
-
-
-
A vector is similar to a one-dimensional array except that if its
-components belong to a ring then arithmetic operations are provided.
-
-
-
-
-
-
-
-
-
-
-
-
0.6.5 Flexible Arrays
-
-
-
Flexible arrays are designed to provide the efficiency of one-dimensional
-arrays while retaining the flexibility of lists. They are implemented by
-allocating a fixed block of storage for the array. If the array needs to
-be expanded then a larger block of storage is allocated and the contents
-of the old block are copied into the new one.
-
-
-
-
There are several operations that can be applied to this type, most of
-which modify the array in place. As a result these functions all have
-names ending in ``!''. The physicalLength returns the actual length
-of the array as stored in memory while the physicalLength! allows this
-value to be changed by the user.
-
-
-
-
-
-
-
f : FARRAY INT := new(6,1)
-
-
-
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
f.1:=4; f.2:=3 ; f.3:=8 ; f.5:=2 ; f
-
-
-
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
insert!(42,f,3); f
-
-
-
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
insert!(28,f,8); f
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
removeDuplicates!(f)
-
-
-
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-Type: PositiveInteger
-
-
-
-
-
-
-
-
-
physicalLength!(f,20)
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
merge!(sort!(f),sort!(g))
-
-
-
-
-
-
-|
-
- |
-
-
-
-
-
-
-
-Type: FlexibleArray Integer
-
-
-
-
-
-
-
-
-
shrinkable(false)$FlexibleArray(Integer)
-
-
-
-
-
-
-
-
-
-
-Type: Boolean
-
-
-
-
-
There are several things to point out concerning these
-examples. First, although flexible arrays are mutable, making copies
-of these arrays creates separate entities. This can be seen by the
-fact that the modification of element b.2 above did not alter
-a. Second, the merge! function can take an extra argument
-before the two arrays are merged. The argument is a comparison
-function and defaults to ``<='' if omitted. Lastly,
- shrinkable tells the system whether or not to let flexible arrays
-contract when elements are deleted from them. An explicit package
-reference must be given as in the example above.
-
-
-
-
-
-
-
-
-
-
-
+
0.6 Data Structures in Axiom
+
+
+
This chapter is an overview of some of the data structures provided
+by Axiom.
+
+
+
+
+
+
0.6.1 Lists
+
+
+
The Axiom List type constructor is used to create homogenous lists of
+finite size. The notation for lists and the names of the functions that
+operate over them are similar to those found in functional languages such
+as ML.
+
+
+
+
Lists can be created by placing a comma separated list of values inside
+square brackets or if a list with just one element is desired then the
+function list is available:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
The function append takes two lists as arguments and returns the list
+consisting of the second argument appended to the first. A single element
+can be added to the front of a list using cons:
+
+
+
+
+
+
+
+
append([1,2,3,5],[7,11])
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
cons(23,[65,42,19])
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
Lists are accessed sequentially so if Axiom is asked for the value of the
+twentieth element in the list it will move from the start of the list over
+nineteen elements before it reaches the desired element. Each element of a
+list is stored as a node consisting of the value of the element and a pointer
+to the rest of the list. As a result the two main operations on a list are
+called first and rest. Both of these functions take a second
+optional argument which specifies the length of the first part of the list:
+
+
+
+
+
+
+
+
first([1,5,6,2,3])
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
first([1,5,6,2,3],2)
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
rest([1,5,6,2,3],2)
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
Other functions are empty? which tests to see if a list contains no
+elements, member? which tests to see if the first argument is a member
+of the second, reverse which reverses the order of the list, sort
+which sorts a list, and removeDuplicates which removes any duplicates.
+The length of a list can be obtained using the `` #'' operator.
+
+
+
+
+
+
+
+
empty?([7,2,-1,2])
+
+
+
+
+
+
+
+
+
+
+Type: Boolean
+
+
+
+
+
+
+
+
+
member?(-1,[7,2,-1,2])
+
+
+
+
+
+
+
+
+
+
+Type: Boolean
+
+
+
+
+
+
+
+
+
reverse([7,2,-1,2])
+
+
+
+
+
+
+
+
+
+
+Type: List Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List Integer
+
+
+
+
+
+
+
+
+
removeDuplicates([1,5,3,5,1,1,2])
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
Lists in Axiom are mutable and so their contents (the elements and the links)
+can be modified in place. Functions that operate over lists in this way have
+names ending in the symbol ``!''. For example, concat! takes two lists
+as arguments and appends the second argument to the first (except when the
+first argument is an empty list) and setrest! changes the link
+emanating from the first argument to point to the second argument:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
concat!(u,[1,5,42]); u
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
endOfu := rest(u,4)
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
partOfu := rest(u,2)
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
setrest!(endOfu,partOfu); u
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
From this it can be seen that the lists returned by first and rest
+are pointers to the original list and not a copy. Thus great care must
+be taken when dealing with lists in Axiom.
+
+
+
+
Although the nth element of the list l can be obtained by
+applying the first function to applications of rest
+to l, Axiom provides a more useful access method in the form of
+the ``.'' operator:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
first rest rest u -- Same as u.3
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
The operation u.i is referred to as indexing into u or
+elting into u. The latter term comes from the elt function
+which is used to extract elements (the first element of the list is at
+index ).
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
If a list has no cycles then any attempt to access an element beyond the
+end of the list will generate an error. However, in the example above there
+was a cycle starting at the third element so the access to the sixth
+element wrapped around to give the third element. Since lists are mutable it
+is possible to modify elements directly:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
Other list operations are:
+
+
+
+
+
+
+
L := [9,3,4,7]; #L
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
Note that using the `` #'' operator on a list with cycles causes Axiom to
+enter an infinite loop.
+
+
+
+
Note that any operation on a list L that returns a list
+will, in general, be such that any changes to will have the
+side-effect of altering L. For example:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
Thus the only save way of copying lists is to copy each element from one to
+another and not use the assignment operator:
+
+
+
+
+
+
+
+
p := [i for i in n] -- Same as `p := copy(n)'
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
In the previous example a new way of constructing lists was given. This is
+a powerful method which gives the reader more information about the contents
+of the list than before and which is extremely flexible. The example
+
+
+
+
+
+
+
+
[i for i in 1..10]
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
should be read as
+
+
+
+
+
+
+
+
+
``Using the expression i, generate each element of the list by
+iterating the symbol i over the range of integers [1,10]''
+
+
+
+
+
+
+
+
+
To generate the list of the squares of the first ten elements we just use:
+
+
+
+
+
+
+
+
[i**2 for i in 1..10]
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
For more complex lists we can apply a condition to the elements that are to
+be placed into the list to obtain a list of even numbers between 0 and 11:
+
+
+
+
+
+
+
+
[i for i in 1..10 | even?(i)]
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
This example should be read as:
+
+
+
+
+
+
+
+
``Using the expression i, generate each element of the list
+by iterating the symbol i over the range of integers [1,10] such that
+i is even''
+
+
+
+
+
+
+
+
+
The following achieves the same result:
+
+
+
+
+
+
+
+
[i for i in 2..10 by 2]
+
+
+
+
+
+
+
+
+
+
+Type: List PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
0.6.2 Segmented Lists
+
+
+
A segmented list is one in which some of the elements are ranges of values.
+The expand function converts lists of this type into ordinary lists:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List Segment PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: List Segment PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: List Integer
+
+
+
+
+
If the upper bound of a segment is omitted then a different type of
+segmented list is obtained and expanding it will produce a stream (which
+will be considered in the next section):
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List UniversalSegment PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: Stream Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
0.6.3 Streams
+
+
+
Streams are infinite lists which have the ability to calculate the next
+element should it be required. For example, a stream of positive integers
+and a list of prime numbers can be generated by:
+
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: Stream PositiveInteger
+
+
+
+
+
+
+
+
+
[i for i in 1.. | prime?(i)]
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: Stream PositiveInteger
+
+
+
+
+
In each case the first few elements of the stream are calculated for display
+purposes but the rest of the stream remains unevaluated. The value of items
+in a stream are only calculated when they are needed which gives rise to
+their alternative name of ``lazy lists''.
+
+
+
+
Another method of creating streams is to use the generate(f,a) function.
+This applies its first argument repeatedly onto its second to produce the
+stream . Given that the function
+ nextPrime returns the lowest prime number greater than its argument we
+can generate a stream of primes as follows:
+
+
+
+
+
+
+
generate(nextPrime,2)$Stream Integer
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: Stream Integer
+
+
+
+
+
As a longer example a stream of Fibonacci numbers will be computed. The
+Fibonacci numbers start at and each following number is the addition
+of the two numbers that precede it so the Fibonacci sequence is:
+.
+
+
+
+
Since the generation of any Fibonacci number only relies on knowing the
+previous two numbers we can look at the series through a window of two
+elements. To create the series the window is placed at the start over
+the values and their sum obtained. The window is now shifted to
+the right by one position and the sum placed into the empty slot of the
+window; the process is then repeated. To implement this we require a
+function that takes a list of two elements (the current view of the window),
+adds them, and outputs the new window. The result is the function
+ :
+
+
+
+
+
+
+
win : List Integer -> List Integer
+
+
+
+
+
+
+
+Type: Void
+
+
+
+
+
+
+
+
+
win(x) == [x.2, x.1 + x.2]
+
+
+
+
+
+
+
+Type: Void
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: List Integer
+
+
+
+
+
Thus it can be seen that repeatedly applying win to the results
+of the previous invocation each element of the series is obtained. Clearly
+ win is an ideal function to construct streams using the generate
+function:
+
+
+
+
+
+
+
fibs := [generate(win,[1,1])]
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: Stream List Integer
+
+
+
+
+
This isn't quite what is wanted -- we need to extract the first element of
+each list and place that in our series:
+
+
+
+
+
+
+
fibs := [i.1 for i in [generate(win,[1,1])] ]
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: Stream Integer
+
+
+
+
+
Obtaining the 200th Fibonacci number is trivial:
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
One other function of interest is complete which expands a finite
+stream derived from an infinite one (and thus was still stored as an
+infinite stream) to form a finite stream.
+
+
+
+
+
+
+
+
+
+
+
+
0.6.4 Arrays, Vectors, Strings, and Bits
+
+
+
The simplest array data structure is the one-dimensional array which
+can be obtained by applying the oneDimensionalArray function to a list:
+
+
+
+
+
+
+
oneDimensionalArray([7,2,5,4,1,9])
+
+
+
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
One-dimensional array are homogenous (all elements must have the same type)
+and mutable (elements can be changed) like lists but unlike lists they are
+constant in size and have uniform access times (it is just as quick to read
+the last element of a one-dimensional array as it is to read the first; this
+is not true for lists).
+
+
+
+
Since these arrays are mutable all the warnings that apply to lists apply to
+arrays. That is, it is possible to modify an element in a copy of an array
+and change the original:
+
+
+
+
+
+
+
x := oneDimensionalArray([7,2,5,4,1,9])
+
+
+
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
Note that because these arrays are of fixed size the concat! function
+cannot be applied to them without generating an error. If arrays of this
+type are required use the FlexibleArray constructor.
+
+
+
+
One-dimensional arrays can be created using new which specifies the size
+of the array and the initial value for each of the elements. Other operations
+that can be applied to one-dimensional arrays are map! which applies
+a mapping onto each element, swap! which swaps two elements and
+ copyInto!(a,b,c) which copies the array b onto a starting at
+position c.
+
+
+
+
+
+
+
a : ARRAY1 PositiveInteger := new(10,3)
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
(note that ARRAY1 is an abbreviation for the type
+OneDimensionalArray.) Other types based on one-dimensional arrays are
+Vector, String, and Bits.
+
+
+
+
+
+
+
+
map!(i +-> i+1,a); a
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
+
+
+
+
b := oneDimensionalArray([2,3,4,5,6])
+
+
+
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: OneDimensionalArray PositiveInteger
+
+
+
+
+
+
+
+
+
vector([1/2,1/3,1/14])
+
+
+
+
+
+
+
+
+
+
+Type: Vector Fraction Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: String
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: Bits
+
+
+
+
+
A vector is similar to a one-dimensional array except that if its
+components belong to a ring then arithmetic operations are provided.
+
+
+
+
+
+
+
+
+
+
+
+
0.6.5 Flexible Arrays
+
+
+
Flexible arrays are designed to provide the efficiency of one-dimensional
+arrays while retaining the flexibility of lists. They are implemented by
+allocating a fixed block of storage for the array. If the array needs to
+be expanded then a larger block of storage is allocated and the contents
+of the old block are copied into the new one.
+
+
+
+
There are several operations that can be applied to this type, most of
+which modify the array in place. As a result these functions all have
+names ending in ``!''. The physicalLength returns the actual length
+of the array as stored in memory while the physicalLength! allows this
+value to be changed by the user.
+
+
+
+
+
+
+
f : FARRAY INT := new(6,1)
+
+
+
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
f.1:=4; f.2:=3 ; f.3:=8 ; f.5:=2 ; f
+
+
+
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
insert!(42,f,3); f
+
+
+
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
insert!(28,f,8); f
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
removeDuplicates!(f)
+
+
+
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Type: PositiveInteger
+
+
+
+
+
+
+
+
+
physicalLength!(f,20)
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
merge!(sort!(f),sort!(g))
+
+
+
+
+
+
+|
+
+ |
+
+
+
+
+
+
+
+Type: FlexibleArray Integer
+
+
+
+
+
+
+
+
+
shrinkable(false)$FlexibleArray(Integer)
+
+
+
+
+
+
+
+
+
+
+Type: Boolean
+
+
+
+
+
There are several things to point out concerning these
+examples. First, although flexible arrays are mutable, making copies
+of these arrays creates separate entities. This can be seen by the
+fact that the modification of element b.2 above did not alter
+a. Second, the merge! function can take an extra argument
+before the two arrays are merged. The argument is a comparison
+function and defaults to ``<='' if omitted. Lastly,
+ shrinkable tells the system whether or not to let flexible arrays
+contract when elements are deleted from them. An explicit package
+reference must be given as in the example above.
+
+
+
+
+
+
+
+
+
+
+