Functional Pearl Trouble Shared is Trouble Halved
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 algorith...
| Hauptverfasser: | , |
|---|---|
| Format: | Journal article |
| Sprache: | English |
| Veröffentlicht: |
2003
|
| Zusammenfassung: | 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. |
|---|