Which tree-based dictionary is the easiest to implement functionally?

Question

I'm looking for a tree-based dictionary data structure which is easy to implement in Haskell.

Do you have any experience with implementing AVL trees or RB trees? I'm also thinking about splay trees, but don't see how they could be implemented using immutable data.

Answer 1

Red-black trees are very easy to implement in a functional language, since you don't need to spend effort trying to shave off a few assignments, and the usual description of algorithms corresponds very well to pattern matching. See Okasaki, Red-Black Trees in a Functional Setting. In fact, his book, which is the revised and extended version of his thesis, is an excellent reference for many purely functional data structures.