Functional Data Structures

extensively studied for more than 30 years. For many languages
(e.g., C, C++, Java, Modula 2, and Pascal) implementations of commonly
used data structure have been described in textbooks. However, for
functional languages like ML and Haskell the situation is different,
because many data structures which are well suited for imperative
programming languages do not have direct implementations in functional
languages. The main reason is that functional languages do not
allow destructive updates, i.e., assignments.

One intriguing example are catenable lists. Lists are the most
important data structure in many functional programs. Functional
programming languages usually only allow the head of a list to be
accessed in constant time, whereas it requires linear time to access
the last element in a list and to catenate two lists. That there
exists a functional implementation of lists supporting list catenation
in constant time while having constant-time access to the head of the
lists was demonstrated only recently by Kaplan and Tarjan.

In this mini course I will survey some basic techniques for designing
efficient data structures for a functional language. Techniques for
both a strict functional language (ML) and a lazy functional language
(Haskell) will be considered. Several techniques for designing
efficient data structure will be illustrated: Incremental rebuilding,
skew binary counters, and data-structural bootstrapping. For strict
functional languages well-known amortization arguments cannot be
applied, because all functional data structures are automatically also
fully persistent (old versions of the data structure can be accessed
and modified). It turns out that for lazy functional languages a
variant of the well-known amortization arguments can be applied.

The data structures that will be covered in this mini course to
illustrate the different techniques are:

Double ended queues (deques),
Priority queues,
Search trees, and
Catenable lists.

The data structures considered will be illustrated with
implementations in Standard ML and Haskell.