Goodreads helps you keep track of books you want to read.
Start by marking “Purely Functional Data Structures” as Want to Read:
Purely Functional Data Structures
Enlarge cover
Rate this book
Clear rating
Open Preview

Purely Functional Data Structures

4.15  ·  Rating details ·  579 ratings  ·  16 reviews
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 de ...more
Paperback, 232 pages
Published June 13th 1999 by Cambridge University Press (first published September 1996)
More Details... edit details

Friend Reviews

To see what your friends thought of this book, please sign up.

Community Reviews

Showing 1-30
4.15  · 
Rating details
 ·  579 ratings  ·  16 reviews

Sort order
Ettore Pasquini
May 13, 2013 rated it it was ok
Shelves: technology
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
Debasish Ghosh
May 29, 2010 rated it it was amazing
It's a must read for practitioners of functional programming. Okasaki is the Alan Kay of functional programming (as Daniel Spiewak says).
Nov 20, 2012 rated it really liked it
Content is in Standard ML, but not difficult to translate to Haskell. The algorithms presented earlier in the book are quite clear when taken from a functional perspective, none of the pointer manipulation noise that I recall when learning about Data Structures and Algorithms courses at University.

Barış Meriç
Jun 20, 2014 rated it it was amazing
It's "the book" on the functional data structures.
Oct 23, 2007 added it
Phew, 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)
Marc Udoff
May 11, 2016 rated it liked it
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 Sta ...more
Junsong Li
May 06, 2016 added it
Shelves: cs
It'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 I am not motivated to explore related problems)
Mar 05, 2009 rated it really liked it
Fascinating book on a topic not covered by anything else.
Jan 25, 2016 rated it really liked it
Raw functional elegance and performance. Is quite hard to swallow, but pretty good mental exercise
Mar 25, 2018 rated it liked it
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
Alejandro D-P
Feb 05, 2019 rated it it was amazing
A must for any functional developer.
Al Matthews
Jun 29, 2017 rated it really liked it
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.
Franck Chauvel
Sep 01, 2016 rated it it was ok
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 chap
Dec 27, 2010 rated it really liked it
Shelves: computer-science
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 rec ...more
Daniel Lyons
Apr 10, 2012 rated it it was amazing
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.
rated it really liked it
Sep 19, 2015
Eroteme Thinks
rated it really liked it
May 04, 2013
Nikodemus Siivola
rated it it was amazing
Dec 27, 2018
Dmytro Sirenko
rated it it was amazing
Dec 20, 2014
Ashutosh Kumar
rated it really liked it
Aug 24, 2014
rated it it was amazing
May 01, 2012
Abdulfattah Alharby
rated it liked it
Mar 05, 2016
rated it really liked it
Oct 23, 2015
Pete Poulos
rated it it was amazing
Jan 15, 2018
rated it liked it
Aug 17, 2017
rated it really liked it
Sep 09, 2012
Burgess Wong
rated it it was amazing
Dec 25, 2013
rated it it was amazing
Jan 19, 2014
Dmitry Zuikov
rated it really liked it
Dec 17, 2011
Randall Thomas
rated it really liked it
May 23, 2014
« previous 1 3 4 5 6 7 8 9 next »
There are no discussion topics on this book yet. Be the first to start one »
  • Types and Programming Languages
  • Let Over Lambda
  • Pearls of Functional Algorithm Design
  • Real World Haskell: Code You Can Believe In
  • Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP
  • On Lisp: Advanced Techniques for Common Lisp
  • The Reasoned Schemer
  • Concepts, Techniques, and Models of Computer Programming
  • The Haskell Road to Logic, Maths and Programming
  • The Art of the Metaobject Protocol
  • The Joy of Clojure
  • LISP in Small Pieces
  • An Introduction to Functional Programming Through Lambda Calculus
  • Programming Erlang
  • Practical Common LISP
  • Haskell: The Craft of Functional Programming
  • Learn You a Haskell for Great Good!
  • Land of LISP: Learn to Program in LISP, One Game at a Time!

Goodreads is hiring!

If you like books and love to build cool products, we may be looking for you.
Learn more »
“The methodological benefits of functional languages are well known [Bac78, Hug89, HJ94], but still the vast majority of programs are written in imperative languages such as C. This apparent contradiction is easily explained by the fact that functional languages have historically been slower than their more traditional cousins, but this gap is narrowing.” 0 likes
“A distinctive property of functional data structures is that they are always persistent—updating a functional data structure does not destroy the existing version, but rather creates a new version that coexists with the old one. Persistence is achieved by copying the affected nodes of a data structure and making all changes in the copy rather than in the original.” 0 likes
More quotes…