An adaptive computation adapts its output to match changes to the
input.  Many techniques have been proposed for certain classes of
adaptive computations, especially for particular applications such as
language-based editing environments and spreadsheets.  The general
problem, however, has proved hard: given an arbitrary computation, how
can we make it adaptive?

We propose a general mechanism for \emph{adaptive functional
programming} that enables the programmer to express adaptive
algorithms in a natural way.  We describe this mechanism in two
contexts: as extensions to a simple typed functional language, and as
a library for Standard ML.  First, we present a {\em modal type
system} and an operational semantics for the extended functional
language.  We establish the soundness of the language with a type
safety theorem and a correctness theorem for the adaptivity mechanism.
Second, we present methods to efficiently implement the operational
semantics and describe how these are used to implement the SML
library.

As an example of how to apply our mechanisms, we present an adaptive
version of quicksort whose input and output are lists.  This version
involves only minor modifications to a standard list-based quicksort.
We show that when adding an element to the end of an input list of
length $n$, the program will adapt the output in expected and
amortized $O(\log n)$ time.