Most books on data structures assume an imperative language such as 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 from the point of view of functional languages, with examples, and presents design techniques that allow programmers to develop their own functional data structures. The author includes both classical data structures, such as red-black trees and binomial queues, and a host of new data structures developed exclusively for functional languages. All source code is given in Standard ML and Haskell, and most of the programs are easily adaptable to other functional languages. This handy reference for professional programmers working with functional languages can also be used as a tutorial or for self-study.
 |
| ||||||||||||||||||
Save up to 70% when you rent your textbooks on Amazon. Keep your textbook rentals for a semester and rental return shipping is free. |
Book Description
Frequently Bought Together
Editorial Reviews
Review
"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
Book Description
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.
Product Details
Would you like to update product info or give feedback on images? |
More About the Author
Discover books, learn about writers, read author blogs, and more.
Customer Reviews
Share your thoughts with other customers
Most Helpful Customer Reviews
110 of 111 people found the following review helpful
Format:Paperback
Okasaki's slim volume is one of the best expositions on implementing data structures & algorithms in a functional language. After taking an introductory course on functional programming, this would be the book which tells you where to go next.
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!
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!
47 of 55 people found the following review helpful
By S. Brickner
Format:Paperback
The description of the book says it includes source code in both ML and Haskell. Unfortunately, the body of the text uses ML exclusively, and the Haskell code is banished to an appendix.
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.
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.
8 of 8 people found the following review helpful
By David Bakin
Format:Paperback
[This review copied from my moribund blog at [...] ]
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 [1]. 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 ... [2]) 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. [3]
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 - [...]
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 [1]. 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 ... [2]) 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. [3]
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 - [...]
Most Recent Customer Reviews
5.0 out of 5 stars
The Design Patterns of FP
I'm not going to lie; I didn't make it through the second 2/3rds of this book. But that first third did more for my understanding of functional programming than the rest of my FP... Read more
Published 23 months ago by Daniel Lyons
4.0 out of 5 stars
Haskell speakers may be daunted.
Despite the editorial description of the book, the book is really about Standard ML. It happens to have an appendix where source code has been translated -- out of order, and... Read more
Published on June 2, 2010 by Cliff L. Biffle
4.0 out of 5 stars
Good, but a bit dense
This book is great for someone who already understands the basics of functional programming but wants to learn more. Read more
Published on December 5, 2009 by J. Baker
5.0 out of 5 stars
Theoretically Interesting and Practically Useful
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 more
Published on May 1, 2009 by Jay McCarthy
5.0 out of 5 stars
Intro to the functional style and fun algorithmic content
If you are beginning to learn functional programming, this is a good book to study. It focuses much on the "no assignment" aspect of the functional style; a good place to start. Read more
Published on March 28, 2008 by Litsios James
4.0 out of 5 stars
Hash Tables are included, briefly.
A correction to another review: Hash Tables are included, briefly.
Published on November 24, 2001
3.0 out of 5 stars
Interesting, but more academic than practical
This is the best book available on the implementation of data structures in functional programming languages (e.g. ML, Haskell). Read more
Published on June 11, 2000
Citations (learn more)
This book cites 3
books:
14
books
cite this book:
See all 14 books citing this book
- The Science of Programming (Monographs in Computer Science) by David Gries in Back Matter
- Design of Dynamic Data Structures (Lecture Notes in Computer Science) by Mark H. Overmars in Back Matter
- Computer Science by Richard Jones in Back Matter
- Generic Programming: Advanced Lectures (Lecture Notes in Computer Science) by Roland Backhouse on page 55, and page 96
- Discrete Mathematics Using a Computer by Cordelia Hall on page 31, and Back Matter
- Programming Languages and Systems: Third Asian Symposium, APLAS 2005, Tsukuba, Japan, November 2-5, 2005, Proceedings (Lecture Notes in Computer Science / Programming and Software Engineering) by Kwangkeun Yi on page 51, and page 297
- Logic Programming: 19th International Conference, ICLP 2003, Mumbai, India, December 9-13, 2003, Proceedings (Lecture Notes in Computer Science) by Catuscia Palamidessi on page 268
- Typed Lambda Calculi and Applications: 6th International Conference, TLCA 2003, Valencia, Spain, June 10-12, 2003, Proceedings (Lecture Notes in Computer Science) by Martin Hofmann on page 285
See all 14 books citing this book
Books on Related Topics
(learn more)
|
|
What Other Items Do Customers Buy After Viewing This Item?
Sell a Digital Version of This Book in the Kindle Store
If you are a publisher or author and hold the digital rights to a book, you can sell a digital version of it in our Kindle Store.
Learn more
Listmania!
|
|
So You'd Like to...
|
|
Look for Similar Items by Category
- Books > Computers & Technology > Computer Science > Information Theory
- Books > Computers & Technology > Computer Science > Modeling & Simulation
- Books > Computers & Technology > Computer Science > Software Engineering
- Books > Computers & Technology > Databases > Database Design
- Books > Computers & Technology > Programming > Algorithms > Data Structures
- Books > Computers & Technology > Programming > Functional
- Books > Computers & Technology > Programming > Languages & Tools
- Books > Computers & Technology > Programming > Software Design, Testing & Engineering > Software Development
- Books > Computers & Technology > Programming > Software Design, Testing & Engineering > Structured Design
- Books > Computers & Technology > Software
- Books > Education & Reference
- Books > New, Used & Rental Textbooks > Computer Science > Programming Languages
- Books > New, Used & Rental Textbooks > Computer Science > Software Design & Engineering
