To get the free app, enter your email address or mobile phone number.
Purely Functional Data Structures
Use the Amazon App to scan ISBNs and compare prices.
Customers Who Bought This Item Also Bought
More About the Author
Top Customer Reviews
This book doesn't just present a rehash/rewrite of imperative data structures, only written in a functional language. Instead, Okasaki makes sure to emphasize benefits which only functional programming can bring to the table. For example, many functional data structures can compactly represent not just their current state, but all of their past states as well--a feature called "Persistence". Also, functional newbie programmers might be wondering why lazy vs. strict programming is a big deal, and Okasaki shows clearly where data structures can benefit from either being lazy or being strict.
For the advanced reader, Okasaki also presents several powerful techniques for analyzing the runtime of algorithms, including the so-called "Banker's Method" and the "Physicist's Method" for analyzing amortized algorithms.
I hope that Okasaki comes out with a 2nd edition of this book; there is one missing piece in particular which I really wish he would have included: Although he presents an EXTREMELY lucid description of how to implement Red-Black trees in a functional language, he only presented algorithms for insertion and querying. Of course, deletion from a red-black tree is the hardest part, left here, I suppose, as an exercise to the student. If you want to supply this missing piece yourself, check out a paper by Stefan Kars, "Red-black trees with types", J. Functional Programming 11(4):425-432, July, 2001.Read more ›
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).Read more ›
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.
I say "unfortunately", because many of the data structures used depend on lazy evaluation, which comes quite naturally to Haskell, and seems to require some sort of non-standard extension in ML.
While the content is good, I wish it would have used Haskell as the primary exposition language.
Most Recent Customer Reviews
This is probably not the kind of book in which techniques described could be applied in everyday work, but definitely a worth-reading mind-opener; the purely functional data... Read morePublished 6 days ago by Chenguang Wang
I used this book to write a data structure library in a functional language. This is a seminal work in the field, and its contents was invaluable and its style easy to read.Published 16 days ago by Daniel Haskin
Like functional languages the book is succinct and profound. The book took me a long time to complete but I thought it was the most interesting book on programming I've read.Published 7 months ago by Mårten Rånge
Gave as a gift, and I have no firsthand knowledge. I haven't heard a negative repors, so assume that it's fine.Published 10 months ago by P. D. Davidson
Okasaki's book on purely functional data structures is a timeless classic.
Every programmer -- functional or otherwise -- should have a copy at arm's length. Read more
In the pantheon of knowledge there are increasing levels of value; data, information, knowledge and wisdom. Read morePublished on January 10, 2014 by Aidan J. Delaney
This book is great for someone who already understands the basics of functional programming but wants to learn more. Read morePublished on December 5, 2009 by Amazon Customer
I use this book all the time to implement and improve purely functional data-structures. It is amazing the performance improvements possible by using good data-structures in... Read morePublished on May 1, 2009 by Jay McCarthy