Persistent Red Black Tree in Lisp (4)

Okasaki’s purely functional red black tree

The peristent red black tree in last post works ok, but the rotate functions and color flip is not efficient for purely functional data sturctures. In 1999, Okasaki introduced a new way to balance the insertion, and the function only takes care of four unbalanced cases.

Chris Okasaki,
"Red-Black Trees in a Functional Setting",
Journal of Functional Programming, 9(4),
pp471-477,
July 1999


The algorithm is easy to present in Haskell code:

Cool! This can be even reduced to only two cases in our mtree-expand and mtree-let macro!

To test the running time:

Conclusions

Lisp is designed for bottom-up programming. You first draft what you want to do, then you can start to write some functions and macros to simplify it. When there are more and more utilities you written, you can use it to experiment more complicated algorithms, in a more elegant and self expressive style.

In purely functional structure, Haskell code seems to be more elegant because it has built in pattern matching, while we have to write one for Lisp. But Lisp provides things more than functional programming, it can also be written in procedure style, object-oriented style, or any other DSL that is best suitable for your objective.

The macro system in lisp can also improve your thinking of designing a program. Because you can always abstract your program structure as you writing it. In other language you are trained to think top-down, while in lisp you are encouraged to think back and forth. This process can shorten required time to get enough experiences of programming. You don’t need a lot experiences to build a complex algorithm in a bottom-up design process. It’s just come up naturally.