|
Ralf Hinze. Functional Pearl: A fresh look at binary search trees.
Insertion into a BST is a simple, succinct, operation. Deletion is much harder. Why?
Our own stab at explaining this phenomenon is algebraic or, if you like, linguistic. Arguably, the data type Tree with its two constructors, Leaf and Node, does not constitute a particularly elegant algebra.
Nice example of the algebraic-stance, as well as of the power of abstraction.
The paper also has a simple example of views, that readers may find useful.
Posted to functional by Ehud Lamm on 9/10/03; 5:56:08 AM
|
Functional Pearl: A fresh look at binary search trees
