2 ms·
could you expand on persistent data structures? How do they give me 'free' memory with neither allocation nor mutable data? Or is that outside of pure FP?
by m_mueller 10y ago
could you expand on persistent data structures? How do they give me 'free' memory with neither allocation nor mutable data? Or is that outside of pure FP?
- fulafel 10y agoSo persistent data structures are conceptually just an extension of the classic lisp cells: You can have a pointer to (a, b, c) and a pointer to (a, b, c, d) simultaneously, without using twice the memory or time. This can be extended to trees. And you can for example make an efficient tree-backed vector, with chunks of values at the nodes. With some thought you can even get good atomic properties so you can have safe parallel operations on the same persistent vector. Here's a good start about Clojure's persistent vector: http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-...