8 ms·
Purely Functional Data Structures (1996) [pdf]
- alexott 11y agoPlease, remember that this is PhD thesis - book covers slightly more...
- agumonkey 11y agoAnd for even more see http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki http://cstheory.stackexchange.com/questions/1539/whats-new-i...
- greydius 11y agoI 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.
- cranium 11y agoI'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!
- laretluval 11y agoThe 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.
- Peaker 11y agoIf 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.
- jonsterling 11y agoEvery implementation in Okasaki is easier than an analogous imperative/ephemeral one. Every single one.
- eru 11y agoYou 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.
- jonsterling 11y agoYes, I know it! This is beside my point, but it is of course definitely true.
- jimbokun 11y agoI imagine the very first imperative implementations of those algorithms was PhD level work as well.
- candu 11y agoReasoning about pivot selection in quicksort was once PhD-level work.
- Retra 11y agoThe 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?
- eru 11y agoThe 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.)