Re:Efficient Immutable Collections [pdf]
by amenghra on Monday August 14, 2017 @09:35AM
(#15008443)
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 and parts of it should be easy to grok by every software engineer. Chris also wrote a book on the same topic.
[ Parent
| on HN ]
Yup. Purely Functional Data Structures (thesis as linked, book: 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.
Re:Efficient Immutable Collections [pdf]
by myth_drannon on Monday August 14, 2017 @11:45AM
(#15009490)
And 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/2230...
Okasaki'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?
Re:Efficient Immutable Collections [pdf]
by loopingoptimism on Tuesday August 15, 2017 @05:04AM
(#15016568)
No, the linked work describes eager data structures that use techniques such as path-copying for persistence. No laziness required.