Purely Functional Data Structures

DOI10.1017/CBO9780511530104MaRDI QIDQ4702190zbMATH OpenOpenAlexFDO

Publication date 24 November 1999

Full work available at URL https://doi.org/10.1017/cbo9780511530104

amortization data structures functional data structures lazy evaluation standard ML

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Data structures (68P05)

Review text

Most existing literature on data structures implicitly assumes that such structures be implemented in some imperative programming language like C or C++. It turns out, however, that data structures for these languages do not always translate well to functional languages thus leaving programmers on their own when they need to implement efficient data structures for a particular problem. The book is intended to help those that want to learn more about data structures in functional setting. To do that it presents a number of data structures described from the point of view of functional languages as well as design techniques so that programmers can develop their own functional data structures. All examples in the book are given in Standard ML (translation of most of the examples to Haskell is given in appendix). Chapter 1 of the book serves as an introduction with brief discussion concerning comparison of functional versus imperative data structures, and strict versus lazy evaluation. Also terminology used in the book is explained there. The book is then divided into three parts. The first part consisting of Chapters 2 and 3 provides an introduction to functional data structures. Chapter 2 describes how functional data structures achieve persistence, and Chapter 3 examines some familiar data structures in a functional setting. The second part consisting of Chapters 4-7 concerns the relationship between lazy evaluation and amortization. In Chapter 4 basic concepts of lazy evaluation are briefly reviewed, while Chapter 5 discusses basic techniques of amortization. Chapter 6 describes the role lazy evaluation plays in combining amortization and persistence, and gives two methods for analyzing the amortized cost of data structures implemented with lazy evaluation. In Chapter 7 scheduling -- a technique for converting lazy amortized data structures to worst-case data structures is described. In Chapters 8-11 that form the third part of the book general techniques for designing functional data structures are explored. Chapter 8 describes a lazy variant of global rebuilding technique, so called lazy rebuilding. In Chapter 9 it is suggested that there exists a strong analogy between representations of the number \(n\) and representations of container objects of size \(n\) and that this analogy can be exploited to design new implementations of container abstractions (so called numerical representation). In Chapter 10 data-structural bootstrapping technique is examined while in Chapter 11 a lazy variant of the recursive-slowdown technique, so called implicit recursive slowdown is described. The book represents handy and useful reference for professional programmers working with functional languages. Due to its clear and readable style it can also be used to self-study.

Recommendations

Cited in

(71)

This page was built for publication: Purely Functional Data Structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4702190)