4 ms·
Chris Okasaki's work (cited several times in this thesis) is worth reading if you want to learn more about these kinds of data structures. His thesis is here: h
by amenghra 9y ago
Chris Okasaki's work (cited several times in this thesis) is worth reading if you want to learn more about these kinds of data structures. His thesis is here: https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf and parts of it should be easy to grok by every software engineer. Chris also wrote a book on the same topic.
- candu 9y agoYup. Purely Functional Data Structures (thesis as linked, book: https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) is awesome. I especially found some of the tree-based recursive algorithms eye-opening (once you spend the time to wrap your head around them). IMHO required reading if you're doing any heavy FP work.
- myth_drannon 9y agoAnd there is UChicago course that is following some parts of this book and implements it in Elm language https://www.classes.cs.uchicago.edu/archive/2017/spring/22300-1/ https://www.classes.cs.uchicago.edu/archive/2017/spring/2230...
- tome 9y agoOkasaki's work depends crucially on laziness for turning amortized time bounds into per operation time bounds. Is that the case with the linked work too?
- loopingoptimism 9y agoNo, the linked work describes eager data structures that use techniques such as path-copying for persistence. No laziness required.