9 ms·
Purely Functional Data Structures (1996) [pdf]
- okennedy 3y agoThis 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.
- 2-718-281-828 3y agois 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"?
- ufo 3y agoIt is is still the go-to textbook for immutable data structures. Worth the read.
- paulgb 3y agoI can’t speak for everyone, but I upvoted it from nostalgia, having read the book version over a decade ago. I happened to be thinking about ordering a copy for the office just yesterday.
- dllthomas 3y agoI have a copy on my desk. The bit about designing data structures by analogy to number systems (and limiting carry propagation) is really fun.
- bradrn 3y ago> is this being upvoted onto the homepage based on upvoters actually understanding that this paper from 1996 is of contemporary relevance and interest …? In my case, yes.
- jstrieb 3y agoI've recently used a number of structures that I learned from this book. Though I don't know if the text represents the state of the art in purely functional data structures, it's a pretty seminal work in the area.
- UncleMeat 3y agoNowhere near the state of the art. Lots of improvements since this was published. It is a good book for learning. It is a decent book for reference. When you want to really fly you will want to reach for more recent work.
- hardlianotion 3y agoExamples of more recent work for us non-specialists?
- nequo 3y agoSee the commenter here: https://news.ycombinator.com/item?id=36125110 https://news.ycombinator.com/item?id=36125110
- hardlianotion 3y agoMissed it - thanks
- schaefer 3y agoThis comment reads as if there is a clear, contemporary successor for learning pure functional data structures. Is there? If so, please do share a reference.
- bluepod4 3y agoYour comment is giving early 2010s hipster “you probably never heard of it” vibes.
- turtleyacht 3y agoThe book is on Amazon, but this submission had those keywords, plus it's a PDF. Of course it is of contemporary relevance; functional programming (FP) is all the rage. The tricky bit are questions like How does this jive with existing JS functional constructs like "fantasy land," for example. How to "recruit" more folks to FP, or even a hybrid approach of objects interacting functionally Game jams using more FP-like data structures? Or more HN submissions like that. The harder things to evaluate are a lot of other topics, news-like but investigative and curious, or sites that are essentially selling a service (versus teaching the mechanism behind it). For SaaS stuff, since HN is about startups, I have to let it slide. But the hacking piece is when one person accomplishes something with persistent decomposition of sequential problems, or does something clever using tools or ideas from a different context.
- solomatov 3y agoMy understanding is that the book is based on this PhD dissertation.
- turtleyacht 3y agoOh.. then, yes--this was unabashedly a (positively) triggered reaction (fortunately or unfortunately).
- rntz 3y agotitle typo: "Purely Functional Data Structure" -> "Purely Functional Data Structures" (pluralization) 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).
- debanjan16 3y agoThanks for pointing it out. I totally missed it. Sorry.
- aeonik 3y agoI'm reading this book right now. It's really great so far! I've been working a lot with Trees in Clojure, and have been hitting serious limitations of my understanding. I also found this YouTube video from a Clojure conference that reviews some different strategies for tree traversal in Clojure: https://youtu.be/YgvJqWiyMRY https://youtu.be/YgvJqWiyMRY 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. Turns out all the stuff I want to do is simply hard. Functional data structures are really awesome though, it just seems to take a bit of up front investment.
- smabie 3y agoI feel like they are.. not so awesome: they are grossly inefficient due to all the pointer chasing and are pretty much guaranteed to be slower than the alternative since they trash your cache.
- aeonik 3y agoMost of the problems I'm trying to solve require those pointers anyway. Tracking diffs and versions of data over time: Version control systems and RDMS just don't cut it. Bitemporal databases are interesting to me as well.
- jfoutz 3y agoI wish I could remember the exact book, I think it's _writing solid code_. There was a long example about the excel evaluation engine back in the day when it was shipped on CD's and had to be perfect. The approach was, use one big dumb slow, but understandable and correct implementation, in parallel, use the lightning fast super whiz bang new implementation. Since both shared the same interface, they could be swapped out, or both run at the same time. I think there is real value in starting with the pure functional versions, then swapping out when needed. One problem that seems fairly common in large codebases is using an object as a hash key. but as the code grows, that object sort of gets passed around and eventually somebody updates it without rehashing. That's a tough bug find. They are for me anyway. This is one of those rare cases where you can actually make it faster later without trashing the overall design. I'd encourage starting with the pure functional version first, every time. I'd go further and say, leave some opportunity to flip back to the pure functional version in dev builds for isolating heisenbugs. Blah blah, grain of salt, free advice, your milage may vary, Games have different requirements than webpages, everything is contextual. This is one rare case where it's always worth having the capability of swapping back and forth is worth it. Just use it, and think hard before giving it up is a really good default.
- gexahaha 3y agoThere's also a nice addendum on cstheory.stackexchange, "What's new in purely functional data structures since Okasaki?" - https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki https://cstheory.stackexchange.com/questions/1539/whats-new-...
- mefarza123 3y agoSince Okasaki's work there have been several advancements and new developments in the field:(Source: MirrorThink.ai) 1. PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections - 2022: This paper introduces PaC-trees, a purely functional data structure that supports parallel and compressed collections. PaC-trees are designed to be efficient in terms of space and time complexity while maintaining the benefits of functional data structures. 2. Proving tree algorithms for succinct data structures - 2019: This paper discusses the development of tree algorithms for succinct data structures, which are compact representations of data that support efficient query and update operations. These is some work in other fields too: 1. CyBy2: a strongly typed, purely functional framework for chemical data management - 2019-12-30: This paper presents CyBy2, a purely functional framework for managing chemical data. The framework is designed to be strongly typed and enforce referential transparency through the type system. 2. chemf: A purely functional chemistry toolkit - 2012-12-20: This paper introduces chemf, a purely functional chemistry toolkit that provides a set of algorithms and data structures for working with chemical data in a functional programming context.
- bafe 3y agoI'm not so sure about cyby2, the persistence is based on "conventional" relational DBs. Judging by the paper, the main goal wasn't developing a specialised functional data structure to store molecules
- anfelor 3y agoI would also recommend Koen Claessen's simplified finger trees (https://dl.acm.org/doi/abs/10.1145/3406088.3409026 https://dl.acm.org/doi/abs/10.1145/3406088.3409026) and Zip trees (https://arxiv.org/pdf/1806.06726.pdf https://arxiv.org/pdf/1806.06726.pdf) for purely functional skip lists.
- eointierney 3y agoI remember encountering an early draft when he was still doing his masters? Absolutely cracking paper, one for the ages. Thanks Chris :)
- paddw 3y agoIt would be cool if someone could translate this into Typescript or the like, I think it would make it a lot more readable.
- haskellandchill 3y agoTypeScript is much less readable than Haskell and OCaml, but you can easily find translations to TypeScript such as https://github.com/skeate/lambdata https://github.com/skeate/lambdata.
- nequo 3y ago> TypeScript is much less readable than Haskell and OCaml That's like saying that Norwegian is much less readable than Italian. It is in the eye of the beholder. They can both express the same concepts but which one is more readable depends on which one you already know.
- substation13 3y agoUsing this to push Brainfuck at work
- consilient 3y ago> They can both express the same concepts Only in the turing tarpit sense. Out of the box, they have very different capabilities. For example: Higher-kinded types: easy in Haskell, hard in OCaml, mostly impossible in Typescript. First-class modules: OCaml has them, Typescript can sort of simulate them with extraordinarily unsafe prototype mangling stuff that you should never ever use, impossible in Haskell Open variants: Easy in OCaml and Typescript, hard in Haskell
- solomatov 3y agoThere'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: https://www.amazon.com/Purely-Functional-Data-Structures-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Data-Structures-Oka...
- 1MachineElf 3y agoWhat are software bugs that can be avoided by choosing data structures like these? 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. 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. The emphasis on software reliability and bugs-avoided is because the audience works under the company's risk-management division.
- thethimble 3y agoPurely functional data structures are very common in purely functional languages like Haskell but are also used in non functional languages via libraries like immutable.js. At a high level, immutability forces you to be extremely deliberate about state changes in your application. This improves reasoning/understanding, reduces bugs, and eases debugging. An example of immutability that you might be familiar with would be react props/state. You don’t modify your state. This makes reasoning about state much more simple.
- red_admiral 3y ago_Immutable_ data structures (not 100% the same thing, but a lot of overlap) avoid all kinds of concurrency problems, because you can safely pass them around and you'll never get a data race. You don't even need any locking (just to make things complicated, _lock-free_ data structures are another closely related but not identical concept). Once you're running a distributed system, this kind of stuff comes into its own.
- taeric 3y agoCareful with this wording. They avoid shared memory mutations. They don't necessarily change data races. Rather, they just change them since, by definition, every edit is now creating stale data. At large, in distributed software, this is a distraction. Since most passing of messages around from one distributed piece to the other was already doing a copy across mediums. Such that sent data was already immutable from the senders perspective. (Granted, the preparation step can have you step on your own feet.)
- mklauber1 3y agoDefinitely read that headline as "Purely Fictional Data Structures". My disappointment is immense.
- 082349872349872 3y agoPurely Fictional Data Structures include: To Queue a Mockingbird The Call-stack of the Wild Tesselation of the d'Urbervilles One Flew Over the Cuckoo Hash The Data of the Woosters Brideshead Re-visitor The Catcher in the Trie Les Miser-tables The Nat-elim of Monte Cristo
- gowld 3y ago> The Catcher in the Trie https://en.wikipedia.org/wiki/Trie#History,_etymology,_and_pronunciation https://en.wikipedia.org/wiki/Trie#History,_etymology,_and_p... and the counterpart, Purely Fictional Languages: The Catcher in the *Try*
- tmtvl 3y agoIt'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 run the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.
- shepherdjerred 3y ago> at some point the code has to hit hardware Yes, but that's not a concern of a computer scientist. Implementation and execution of the algorithm are up to the reader. It's like complaining that engineers don't do enough novel computer science research; of course they don't! It's not their job.
- Gravityloss 3y agoWhich profession is expected to make progress on actual software performance?
- shepherdjerred 3y agoComputer scientists (and of course engineers) both care about real-world performance, but some computer scientists just care about the theory.
- fjeifisjf 3y agoThat's a very naive view of computer science. That is the attitude of people who have given up and decided that computers are too big for science now.
- shepherdjerred 3y agoYou're right, there are plenty of papers focusing on real-world performance. I chose not to capture the nuance because I wasn't sure how to express it succinctly.
- chalcolithic 3y agomy dream language is rebol with immutable data structures only
- weeksie 3y agoThis 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.
- lemper 3y agothis literature was my "serious" introduction to fp. implemented some of the data structure on f#.
- user2342 3y agoThanks. I have the printed book, but a PDF is much more comfortable!
- EddieEngineers 3y agoWhy 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?
- toolslive 3y agothey have some nice properties that you might want to benefit from. For example, they're persistent: every previous state of the data structure is still in there.. aka snapshots!
- yawaramin 3y agoDo you use git? The git commit graph is a purely functional data structure.
- haroldl 3y agoThe most common point is that they're safe to share between threads making parallel algorithms easier to invent, understand, and implement correctly. You can also safely re-use sub-structures without performing a deep copy. For example, if you want to keep a sub-tree around for later you can do that in O(1) time because it's safe to keep a reference to it. If it is a mutable tree you don't know what's going to happen to it so you need to do a deep copy of the entire sub-tree you're holding on to. This can save a lot on memory allocation and copying depending on your use case.
- wtetzner 3y agoThere's a tradeoff between the complexity of the implementation of a data structure, and the use of one. While the complexity of implementing purely functional data structures is often (except maybe in the case of singly linked lists) higher than their mutable counterparts, actually using them in a program is simpler and less error prone. There are obviously other trade offs as well, like performance and memory usage.
- rg111 3y agoDeep Learning applications is one area. Traditionally, OO code is written all the time. But after I learned JAX/Flax, a light turned on inside my head and I now write functional Deep Learning code as much as I can. All my side projects and new code are purely functional in JAX/Flax. PyTorch has functional API known as functorch, and I have used it one project. Where lots and lots of data in 3,4,5 dimensional tensors exist, and you need to run lots of transformation on them, and then you need to multiply a huge number of them thousand times in each second- functional code makes much more sense and gives immense sanity and peace of mind. Those of you writing Deep Learning code, learn functional programming principles (immutable data, pure functions, leaving no side effect, etc.), and apply them to DL via functorch or JAX. Your life will never be the same.
- malkia 3y agoFor C++ check this one out - https://github.com/arximboldi/immer https://github.com/arximboldi/immer and this talk from the author - https://www.youtube.com/watch?v=_oBx_NbLghY https://www.youtube.com/watch?v=_oBx_NbLghY (CppCon 2018: Juan Pedro Bolivar Puente “The Most Valuable Values”)
- tpoacher 3y agoI 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. 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' ... 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?". 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...
- dang 3y agoRelated. Others? Purely Functional Data Structures in Elm – course lecture notes (2015) - https://news.ycombinator.com/item?id=12145741 https://news.ycombinator.com/item?id=12145741 - July 2016 (15 comments) What's new in purely functional data structures since Okasaki? (2010) - https://news.ycombinator.com/item?id=11056704 https://news.ycombinator.com/item?id=11056704 - Feb 2016 (42 comments) Purely Functional Data Structures (1996) [pdf] - https://news.ycombinator.com/item?id=10486481 https://news.ycombinator.com/item?id=10486481 - Nov 2015 (13 comments) Okasaki: Purely Functional Data Structures (1996) [pdf] - https://news.ycombinator.com/item?id=8327838 https://news.ycombinator.com/item?id=8327838 - Sept 2014 (1 comment) What's new in purely functional data structures since Okasaki? (2010) - https://news.ycombinator.com/item?id=7081191 https://news.ycombinator.com/item?id=7081191 - Jan 2014 (17 comments) Ten Years of Purely Functional Data Structures (2008) - https://news.ycombinator.com/item?id=5701396 https://news.ycombinator.com/item?id=5701396 - May 2013 (24 comments) What's new in purely functional data structures since Okasaki? - https://news.ycombinator.com/item?id=1983461 https://news.ycombinator.com/item?id=1983461 - Dec 2010 (2 comments) What's new in purely functional data structures since Okasaki - https://news.ycombinator.com/item?id=1713594 https://news.ycombinator.com/item?id=1713594 - Sept 2010 (1 comment) "Purely Functional Data Structures" by Chris Okasaki [pdf] - https://news.ycombinator.com/item?id=1138979 https://news.ycombinator.com/item?id=1138979 - Feb 2010 (12 comments) Teaching, Playing, and Programming: Ten Years of Purely Functional Data Structures - https://news.ycombinator.com/item?id=112270 https://news.ycombinator.com/item?id=112270 - Feb 2008 (2 comments) Chris Okasaki's PhD thesis on purely functional data structures (pdf) - https://news.ycombinator.com/item?id=8221 https://news.ycombinator.com/item?id=8221 - April 2007 (1 comment)
- odipar 3y agoOkasaki got me interested in confluently persistent data-structures, way back in the 2000s. They seem magical! To be able to combine data from the past with current data, efficiently! They are almost always trees, with the exception of skip-lists, with all operations O(log(n)), . After creating my own programming language Enchilada that is based on immutable data structures, I started considering what I deemed "next level": Uniquely represented confluently persistent data structures 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.
- alex_lav 3y agoI 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. 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.
- mrkeen 3y agoThe bottom line is that pure FP means that the same input to a function gives you the same output. When you debug, you just give the program the same input which was problematic and you get to reproduce the error. Persistent data structures make it less wildly inefficient to do so.
- deleted 3y ago[deleted]
- xupybd 3y agoGah, why did I just buy this as an ebook if it's free.
- sriku 3y agoFor 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.
- pyuser583 3y agoI thought it said “Purely Fictional Data Structures” - which would have been fascinating.
- eigenhombre 3y agoBorges meets Knuth.