[wyager]

I meant that, despite the fact that adding an element to a tree in Haskell naively constitutes "making a new tree", Haskell usually doesn't end up actually make a whole new tree (because of lazy evaluation), so trees are still really fast.

[chris_j]

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-...

[wyager]

That's fair. I'll fix the article. Thanks!