Data structures

libaldor provides both linear data structures (e.g. arrays and lists) and non-linear ones (e.g. hash tables). The category hierarchy for data structures is shown in Figure 2.

Figure 2: The libaldor category hierarchy for data structures

libaldor provides some standard linear data structures having very similar functionalities: List T and CheckingList T both provide linked lists whose entries are of type T, while Array T and CheckingArray T both provide arrays whose entries are of type T. Lower-level linear data structures are PrimitiveArray T and PackedPrimitiveArray T, which provide simpler arrays whose entries are of type T. All of those data structures can be created by explicitly listing a finite number of elements, for example

l:List String := ["hello", "world"]

or by bracketing a generator, for example

a:PrimitiveArray MachineInteger := [n for n in 1..100 | odd? n].

In addition, the function new also allows structures to be created, and the constant empty returns an empty structure. The individual elements can be accessed via s.n where s is a data structure and n an index. The indexing scheme and the bound-checking scheme both depend on the structure: List and CheckingList are 1-indexed, while Array, CheckingArray, PrimitiveArray and PackedPrimitiveArray are 0-indexed. If you need to know the indexing scheme at runtime, or want to write index-independent code, the firstIndex constant returns the index of the first element of a structure.

The general form for iterating efficiently over a BoundedFiniteLinearStructureType is

for variable in structure | condition repeat { ... }

where ``| condition'' is optional. This is available for all high-level linear data structures, but not for those of category PrimitiveArrayType.

There are classical tradeoffs between the various array types: the only difference between CheckingArray and Array is that CheckingArray checks whether the index is within the range of the array, while Array does not. Similarly, CheckingList checks whether a list is empty before calling first and rest, while List does not. Since both pairs of types offer the same exports, you can use one during the development and testing phase, and then switch to the other for releasing your code. An advantage of the lower-level arrays of category PrimitiveArrayType is that they are compatible with C pointers and generate more efficient code when accessing their elements. In order to benefit from the advantages of all those types, libaldor provides the data function, which returns the data of an Array or CheckingArray as a PrimitiveArray without copying or allocating memory. It is thus possible to use Array or CheckingArray in your code, making sure to apply data to it before accessing elements in a loop. For example, the following function efficiently computes the sum of all the elements with even indices of an array of machine integers:

evenSum(a:Array MachineInteger):MachineInteger == {
    import from MachineInteger;               -- for the index i
    import from PrimitiveArray MachineInteger;-- for accessing the elements of p
    p := data a;                              -- for efficiency (optimized code)
    sum:MachineInteger := 0;
    for i in 0..#a by 2 repeat sum := sum + p.i;
    sum;
}

Conversely, the function array creates an Array or CheckingArray from a PrimitiveArray without copying. Note that the generator functions in Array and CheckingArray use the data function, so iterating an Array or CheckingArray a via

for x in a repeat { ... }

is as efficient as using a PrimitiveArray. Note that the debug version² of libaldor performs bound checking on accesses into all types of arrays, including String and all the low-level array types.

Since String has the category ArrayType Character, all the array functionalities are also applicable to strings. For example,

for c in "hello" repeat { ... }

assigns successively the characters 'h', 'e', 'l', 'l' and 'o' to c, and strings can be created from Generator Character. Note that String and PrimitiveArray Character are not interchangeable, since the former is packed and not the latter. String is however interchangeable with PackedPrimitiveArray Character. Similarly, chunks of memory viewed as byte arrays are provided by either one of PrimitiveMemoryBlock, MemoryBlock or CheckingMemoryBlock. Those types are to be used for buffers rather than PrimitiveArray Byte, which is not interchangeable with PrimitiveMemoryBlock.

For types whose elements are not word-size, such as Byte, Character, SingleFloat and DoubleFloat, you can use PackedPrimitiveArray as a packed alternative to PrimitiveArray, which is then compatible with the corresponding C-arrays (see Table 1).

The type Stream T, of category LinearStructureType T, provides infinite linear structures. There are several ways to create streams, the easier ones being via an unbounded iterator, or via a function that computes its ${n}^{{\rm th}}$ element. For example,

    import from MachineInteger, Stream MachineInteger;
    sqr1 := [n^2 for n in 0..];
    sqr2 := stream(0, (n:MachineInteger):MachineInteger +-> n^2);

are two different ways to create the infinite stream $[0^2, 1^2, 2^2, \dots]$. Streams can be iterated, yielding loops whose duration cannot be predicted in advance, so using a parallel finite iterator or a termination condition inside the loop is advisable. Finally, streams are lazy in that $s.0,\dots,s.n$ are computed only when $s.n$ has been specifically resquested, and elements are never recomputed a second time.

libaldor also provides different table stuctures: hash tables are provided by the HashTable type and are created via the table function, as in

t:HashTable(String, MachineInteger) := table();

The hash function defaults to the one provided by the type of the keys if it has HashType, but can be overridden by providing your own as last argument to the hash table type constructor, as in

t:HashTable(SingleFloat, MachineInteger, h) := table();

where h any function producing machine integers from machine floats. Providing the hash function is required when the type of the keys does not have HashType. Sorted tables are provided by the SortedAssociationSet type, those do not use hashing however. Hash tables can also be used to make a function remember its previous computed values: if $f: A \to B$ is any function, then

g:HashTable(A, B) := remember f;

creates a table g that can be used everywhere instead of g. While f(a) always recomputes $f(a)$, g(a) computes $f(a)$ only once and stores the pair $[a,f(a)]$ in the table.

Finally, libaldor also provides more specialized data structures documented in the reference section: Set, SortedSet, SortedList and Queue.