|
|
|
|
|
|
by chris_j
4378 days ago
|
|
|
That's still not quite right. It's not lazy evaluation that makes it feasible to "make a new tree" in Haskell (although it doesn't hurt), it's the fact that the new tree shares most of the state of the old tree and the data structures make the asymptotic time complexity of both update and retrieval very close to (but not quite) O(n). If you haven't looked at persistent data structures yet then I'd definitely recommend doing so because they are fascinating. A few people have written about Clojure's data structures and the following article looks like it gives a good introduction: http://hypirion.com/musings/understanding-persistent-vector-... |
|
|