Which tree dictionary is the easiest to implement functionally?

Question

I am looking for a tree-like dictionary data structure that is easy to implement in Haskell.

Do you have experience implementing AVL trees or RB trees? I also think about splay trees, but I don’t see how they can be implemented using immutable data.

Answer 1

Red-black trees are very easy to implement in a functional language, since you do not need to spend effort trying to shave off a few tasks, and the usual description of the algorithms matches the pattern matching well. See Okasaki, Red-Black Trees in Functional Customization . In fact, his book , which is a revised and extended version of his thesis , is a great reference for many purely functional data structures.