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 ·  639 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 September 16th 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.15  · 
Rating details
 ·  639 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). ...more
Barış Meriç
Jun 20, 2014 rated it it was amazing
It's "the book" on the functional data structures. ...more
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) ...more
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
John Clements
Mar 30, 2021 rated it it was amazing
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. ...more
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. ...more
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
Dmitry Zuikov
rated it really liked it
Dec 17, 2011
« 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

  • The Mythical Man-Month: Essays on Software Engineering
  • Hacker's Delight
  • JavaScript: The Good Parts
  • Compilers: Principles, Techniques, and Tools
  • Coders at Work: Reflections on the Craft of Programming
  • How to Design Programs: An Introduction to Programming and Computing
  • Classical Form: A Theory of Formal Functions for the Instrumental Music of Haydn, Mozart, and Beethoven
  • The Oxford History of Western Music: College Edition
  • Analyzing Classical Form: An Approach for the Classroom
  • A History of Loneliness
  • Golden Hill
  • Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)
  • The Spotify Play: How CEO and Founder Daniel Ek Beat Apple, Google, and Amazon in the Race for Audio Dominance
  • TypeScript Quickly
  • The Film Buff's Bucket List
  • Battle Hymn of the Tiger Mother
  • Billion Dollar Loser: The Epic Rise and Spectacular Fall of Adam Neumann and WeWork
  • The Devil's Highway: A True Story
See similar books…

Goodreads is hiring!

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

Related Articles

Juneteenth, observed on June 19th each year, is an American holiday commemorating the day in 1865 when the last enslaved people in Galveston,...
112 likes · 16 comments
“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…