| Under consideration for publication in J. Functional Programming 1 FUNCT I ONAL PEARL (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Introduction Binary search trees are old hat, aren't they? Search trees are routinely covered in introductory computer science classes and they are widely used in functional programming courses to illustrate the bene ts of algebraic data types and pattern matching. And indeed, the operation of insertion enjoys a succinct and elegant functional formulation. Fig. 1 contains the six-liner given in the language Haskell 98. Alas, both succinctness and elegance are lost when it comes to implementing the dual operation of deletion, also shown in Fig. 1. Two additional helper functions are required causing the code size to double in comparison with insertion. Why this discrepancy? The algorithmic explanation is that insertion always takes place at an external node, that is, at a leaf whereas deletion always takes place at an internal node and that manipulating internal nodes is notoriously more dicult than manipulating external nodes. Our own stab at explaining this phenomenon is algebraic | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||