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:

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

  1. G. S. Brodal and C. Okasaki. Optimal Purely Functional Priority Queues. Journal of Functional Programming, 6(6):839-857, November 1996.
  2. 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.
  3. C. Okasaki. Catenable Double-Ended Queues. International Conference on Functional Programming, June 1997, pages 66-74.
  4. C. Okasaki. Functional Data Structures. Advanced Functional Programming, August 1996, pages 131-158, LNCS 1129.
  5. C. Okasaki. The Role of Lazy Evaluation in Amortized Data Structures. International Conference on Functional Programming, May 1996, pages 62-72.
  6. 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.
  7. C. Okasaki. Simple and Efficient Purely Functional Queues and Deques. Journal of Functional Programming, 5(4):583-592, October 1995.
  8. C. Okasaki. Purely Functional Random-Access Lists. Functional Programming Languages and Computer Architecutre, June 1995, pages 86-95.
  9. L. C. Paulson. ML for the Working Programmer. 2nd Edition. Cambridge University Press, 1996.
  10. S. Thompson. Haskell: The Craft of Functional Programming. Addison-Wesley, 1996.

Some material


People

Haskell

Standard ML