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.16  ·  Rating details ·  623 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
Average rating 4.16  · 
Rating details
 ·  623 ratings  ·  16 reviews

More filters
Sort order
Start your review of Purely Functional Data Structures
Rose Smith
Sep 28, 2019 rated it it was amazing
This book was EXACTLY what I expected it to be.
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
Piyush Katariya
rated it really liked it
Nov 15, 2019
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
« 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 »

Readers also enjoyed

  • Hacker's Delight
  • Types and Programming Languages
  • Learn You a Haskell for Great Good!
  • Seven Languages in Seven Weeks
  • Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)
  • Programming Language Pragmatics
  • Real World Haskell: Code You Can Believe In
  • Introduction to Algorithms
  • The C++ Programming Language
  • Algorithms to Live By: The Computer Science of Human Decisions
  • The Little Schemer
  • LISP in Small Pieces
  • The Art of Computer Programming, Volume 1: Fundamental Algorithms
  • Programming Clojure
  • The Dictator's Handbook: Why Bad Behavior is Almost Always Good Politics
  • Programming in Scala
  • Compilers: Principles, Techniques, and Tools
See similar books…

Goodreads is hiring!

If you like books and love to build cool products, we may be looking for you.
Learn more »

News & Interviews

As dedicated readers already know, some of the best and most innovative stories on the shelves come from the constantly evolving realm of young ...
31 likes · 11 comments
“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.” 1 likes
“The notion of amortization arises from the following observation. Given a sequence of operations, we may wish to know the running time of the entire sequence, but not care about the running time of any individual operation. For instance, given a sequence of n operations, we may wish to bound the total running time of the sequence by O(n) without insisting that every individual operation run in O(1) time. We might be satisfied if a few operations run in O(log n) or even O(n) time, provided the total cost of the sequence is only O(n). This freedom opens up a wide design space of possible solutions, and often yields new solutions that are simpler and faster than worst-case solutions with equivalent bounds.” 1 likes
More quotes…