Ten Years of Purely Functional Data Structures (2008)

http://okasaki.blogspot.ru/2008/02/ten-years-of-purely-functional-data.html

by ColinWright • 13 years ago

170 24 13 years ago

okasaki.blogspot.ru

oinksoft• 13 years ago

(2008)

it mentions me! my one claim to fame... here's the review http://developers.slashdot.org/story/04/02/19/2257203/purely...

DanWaterworth4• 13 years ago

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

juliangamble• 13 years ago

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

vowelless• 13 years ago

His thesis is quite useful:

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

jph2• 13 years ago

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

jfb• 13 years ago

$100 here as well.

binarycrusader• 13 years ago

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

jph2• 13 years ago

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.

kenjackson2• 13 years ago

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• 13 years ago

It does have the Haskell versions in the appendix.

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

kenjackson2• 13 years ago

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.

igravious• 13 years ago

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 :(

DanWaterworth4• 13 years ago

> I kind of see Ruby like a hybrid functional language.

Functions aren't even first class in Ruby (though it does have closures). I certainly wouldn't describe it as a hybrid functional language.

riffraff• 13 years ago

I'd refrain from saying "functions aren't first class in ruby", unless you qualify the assertion.

E.g. you could mean "you can't call functions by just adding () at the end", or "the block syntax only allows passing one function", but these are both just syntax differences.

On the other hand, you can create standalone functions, pass them around, introspect them, invoke them, call methods on them and compose them, which is more or less what you can do with integers in python (we can agree integers are first class objects in python, I think)

So there may be reason for saying they are "not first class", but you should expand on it.

pavelludiq• 13 years ago

Common Lisp is in the same category as a FP-ish language but still mostly used in a mutable OO fashion. We have a library called FSET written in CL to add persistent data structures and convenient syntax for them to the language. I don't know how powerful ruby meta-programming is, but I imagine it isn't as easy to do(like add a syntax for persistent maps that is as convenient as the built in one). Not to mention that ruby has a reputation for much worse performance than CL, so you'll likely have to use FFI and write most of it in C.

As for clojure, I think they are all implemented in java, but I haven't been following clojure development in two years, so maybe with protocols they moved them(or could) to clojure? I don't know.

noelwelsh• 13 years ago

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...

mtrimpe• 13 years ago

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.

sfrank• 13 years ago

Sure you can do however, since Ruby allows destructive updates, why not use one of the established/traditional imperative data structures and then apply techniques to make them "persistent" (i.e. immutable in the functional programming sense as is also used by Okasaki and of course not using the trivial technique of copying the whole thing). Such techniques are e.g. presented in CLRS if I remember correctly.

It is not that Okasaki was the first one to implement any functional data structure. People have been doing this before and also in purely functional languages such as Haskell, ML, or Opal). He was the first to give a very nice overview, showed some new designs and even more important, showed a way for time complexity analysis (in a lazy evaluation context).

And it is this last part of the thesis that many people overlook: the importance of lazy evaluation (and thus the implied fundamental optimizations/evaluations performed by the compiler/runtime) for most of the presented data structures (i.e. everything with an amortized time complexity). Simply implementing Queues as presented in the thesis and not having a lazy language will lead to a very different time complexity than is proven there, because lazy semantics is vital for the given complexity analysis.

This is also the reason, why e.g. Clojure (or Opal from the early 90s, [1]) use other data structures to ensure functional (i.e. persistent) semantics in an eager/strict evaluation model.

[1] 1994, http://projects.uebb.tu-berlin.de/opal/trac/raw-attachment/w...

WildUtah• 13 years ago

Rich Hickey says during talks that Clojure's persistent data structures are based on this book and inspired by the Haskell implementation. The book is in Hickey's recommended reading list. Language designers should pursue the books in that list; it's a good one.

http://www.amazon.com/Clojure-Bookshelf/lm/R3LG3ZBZS4GCTH

The main Clojure ('JClojure') implementation has these written in Java but Clojurescript has a pure Clojure implementation and there are Clojure-in-Clojure projects that do the same. The Java versions are still slightly faster on the JVM, unless things have changed.

Clojure does not require you to program in pure functional style like Haskell. You can even write Clojure code with no immutable data structures and always use the Java paradigm data structures instead, though I do not recommend it. The support for mixing both paradigms and also transactional memory are part of the defining flexibility of Clojure. It's not a bondage and discipline affair; Clojure has a strong aesthetic but you can code however you want when you need to.

I think Scala has similar data structures, also.

ludicast• 13 years ago

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.

Ten Years of Purely Functional Data Structures (2008)

Related Stories