If it's worth saying, but not worth its own post, then it goes here.
Notes for future OT posters:
1. Please add the 'open_thread' tag.
2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)
3. Open Threads should start on Monday, and end on Sunday.
4. Unflag the two options "Notify me of new top level comments on this article" and "
I expect it is -- I haven't looked. But AIUI the usual way of making this sort of structure persistent amounts to remembering a log of everything you did, so the requirement for more rotations means that a persistent AVL tree ends up less space-efficient than a persistent red-black tree. Something like that, anyway, I haven't attempted to build either.
In Haskell, or any GC language really, you don't need a log to make a tree data structure persistent. Just always allocate new nodes instead of changing old ones, so all operations will return a new version of the whole tree. That's O(log n) allocations per operation, because most subtrees can be shared between the old and new versions, only the nodes along one path down the tree need to be new. Anyone who kept a reference to an old version's root can keep accessing the entire old version, because nodes never change. And if nobody kept a reference, GC picks it up. That way it's also easy to have branching history, which seems impossible with a log.