Purely Functional Data Structures
Description: Purely Functional Data Structures by Chris Okasaki presents data structures and design methods specifically suited for functional programming languages. It focuses on implementing efficient, immutable data structures
ISBN: 0521663504
Found in 3 comments on Hacker News
View on Amazon
We may earn a commission from purchases made through links on this page.
Not ready yet? Get weekly book picks.
twaybtclong
· 2021-02-15
·
Original thread
bcherny
· 2020-01-01
·
Original thread
A great resource for understanding how persistent data structures are implemented is Okasaki’s Purely Functional Data Structures: https://www.amazon.com/Purely-Functional-Data-Structures-Oka...
Also available as a free PDF: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
Get the best books from Hacker News each week
Join 4,500+ subscribers and get the best books mentioned on Hacker News every Thursday.
For example, if you have a vector of 100 items, and you "mutate" that by adding an item (actually creating a new vector), the language doesn't allocate a new 101-length vector. Instead, we can take advantage of the assumption of immutability to "share structure" between both vectors, and just allocate a new vector with two items (the new item, and a link to the old vector.) The same kind of idea can be used to share structure in associative data structures like hash-maps.
I'm no expert on this, so my explanation is pretty anemic and probably somewhat wrong. If you're curious, the book "Purely Functional Data Structures" [0] covers these concepts in concrete detail.
[0]: https://www.amazon.com/Purely-Functional-Data-Structures-Oka...