There's also a nice addendum on cstheory.stackexchange, "What's new in purely functional data structures since Okasaki?" - <a href="https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki" rel="nofollow">https://cstheory.stackexchange.com/questions/1539/whats-new-...</a>
I'm reading this book right now. It's really great so far!<p>I've been working a lot with Trees in Clojure, and have been hitting serious limitations of my understanding.<p>I also found this YouTube video from a Clojure conference that reviews some different strategies for tree traversal in Clojure: <a href="https://youtu.be/YgvJqWiyMRY" rel="nofollow">https://youtu.be/YgvJqWiyMRY</a><p>I thought that learning a Functional Lisp would make it really easy to traverse trees, since that is that the language is doing to actually execute its code.<p>Turns out all the stuff I want to do is simply hard.<p>Functional data structures are really awesome though, it just seems to take a bit of up front investment.
This is the canonical guide to reasoning about amortized runtimes. The exponentially growing ArrayBuffer (O(1) amortized append) is the classical data structure used to teach amortized runtimes, but the O(1) amortized functional queue Okasaki presents here gives a much better intuition for what amortized runtimes are all about.
There's a book which looks like it's based on this dissertation, which probably is a better source to read if you are interested in this topic: <a href="https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504" rel="nofollow">https://www.amazon.com/Purely-Functional-Data-Structures-Oka...</a>
For C++ check this one out - <a href="https://github.com/arximboldi/immer">https://github.com/arximboldi/immer</a> and this talk from the author - <a href="https://www.youtube.com/watch?v=_oBx_NbLghY">https://www.youtube.com/watch?v=_oBx_NbLghY</a> (CppCon 2018: Juan Pedro Bolivar Puente “The Most Valuable Values”)
It's weird that there are so many claims in here that the data structures and algorithms are perfectly performant yet there isn't even one look at generated assembly or any acknowledgement of the underlying system that is supposed to <i>run</i> the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.
is this being upvoted onto the homepage based on upvoters actually understanding that this paper from 1996 is of contemporary relevance and interest or more due to keywords like "pure", "functional", "data" and "structure"?
I would love to be educated. I've seen claims about the merit and value of functional programming throughout my (nowadays relatively long) programming career. In practice I've never once seen those values or merits come to fruition - just the same cycle all software goes through.<p>My very direct experience recently has been Scala + cats resulted in the same buggy nonperformant software it was meant to prevent. I understand that bad programmers produce bad programs, regardless of language, but I feel pretty strongly that good tools prevent some amount of the typical "bad" that makes bad programs bad (ignoring the obviously maliciously bad examples). So I don't really understand, and would like to understand, if, how and when pure FP (and I suppose FP in general) actually improve quality of code/life outside of toy examples.
title typo: "Purely Functional Data Structure" -> "Purely Functional Data Structures" (pluralization)<p>reads a bit weird otherwise - sounds like it's discussing a particular purely functional data structure when it's actually a survey of many (pretty much the canonical survey of them, in fact).
What are software bugs that can be avoided by choosing data structures like these?<p>I'm making a broad, high-level presentation about immutability in technology. At my company we have folks who have heard of it in the context of ransomware-resilient backups, others who have heard of it in the context of infrastructure as code, and very few who have heard of it in terms of data structures (distributed and non-distributed). My goal is to showcase the concept in various contexts so that people can better understand its role as a key design choice in technology.<p>Personally I have no experience working on software that utilizes these, so if others here do, I would appreciate your input on how these make your software more reliable.<p>The emphasis on software reliability and bugs-avoided is because the audience works under the company's risk-management division.
Okasaki got me interested in confluently persistent data-structures, way back in the 2000s.<p>They seem magical! To be able to combine data from the past with current data, efficiently!<p>They are almost always trees, with the exception of skip-lists, with all operations O(log(n)), .<p>After creating my own programming language Enchilada that is based on immutable data structures, I started considering what I deemed "next level":<p><i>Uniquely represented confluently persistent data structures</i><p>Combined with a Merkle tree encoding of such uniquely represented data structures (they are almost always trees), you can efficiently and incrementally authenticate them. Think 'block chain' on steroids, with incremental cryptographic hashes. Or torrents, if you are into that kind of thing.
<i>Why</i> would we want to use purely functional data structures? When do the pros of functional data structures outweigh the additional complexity? Are there scenarios when a project would want to pivot from a regular data structure to a purely functional one?
This book is near and dear to my heart. Back in the mists of time (~05?) when I was learning Haskell I reimplemented several of these in order to get my head around things. Lots of fond memories.
For me, the most mind-blowing part of Okasaki's book was the chapter on "numerical representations". Never looked at it like that before I read that chapter. While the other chapters certainly introduced material that was new to me at the time, this one took some things I knew and added a whole new dimension to them.
I have a personal pet peeve about the misuse of terminology when dealing with such names, for which the only solution is to go read the original reference to figure out what they meant by it.<p>E.g., in this case, to describe a data structure as "purely functional" makes zero sense to me intuitively at first. You need to go read the thesis and realise they're referring to data structures implemented as algebraic data types, which in the context of a purely functional language can themselves be thought of as functions, and can therefore be described as 'functional' ...<p>But unless you do that, the first thought is going to be "huh? can arrays be further split into imperative vs functional?" "Does he mean immutable?" "Can I use functional arrays in c?" "Are they faster/safer than normal arrays?".<p>By contrast, I think "Purely Functional Data-Structure Types" would have been a far more intuitive term ... but I suppose the author may have felt that clarifying further wasn't punchy enough, and could have made the thesis more wordy...
Related. Others?<p><i>Purely Functional Data Structures in Elm – course lecture notes (2015)</i> - <a href="https://news.ycombinator.com/item?id=12145741" rel="nofollow">https://news.ycombinator.com/item?id=12145741</a> - July 2016 (15 comments)<p><i>What's new in purely functional data structures since Okasaki? (2010)</i> - <a href="https://news.ycombinator.com/item?id=11056704" rel="nofollow">https://news.ycombinator.com/item?id=11056704</a> - Feb 2016 (42 comments)<p><i>Purely Functional Data Structures (1996) [pdf]</i> - <a href="https://news.ycombinator.com/item?id=10486481" rel="nofollow">https://news.ycombinator.com/item?id=10486481</a> - Nov 2015 (13 comments)<p><i>Okasaki: Purely Functional Data Structures (1996) [pdf]</i> - <a href="https://news.ycombinator.com/item?id=8327838" rel="nofollow">https://news.ycombinator.com/item?id=8327838</a> - Sept 2014 (1 comment)<p><i>What's new in purely functional data structures since Okasaki? (2010)</i> - <a href="https://news.ycombinator.com/item?id=7081191" rel="nofollow">https://news.ycombinator.com/item?id=7081191</a> - Jan 2014 (17 comments)<p><i>Ten Years of Purely Functional Data Structures (2008)</i> - <a href="https://news.ycombinator.com/item?id=5701396" rel="nofollow">https://news.ycombinator.com/item?id=5701396</a> - May 2013 (24 comments)<p><i>What's new in purely functional data structures since Okasaki?</i> - <a href="https://news.ycombinator.com/item?id=1983461" rel="nofollow">https://news.ycombinator.com/item?id=1983461</a> - Dec 2010 (2 comments)<p><i>What's new in purely functional data structures since Okasaki</i> - <a href="https://news.ycombinator.com/item?id=1713594" rel="nofollow">https://news.ycombinator.com/item?id=1713594</a> - Sept 2010 (1 comment)<p><i>"Purely Functional Data Structures" by Chris Okasaki [pdf]</i> - <a href="https://news.ycombinator.com/item?id=1138979" rel="nofollow">https://news.ycombinator.com/item?id=1138979</a> - Feb 2010 (12 comments)<p><i>Teaching, Playing, and Programming: Ten Years of Purely Functional Data Structures</i> - <a href="https://news.ycombinator.com/item?id=112270" rel="nofollow">https://news.ycombinator.com/item?id=112270</a> - Feb 2008 (2 comments)<p><i>Chris Okasaki's PhD thesis on purely functional data structures (pdf)</i> - <a href="https://news.ycombinator.com/item?id=8221" rel="nofollow">https://news.ycombinator.com/item?id=8221</a> - April 2007 (1 comment)