Functional Pearl Trouble Shared is Trouble Halved

Journal article

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 ...

Expand abstract

Authors: Bird, R; Hinze, R

• Journal: Proceedings of the 2003 ACM SIGPLAN Haskell Workshop
• Pages: 1-6
• Publication date: 2003-01-01
• Language: English
• Keywords: Binomial trees; Sharing; Boolean lattices; Memoization; Haskell; Purely functional data structures