\begin{abstract}
The goal of this paper is to develop a form of functional arrays (sequences) that are as efficient as imperative
arrays, can be used in parallel, and have well defined cost-semantics. The key idea is to consider sequences with
functional value semantics but non-functional cost semantics. Because the value semantics is functional, ``updating" a
sequence returns a new sequence. We allow operations on ``older" sequences (called interior sequences) to be more
expensive than operations on the ``most recent" sequences (called leaf sequences) .
We embed sequences in a language supporting fork-join parallelism. Due to the parallelism, operations can be
interleaved non-deterministically, and, in conjunction with the different cost for interior and leaf sequences, this
can lead to non-deterministic costs for a program. Consequently the costs of programs can be difficult to analyze.
The main result is the derivation of a deterministic cost dynamics which makes analyzing the costs easier. The
theorems are not specific to sequences and can be applied to other data types with different costs for operating on
interior and leaf versions.
We present a wait-free concurrent implementation of sequences that requires constant work for accessing and updating
leaf sequences, and logarithmic work for accessing and linear work for updating interior sequences. We sketch a proof
of correctness for the sequence implementation. The key advantages of the present approach compared to current
approaches is that our implementation requires no changes to existing programming languages, supports nested
parallelism, and has well defined cost semantics. At the same time, it allows for functional implementations of
algorithms such as depth-first search with the same asymptotic complexity as imperative implementations.
\end{abstract}