Purely Functional Data Structures (1996) [pdf] | Hacker News Reader

Purely Functional Data Structures (1996) [pdf]

cs.cmu.edu

83 pointsjoubert13 comments

I worked through the book a couple years ago, implementing the data structures in Haskell. It was an enlightening experience. One of these days I'd like to go back and pay more attention to the analysis.

I'll add that the book has a good amount of exercises, both theoretical and implementation-related. It's worth noting that the book also includes the Haskell implementations of the data structures. Not that Standard ML is difficult to understand but hey, it's a plus!

Please, remember that this is PhD thesis - book covers slightly more...

And for even more see http://cstheory.stackexchange.com/questions/1539/whats-new-i...

The next time someone argues handwavily that pure functional programming makes code "easy to reason about," consider the fact that implementing a data structure as simple as a double-ended queue in that paradigm was PhD level work.

If someone doing a PhD on some subject made it PhD level and inaccessible to non PhDs, you wouldn't be able to use virtually any of the data structures you use today.

Additionally, even if discovery of a certain pure algorithm is difficult, that doesn't mean that using that algorithm (especially one abstracted behind a nice API) is difficult.

There's no doubt that not having aliasing everywhere, and having basic laws available about the behavior of programs and combinators aids in reasoning about programs.

Every implementation in Okasaki is easier than an analogous imperative/ephemeral one. Every single one.

You can build ephemeral data structures in functional languages, and persistent data structures in imperative languages. (It's just not their default idiom.)

The ease and simplicity of the book's implementations owes to pattern matching syntax more than anything else.

As an aside: pattern matching on algebraic datatypes is awesome, and just like other innovations before, like garbage collection and first-class closures, I hope to see it transplanted to more and more mainstream languages.

Yes, I know it! This is beside my point, but it is of course definitely true.

I imagine the very first imperative implementations of those algorithms was PhD level work as well.

Reasoning about pivot selection in quicksort was once PhD-level work.

The concept of energy makes motion easier to reason about, but it took some of the greatest scientists in human history to come up with that idea.

So I guess you'd have us all read Aristotle and be arrogant and proud of our state of ignorance?

The simplest functional double-ended queue is actually really easy to code up and reason about.

It's the more complicated optimizations that were PhD work. But designing fast persistent data structures in an imperative setting ain't easier.

(To avoid confusion: `persistent' used here as the opposite of `ephemeral', and without any relation to saving to disk.)

Reply on news.ycombinator.com