- Paperback: 232 pages
- Publisher: Cambridge University Press (June 13, 1999)
- Language: English
- ISBN-10: 0521663504
- ISBN-13: 978-0521663502
- Product Dimensions: 6 x 0.5 x 9 inches
- Shipping Weight: 14.6 ounces (View shipping rates and policies)
- Average Customer Review: 4.0 out of 5 stars See all reviews (21 customer reviews)
- Amazon Best Sellers Rank: #265,730 in Books (See Top 100 in Books)
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.
Purely Functional Data Structures
Use the Amazon App to scan ISBNs and compare prices.
Prepare for your professional certification with study guides and exam prep tools from Wiley. See more
Frequently bought together
Customers who bought this item also bought
"This book is important because it presents data structures from the point of view of functional languages...a handy reference for professional functional programmers...Most of the programs can easily be adapted to other functional languages. Even C and Java programmers should find implementing these data structures a relatively straightforward process...Programs are physically well structured and readable, and are displayed in boxes. Okasaki has produced a valuable book about functional programming, exploring a wide range of data structures...a significant contribution to the computer science literature." Computing Reviews
Most books on data structures assume an imperative language like C or C++. However, data structures for these languages do not always translate well to functional languages such as Standard ML, Haskell, or Scheme. This book describes data structures and data structure design techniques from the point of view of functional languages. It includes code for a wide assortment both of classical data structures and of data structures developed exclusively for functional languages.This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study.
Browse award-winning titles. See more
If you are a seller for this product, would you like to suggest updates through seller support?
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. It presents deletion routines, but you'll still want to read Okasaki's book first, for unless you're very much smarter than me you won't be able to understand Kars' paper until you read Okasaki's exposition of red black trees.
Finally, this book is not just useful for programmers in functional languages; logic programmers, using prolog or a varient, will also find this book very helpful, because most of the techniques (all of the techniques, really, with the exception perhaps of the lazy programming stuff) can be directly applied in a prolog programming setting as well.
After reading this book and implementing some of the data structures for yourself, you'll be amazed at how fast algorithms can run, even when written in a functional language!
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.
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.