\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}