[autodidakto]

Possible error:

>If you want to modify a data structure, you have to create an entirely new data structure with the correct changes. This is still pretty fast because Haskell uses lazy evaluation.

I believe the issue is persistent data structures -- the new data structure "remembers" the old one (instead of recreating it) and records changes. (Clojure works like this as well) -- and not lazy evaluation.

[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!