In the contiguous representation, a sequence is represented by a reference to an immutable array of fields of type T. An immutable array is an array that, once initialized, is never modified. Java doesn't directly support immutable arrays, but a Java program can enforce immutability by defining a wrapper class for arrays (akin to the Integer class for wrapping ints in objects) with a single private field holding the embedded array and a collection of public methods that do not mutate this field. A lighter weight but less robust protocol for supporting immutable arrays is to use comments to indicate which arrays are immutable and to follow the discipline of never modifying arrays documented as immutable. In either case, a new array object generally must be created whenever an element of the represented sequence is changed, added, or removed. Creating an array object is a costly operation proportional in time and space to the number of elements in the new array.
In the linked representation of sequences, every operation in the collection listed above except eltAt can be performed in constant time. On the other hand, the eltAt operation takes time proportional to the length of the sequence in both the worst case and the typical case. The List implementation of sequences given in chapter 1 has this property.
The performance trade-offs embodied in the immutable array implementation are very different. In this implementation, the operations empty, first, length, eltAt, can be performed in constant time. (In the Java array implementation, length is stored in a separate ``field'' in the block of storage holding the array.) With the exception of the rest operation, the remaining operations all take time proportional to the length of the sequence. The running time of the rest operation depends on an interesting implementation detail. If immutable arrays are implemented as instances of a ``wrapper'' class, then the rest operation can be performed in constant time at the cost of making an extra field reference in the implementation of eltAt. A wrapper object can store an integer offset that is added to the index passed as an argument to eltAt. In this scheme, the rest operation constructs a new wrapper object containing a pointer to the same array object as this but an increased offset (by one). If immutable arrays are implemented directly by Java arrays, then rest operation must construct a completely new array one element shorter than the original.
Finger Exercise 2.1.3.2 Construct two implementations of an
ImmutArray wrapper class that represents sequences as
arrays. Do not include an offset field in the first implemenation.
Include a offset field in the second implementation.
Test the Append and Reverse visitors written
in the context of the linked representation above and your
contiguous implementations.
Conduct some experiments to
measure the performance impact of including the offset pointer.
For each implementation, can you devise a test program that
favors it?
In practice, array representations of immutable sequences are generally not used in computations that make extensive use of the cons and empty operations to construct new sequences. The repeated copying of arrays required to support these operations is very inefficient (proportional to the square of the length of the constructed array!)
Finger Exercise 2.1.3.3 Let n be the length of a sequence host
represented either as a linked list or an array.
Prove that the computation
host.execute(new Append(host.empty()))runs in time O(n) in the linked representation, O(
) in the
contiguous representation (with or without an offset field).
The usual way to avoid this source of inefficiency is to include an operation in the immutable array class that constructs an array representation for a sequence given either a corresponding linked representation or mutable array representation. The Java Foundation classes include both the immutable string (sequence of char) class String and the mutable string class StringBuffer for this reason.
The array implementation of immutable sequences is a good choice when new sequences are generally built from scratch rather than constructed by applied operations to existing sequences. For this reason, many computations involving immutable sequences of characters (strings) rely on the array representation. The Java String class implements the array representation for immutable sequences of characters (the primitive type char in Java). Note that Java includes an operation for converting mutable strings (represented by the Java class StringBuffer) to immutable strings (represented by the Java class String). Strings can be incrementally constructed from characters far more efficiently using the StringBuffer class that they can be using the String class.