Purely Functional Data Structures 1st Edition, Kindle Edition
Use the Amazon App to scan ISBNs and compare prices.
This month's Book With Buzz: "The Lying Game" by Ruth Ware
From the instant New York Times bestselling author of blockbuster thrillers "In a Dark, Dark Wood" and "The Woman in Cabin 10" comes Ruth Ware’s chilling new novel, "The Lying Game." See more
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
Customers who bought this item also bought
Would you like to tell us about a lower price?
Top customer reviews
The typical data structures most programmers know and use require imperative programming: they fundamentally depend on replacing the values of fields with assignment statements, especially pointer fields. A particular data structure represents the state of something at that particular moment in time, and that moment only. If you want to know what the state was in the past you needed to have made a copy of the entire data structure back then, and kept it around until you needed it. (Alternatively, you could keep a log of changes made to the data structure that you could play in reverse until you get the previous state - and then play it back forwards to get back to where you are now. Both these techniques are typically used to implement undo/redo, for example.)
Or you could use a persistent data structure. A persistent data structure allows you to access previous versions at any time without having to do any copying. All you needed to do at the time was to save a pointer to the data structure. If you have a persistent data structure, your undo/redo implementation is simply a stack of pointers that you push a pointer onto after you make any change to the data structure.
This can be quite useful--but it is typically very hard to implement a persistent data structure in an imperative language, especially if you have to worry about memory management . If you're using a functional programming language--especially a language with lazy semantics like Haskell--then all your data structures are automatically persistent, and your only problem is efficiency (and of course, in your functional languages, the language system takes care of memory management). But for practical purposes, as a hardcore C++ programmer for professional purposes, I was locked out of the world of persistent data structures.
Now, however, with C# and C++/CLI in use (and garbage collection coming to C++ any time now ... ) I can at last contemplate the use of persistent data structures in my designs. And that's great, because it gave me an excuse to take one of my favorite computer science books off the shelf and give it another read.
The book is Purely Functional Data Structures, by Chris Okasaki. I find it to be a very well written and easy to understand introduction to the design and analysis of persistent data structures--or equivalently--for the design and analysis of any data structure you'd want to use in a functional language.
There are two key themes of the book: First, to describe the use and implementation of several persistent data structures, such as different kinds of heaps, queues, and random-access lists, and second, to describe how to create your own efficient persistent data structures.
A nice feature here is the inclusion of "Hint to Practitioners" sidebars that point out which of these data structures work especially well in various contexts.
The second theme is the more demanding one--but of course, it is teaching something really valuable. First, the methods of analyzing amortized time taken by operations in a data structure are fully explained. The two basic techniques are the "banker's method" and the "physicist's method", and they have to do with different ways of accounting for time spent in in the different operations on a data structure so that bounds on the time spent can be computed. (The "credits" and "debits" used for accounting for time are not reflected in the code for the data structure - they are "virtual" and only used for the analysis.) Then, Okasaki adapts these methods to work for persistent data structures, and provides several fully worked out examples.
With analysis of persistent data structures explained he then goes on to describe several methods of creating efficient persistent data structures from non-persistent data structures. These methods are lazy rebuilding,use of numerical representations in building data structures, data-structural bootstrapping, and implicit recursive slowdown. These methods are all interesting, but the one which is most fun (and for me, the easiest to understand) is the use of numerical representations. In this method data structures are built by composing smaller structures in a form that is similar to the representation of a binary number--and merging and deleting items from the data structure is modeled as adding or subtracting from a number. Also, different kinds of binary number representations are used, and the use of base 3 and base 4 numbers is mentioned. 
The persistent data structures described are given with code (in an ML variant that includes explicit notations for lazy evaluation, and also in Haskell). After the book was published the data structures described were "productized" into a Haskell library called Edison, originally written by Chris Okasaki, but which is now maintained and enhanced by Robert Dockins and available at [...]
1: A good starting point to look for papers on the subject of imperative persistent data structures is to search for papers co-authored by Robert E Tarjan with the word "persistent" in the title.
2: GC is part of the C++0x language and compilers will be required to support it, so that means we'll get to use it by 2015, I'm sure!
3: You can get the flavor of this kind of thing from this paper by Ralf Hinze - [...]
It is a great challenge to read and gives a great view of data structures you would never have thought of.
Every programmer -- functional or otherwise -- should have a copy at arm's length.
This book remains the best resource available on implementing performant purely functional versions of well-known data structures -- the kind of data structures that everyday programmers need to get their jobs done.
It would be one thing to only aim for coverage of the space, but Okasaki goes much further by demanding that every algorithm he presents be as elegant as possible.
That insistence on elegance really pays off for the reader: the algorithms are easy to understand and easy to implement in the language of your choice.
To the delight of the reader, in many cases, the functional versions of these data structures end up much easier to implement and understand than their more well-known imperative versions.
The exercises, also, are only SML. Several appear to use idiosyncratic SML features -- I say "appear" because no answers to the exercises, even the basic ones, are provided for me to check my understanding.
Essentially, the content is good, but expect to learn Standard ML to really get the most out of this book.
If you are an advanced programmer, i.e. you have significant experience with a procedural or OO language and some experience with a functional programming language, then this book may be for you. If you have experienced issues in synchronising access to data structures in multi-threaded environments or ensuring transactional access to complex data, then this book contains the wisdom you seek.
Most recent customer reviews
Set up an Amazon Giveaway
Customers who viewed this item also viewed
What other items do customers buy after viewing this item?
Look for similar items by category
- Books > Computers & Technology > Databases & Big Data > Data Modeling & Design
- Books > Computers & Technology > Programming > Algorithms > Data Structures
- Books > Computers & Technology > Programming > Functional
- Books > Computers & Technology > Programming > Software Design, Testing & Engineering > Software Development
- Books > Computers & Technology > Programming > Software Design, Testing & Engineering > Structured Design
- Books > Computers & Technology > Programming Languages
- Kindle Store > Kindle eBooks > Computers & Technology > Programming > Software Design, Testing & Engineering > Software Development