
Ten Years of Purely Functional Data Structures (2008) - ColinWright
http://okasaki.blogspot.ru/2008/02/ten-years-of-purely-functional-data.html
======
andrewcooke
it mentions me! my one claim to fame... here's the review
[http://developers.slashdot.org/story/04/02/19/2257203/purely...](http://developers.slashdot.org/story/04/02/19/2257203/purely-
functional-data-structures)

~~~
DanWaterworth
I wonder what other interesting books are out there that just need someone to
review them on slashdot.

------
juliangamble
These ideas are one of the foundations of the Clojure language. Rich Hickey
mentions in one of his talks that this book got him quite excited. You can see
reference to it in Rich Hickey's Clojure bookshelf on Amazon
<http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH>

------
ludicast
I took his PLT class at Columbia and TA-ed the class later. Best professor I
ever had. I believe he is now at West Point where students won't whine when he
hurts their brains.

Would like to see the book re-done with Haskell as the base (rather than
appendix) because that language is more "purely functional" and seems to
finally have the legs it needed back in 2008.

------
vowelless
His thesis is quite useful:

<http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf>

------
igravious
Some questions. Background: I'm coming to the whole world of functional
programming via Ruby (via C).

Doesn't Clojure have purely functional (immutable) data structures? Whenever
this area is talked about I always hear Clojure mentioned. Do other functional
languages have libraries (standard or otherwise) of these? Are these data
structures implemented in Clojure itself?

I kind of see Ruby like a hybrid functional language. Could Ruby be used to
implement the data structures in this book, or would that be like a square peg
in a round hole? Didn't Ruby recently get official lazy evaluation?

Hum, so many questions, so little Google :(

~~~
noelwelsh
Yes, Clojure does have many purely functional data structures built in to its
core. I don't know the precise implementations, or if they're written in
Clojure or Java, but I believe they're based on the work of Phil Bagwell.

Every functional language implementation I know of has many of these data
structures available as a library somewhere.

You certainly could implement these data structures in Ruby, though it's
likely they wouldn't mesh as well as in a more functional language.

This Stackexchange answer has links to many papers if you're interested in
more:

[http://cstheory.stackexchange.com/questions/1539/whats-
new-i...](http://cstheory.stackexchange.com/questions/1539/whats-new-in-
purely-functional-data-structures-since-okasaki)

~~~
mtrimpe
Clojure was also the _first_ mainstream (non-PF) language to implement
Okasaki's as first class data structures.

I know Scala quickly followed suit, since I remember Odersky bragging in a
meetup that he went out of his way to find the scientists that improved on
Okasaki's work and based Scala's data structures on their work instead.

------
kenjackson
Great book. Although I'd like to see an "open source" version when you can get
all the code snippets expressed in the language of your choice. When I read
the book I wanted Haskell, but now I think I'd like to see it in F# or maybe
even C#.

~~~
tikhonj
It does have the Haskell versions in the appendix.

Besides, depending on your perspective, both SML and Haskell are basically
functional pseudocode.

~~~
kenjackson
There was something missing from the Haskell stuff, but I can't recall the
details -- it's been almost 10 years ago since I read it.

But when I am reading a data structures/algorithms book, I don't want to have
to deal with code (SML in this case) that I'm not super familiar with. Little
things get in the way. With modern software, and the ability to dynamically
swap out content, it seems a pity that we don't better tailor content to the
reader.

------
jph
Brilliant. I can donate $100 to get it updated and as a PDF.

~~~
binarycrusader
What is this referring to? I see nothing obvious that mentions a donation or
PDF.

~~~
jph
I'm offering to donate $100 to the author if he would like to update the book
as he mentions in his story, and I'd like to get the book as a PDF instead of
on paper because of the code samples and searching.

This is my personal gift to him because I value his ideas and I hope to learn
more. This may also inspire other people here to offer to donate, which will
be great if it happens.

------
oinksoft
(2008)

