What do you think?
Rate this book
Purely Functional Data Structures
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.
232 pages, Paperback
First published September 1, 1996
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 19 of 19 reviews
September 2, 2015
This book is mainly for computer scientists, not so much for engineers. The emphasis is first and foremost on theory and it didn't provide enough practicality for me.
The choice of language for this book -- Standard ML -- is in line with the above: Standard ML is used in research but not as much in the industry as other languages like Haskell, Erlang, Clojure, Scala. How many people are you reaching with this choice? True, there is Haskell source code at the end of the book, and sure I can think of the reason why SML was chosen (being defined formally in a very concise way, leaving out implementation details, etc) but still, I can’t shake the feeling that this choice is somewhat elitist and limiting.
Plus SML is not even a pure functional language!
The other problem I have with this book is that the “purely functional” part of the title doesn’t come out as clearly as I wanted to. Could be it’s just me since I mainly code in OO languages, but after the first 3 chapters there’s a lot of data/state manipulation which resonated more as imperative than functional to me. (After all SML has some imperative features.) The initial chapters instead spent time bringing this out, and those are the ones I enjoyed the most.
I did take away something though:
- the explanation of persistence vs performance was cool. At first this was confusing because what they refer to as persistence I call immutability. So, persistence requires that (e.g.) when joining 2 lists into one, the original lists need to be unchanged even if the joining operation should be performant. This requires copying the original lists but in practice only parts of the lists need to be copied. Very cool.
- There’s a good run-through data structures I never once used professionally (binomial heaps, leftists heaps, red black trees, splay trees, …) so it was nice to read about them.
- The explanation of amortization: for some collections where we need to perform some kind of processing on each item, we may not care if one item takes O(log n) or even O(n) as long as the overall computation is still O(n).
- After studying the persistence + memoization + lazy evaluation + amortization theory it applied it to a queue implemented as 2 lists (front and rear), rotating its elements to amortize the cost of each insert/delete/etc operation to O(1). I didn’t have the time to dive deep into this but it’s something it’d be cool to do one day... If they ever translate this book to Erlang or some other purely functional language!
The choice of language for this book -- Standard ML -- is in line with the above: Standard ML is used in research but not as much in the industry as other languages like Haskell, Erlang, Clojure, Scala. How many people are you reaching with this choice? True, there is Haskell source code at the end of the book, and sure I can think of the reason why SML was chosen (being defined formally in a very concise way, leaving out implementation details, etc) but still, I can’t shake the feeling that this choice is somewhat elitist and limiting.
Plus SML is not even a pure functional language!
The other problem I have with this book is that the “purely functional” part of the title doesn’t come out as clearly as I wanted to. Could be it’s just me since I mainly code in OO languages, but after the first 3 chapters there’s a lot of data/state manipulation which resonated more as imperative than functional to me. (After all SML has some imperative features.) The initial chapters instead spent time bringing this out, and those are the ones I enjoyed the most.
I did take away something though:
- the explanation of persistence vs performance was cool. At first this was confusing because what they refer to as persistence I call immutability. So, persistence requires that (e.g.) when joining 2 lists into one, the original lists need to be unchanged even if the joining operation should be performant. This requires copying the original lists but in practice only parts of the lists need to be copied. Very cool.
- There’s a good run-through data structures I never once used professionally (binomial heaps, leftists heaps, red black trees, splay trees, …) so it was nice to read about them.
- The explanation of amortization: for some collections where we need to perform some kind of processing on each item, we may not care if one item takes O(log n) or even O(n) as long as the overall computation is still O(n).
- After studying the persistence + memoization + lazy evaluation + amortization theory it applied it to a queue implemented as 2 lists (front and rear), rotating its elements to amortize the cost of each insert/delete/etc operation to O(1). I didn’t have the time to dive deep into this but it’s something it’d be cool to do one day... If they ever translate this book to Erlang or some other purely functional language!
September 29, 2019
This book was EXACTLY what I expected it to be.
February 9, 2011
It's a must read for practitioners of functional programming. Okasaki is the Alan Kay of functional programming (as Daniel Spiewak says).
May 11, 2016
This book is a little much for someone who doesn't write code in StandardML or Haskell or a pure functional language. If you do code in these languages his examples and code and style is very clear. Otherwise, even if you work in a language that supports functions as a first class citizen (e.g. JavaScript), you can sort of grasp what he is saying, but you won't feel like you are learning that much. I would not recommend this to anyone as a way to learn about FP, without already understanding StandardML.
Read
August 12, 2015Phew, one of those books that you really get only as much as you put into.
Worth it, but prepare to work :-)
(I'm afraid i was far lazier than I should have been)
Worth it, but prepare to work :-)
(I'm afraid i was far lazier than I should have been)
June 20, 2014
It's "the book" on the functional data structures.
Read
August 23, 2016It's great to see persistent data structure simplifies its implementation, but I don't really see the context of the second half of this book. (Sign. I don't have applications for them...so I am not motivated to explore related problems)
March 5, 2009
Fascinating book on a topic not covered by anything else.
January 25, 2016
Raw functional elegance and performance. Is quite hard to swallow, but pretty good mental exercise
March 25, 2018
A very academic text, dense with complex ideas and tedious to work through; I don't think it ever took me as long to make it through a mere 180 pages. I started to skim most of the code listings and proofs half way through the book and the author definitely lost me several times with his sparse descriptions of complex but often genius ideas.
Which is really why I think it was worth the effort to untangle this mess: even if you only get the gist of some of the topics covered in this book, they're really mind bending at times. There are some remarkably cool ideas here, such as the (somewhat Gödelian) approach to implementing data structures using isomorphisms with binary number systems.
Overall, however, I don't think I got a lot out of this book, certainly not anything I can see me apply to my daily programming routine.
Which is really why I think it was worth the effort to untangle this mess: even if you only get the gist of some of the topics covered in this book, they're really mind bending at times. There are some remarkably cool ideas here, such as the (somewhat Gödelian) approach to implementing data structures using isomorphisms with binary number systems.
Overall, however, I don't think I got a lot out of this book, certainly not anything I can see me apply to my daily programming routine.
March 31, 2021
Okasaki's book is a must-have for anyone who wants to see how to tackle algorithms in a functional style. After presenting some basic amortization analysis styles, he runs through a number of important data structures, including what appears to me to be an obviously better presentation of red-black trees than e.g. CLR.
May 17, 2022
Very good, but restricted to solutions that can be implemented in purely functional code. Consider first reading the article Making Data Structures Persistent by James Driscoll first, to see how data structures that are used functionally can be implemented in impure code:
https://www.cs.cmu.edu/~sleator/paper...
https://www.cs.cmu.edu/~sleator/paper...
June 29, 2017
Thesis available as PDF. The print copy contains the ML code translated into Haskell. I'm on record as saying that the Haskell is incompletely implemented, but by now I imagine I'm wrong.
February 5, 2019
A must for any functional developer.
June 30, 2021
While this book takes some deliberate effort to digest, it’s well worth it to gain some insight about a number of fundamental functional programming techniques.
Read
December 11, 2022u
December 28, 2010
What data structures would you use in a purely functional programming language? A list is okay: all of the operations it supports, which is to say car, cdr and cons, are non-destructive and execute in O(1) time. A stack is just a list, and a queue can be modeled by two lists; we get from one and put onto the other; when the first list gets empty, we reverse the second list and make it the first; the amortized time complexity is still O(1). When we update an unbalanced binary tree, we need to recreate all the nodes from the root to the updated node, but do not have to touch any other nodes; if there is a balancing condition, things get more complicated. There is a natural correspondence between numeral systems and data structures: unary corresponds to a list, binary corresponds to a binary tree, and there is a special numeral system called skew binary, which corresponds to a list of binary trees with nice time complexity properties.
September 9, 2016
This book explains how to build purely functional data structure, that is, persistent structures that are not directly modified but rather copied and rebuild. Chris explains how to use lazy evaluation and other advanced functional techniques in order to reconcile functional programming and efficiency.
First, the book does not read exactly like a novel. It is dense and technical and tackles difficult question. Hopefully the chapters are self contained and one can worked them separately. Every chapters requires more work and time than I was willing to spend.
Still, I found the topic too narrow. Functional programming remains a niche and I believe most programmers seldom develop their own data structure, but reuse tried and tested modules—as good professionals. This book will please the curious and the mathematically oriented, but will be less useful for the regular/professional practitioners, I believe.
First, the book does not read exactly like a novel. It is dense and technical and tackles difficult question. Hopefully the chapters are self contained and one can worked them separately. Every chapters requires more work and time than I was willing to spend.
Still, I found the topic too narrow. Functional programming remains a niche and I believe most programmers seldom develop their own data structure, but reuse tried and tested modules—as good professionals. This book will please the curious and the mathematically oriented, but will be less useful for the regular/professional practitioners, I believe.
April 10, 2012
This book is for FP what Design Patterns is for OOP. Read through Chapter 3 and functional purity and persistence will become clear. I consider the rest of the book optional advanced reading. Highly recommended.
Displaying 1 - 19 of 19 reviews