Axiom has a large variety of data structures available. Many data structures are particularly useful for interactive computation and others are useful for building applications. The data structures of Axiom are organized into category hierarchies.
A list, Lists are discussed in Section ListXmpPage, is the most commonly used data structure in Axiom for holding objects all of the same type. The name list is short for ``linked-list of nodes.'' Each node consists of a value (firstfirstList) and a link (restrestList) that points to the next node, or to a distinguished value denoting the empty list. To get to, say, the third element, Axiom starts at the front of the list, then traverses across two links to the third node.
Write a list of elements using square brackets with commas separating the elements.
This is the value at the third node. Alternatively, you can say .
Many operations are defined on lists, such as: empty?, to test that a list has no elements; cons, to create a new list with first element and rest ; reverse, to create a new list with elements in reverse order; and sort, to arrange elements in order.
An important point about lists is that they are ``mutable'': their constituent elements and links can be changed ``in place.'' To do this, use any of the operations whose names end with the character ``!''.
The operation concat!concat!List replaces the last link of the list to point to some other list . Since refers to the original list, this change is seen by .
A cyclic list is a list with a ``cycle'': list:cyclic a link pointing back to an earlier node of the list. cyclic list To create a cycle, first get a node somewhere down the list.
Use setrest!setrest!List to change the link emanating from that node to point back to an earlier part of the list.
A stream is a structure that (potentially) has an infinite number of distinct elements. Think of a stream as an ``infinite list'' where elements are computed successively. Streams are discussed in Section{StreamXmpPage}.
Create an infinite stream of factored integers. Only a certain number of initial elements are computed and displayed.
Axiom represents streams by a collection of already-computed elements together with a function to compute the next element ``on demand.'' Asking for the -th element causes elements through to be evaluated.
Streams can also be finite or cyclic. They are implemented by a linked list structure similar to lists and have many of the same operations. For example, first and rest are used to access elements and successive nodes of a stream.
A one-dimensional array is another data structure used to hold objects of the same type OnedimensionalArray is discussed in Section OneDimensionalArrayXmpPage. Unlike lists, one-dimensional arrays are inflexible---they are array:one-dimensional implemented using a fixed block of storage. Their advantage is that they give quick and equal access time to any element.
A simple way to create a one-dimensional array is to apply the operation oneDimensionalArray to a list of elements.
One-dimensional arrays are also mutable: you can change their constituent elements ``in place.''
However, one-dimensional arrays are not flexible structures. You cannot destructively concat! them together.
Examples of datatypes similar to OneDimensionalArray are: Vector (vectors are mathematical structures implemented by one-dimensional arrays), String (arrays of ``characters,'' represented by byte vectors), and Bits (represented by ``bit vectors'').
A vector of 32 bits, each representing the Boolean value .
A flexible array (FlexibleArray is discussed in Section FlexibleArrayXmpPage ) is a cross between a list array:flexible and a one-dimensional array. Like a one-dimensional array, a flexible array occupies a fixed block of storage. Its block of storage, however, has room to expand. When it gets full, it grows (a new, larger block of storage is allocated); when it has too much room, it contracts.
Create a flexible array of three elements.
Insert some elements between the second and third elements.
Flexible arrays are used to implement ``heaps.'' A heap (Heap is discussed in Section HeapXmpPage ) is an example of a data structure called a priority queue, where elements are ordered with respect to one another. A heap is organized so as to optimize insertion and extraction of maximum elements. The extract! operation returns the maximum element of the heap, after destructively removing that element and reorganizing the heap so that the next maximum element is ready to be delivered.
An easy way to create a heap is to apply the operation heap to a list of values.
This loop extracts elements one-at-a-time from until the heap is exhausted, returning the elements as a list in the order they were extracted.
A binary tree is a ``tree'' with at most two branches tree per node: it is either empty, or else is a node consisting of a value, and a left and right subtree (again, binary trees). Examples of binary tree types are BinarySearchTree, PendantTree, TournamentTree, and BalancedBinaryTree.
A binary search tree is a binary tree such that, tree:binary search for each node, the value of the node is binary search tree greater than all values (if any) in the left subtree, and less than or equal all values (if any) in the right subtree. (BinarySearchTrees are discussed in Section BinarySearchTreeXmpPage )
A balanced binary tree is useful for doing modular computations. balanced binary tree Given a list of moduli, tree:balanced binary modTree produces a balanced binary tree with the values at its leaves.
A set is a collection of elements where duplication and order is irrelevant. Sets are discussed in Section SetXmpPage Sets are always finite and have no corresponding structure like streams for infinite collections.
Create sets using braces ``{`` and ``}'' rather than brackets.
A multiset is a set that keeps track of the number of duplicate values. Multisets are discussed in Section MultiSetXmpPage
For all the primes between 2 and 1000, find the distribution of .
A table is conceptually a set of ``key--value'' pairs and is a generalization of a multiset. For examples of tables, see AssociationList, HashTable, KeyedAccessFile, Library, SparseTable, StringTable, and Table. The domain Table(Key, Entry) provides a general-purpose type for tables with values of type indexed by keys of type .
Compute the above distribution of primes using tables. First, let denote an empty table of keys and values, each of type Integer.
We define a function howMany to return the number of values of a given modulus seen so far. It calls search which returns the number of values stored under the key in table , or ``failed'' if no such value is yet stored in under .
In English, this says ``Define as follows. First, let be the value of search. Then, if has the value , return the value ; otherwise return .''
Run through the primes to create the table, then print the table. The expression t.m := howMany(m) updates the value in table stored under key .
A record is an example of an inhomogeneous collection of objects.See ugTypesRecords for details. A record consists of a set of named selectors that can be used to access its components. Record@{\sf Record}
Declare that can only be assigned a record with two prescribed fields.
Give a value, using square brackets to enclose the values of the fields.
Give a raise.
A union is a data structure used when objects have multiple types.See ugTypesUnions for details. Union@{\sf Union}
Let be either an integer or a string value.
Give a name.
All told, there are over forty different data structures in Axiom. Using the domain constructors described in Chapter ugDomains you can add your own data structure or extend an existing one. Choosing the right data structure for your application may be the key to obtaining good performance.