| General Terms (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| A nexus is a tree that contains shared nodes, nodes that have more than one incoming arc. Shared nodes are created in almost every functional program—for instance, when updating a purely functional data structure—though programmers are seldom aware of this. In fact, there are only a few algorithms that exploit sharing of nodes consciously. One example is constructing a tree in sublinear time. In this pearl we discuss an intriguing application of nexuses; we show that they serve admirably as memo structures featuring constant time access to memoized function calls. Along the way we encounter Boolean lattices and binomial trees. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||