MPII Mini-Course on Functional Data Structures,
May 5-12, 1998
by Gerth Stølting Brodal
This mini course does not require any prior knowledge about
functional programming!
Abstract
The design and analysis of efficient data structures has been
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.
Plan
| Date
| Time
| Contents
|
| Tuesday, May 5
| 13.30-15.00
| Introduction to functional data structures.
Data structuring techniques for strict functional languages:
Incremental rebuilding, skew binary counters, data structural bootstrapping.
Example data structures: double ended queues (deques), and priority queues.
|
| Thursday, May 7
| 13.30-15.00
| Data structuring techniques for lazy functional languages.
Amortized analysis for data structures in a lazy functional language.
Example data structures: search trees, double ended queues (deques), and
priority queues.
|
| Tuesday, May 12
| 13.30-15.00
| Catenable lists: Strict and lazy implementations.
|
References
-
G. S. Brodal and C. Okasaki.
Optimal Purely Functional Priority Queues.
Journal of Functional Programming, 6(6):839-857, November 1996.
-
H. Kaplan and R. E. Tarjan.
Persistent Lists with Catenation via Recursive Slow-Down.
27th Annual ACM Symposium on Theory of Computing, 1995, pages 93-102.
-
C. Okasaki.
Catenable Double-Ended Queues.
International Conference on Functional Programming,
June 1997, pages 66-74.
-
C. Okasaki.
Functional Data Structures.
Advanced Functional Programming, August 1996, pages 131-158, LNCS 1129.
-
C. Okasaki.
The Role of Lazy Evaluation in Amortized Data Structures.
International Conference on Functional Programming, May 1996, pages 62-72.
-
C. Okasaki.
Amortization, Lazy Evaluation, and Persistence: Lists with Catenation via Lazy Linking.
IEEE Symposium on Foundations of Computer Science, October 1995, pages 646-654.
-
C. Okasaki.
Simple and Efficient Purely Functional Queues and Deques.
Journal of Functional Programming, 5(4):583-592, October 1995.
-
C. Okasaki.
Purely Functional Random-Access Lists.
Functional Programming Languages and Computer Architecutre, June 1995, pages 86-95.
-
L. C. Paulson.
ML for the Working Programmer. 2nd Edition.
Cambridge University Press, 1996.
-
S. Thompson.
Haskell: The Craft of Functional Programming.
Addison-Wesley, 1996.
Some material
People
Haskell
-
Haskell, a purely functional language.
-
Hugs,
a portable Haskell interpreter written in C that runs on almost any machine.
Standard ML