Purely functional algorithms have the advantages of leading to full
persistence of all partial results, being easier to parallelize, and
being easier to formally analyze.  We present sequential and parallel
functional algorithms for computing the union, intersection and
difference of ordered sets using a variant of random balanced binary
search trees (treaps).  The algorithms are optimal with respect to the
Block Metric bound of Carlsson et al..  In particular for two sets of
length $n$ and $m$, with $m \leq n$, the algorithms run in $\oklg$
expected work, where $k$ is the least possible number of blocks that
we can break the two lists into before reforming them into one list.
The expected parallel depth of the parallel algorithms is
$O(\log^2(n))$.  The sequential bounds can also be achieved using the
purely functional catenable list data structures suggested by Kaplan
and Tarjan.  However, we believe our are structure is significantly
simpler---it only involves reversing the spines of a standard treap.
We also present experimental results that analyze the constant factors
involved in the algorithm.

A full implementation of our algorithms is available on the web at 
http://www.cs.cmu.edu/~pscico/fingertrees.html| in both JAVA and SML.