I'm happy to see finger trees got mentioned. Finger trees[0] are extremely useful and general data structure that can be used to implement persistent sequences, priority queues, search trees and priority search queues. (Haskell's Data.Sequence[1] uses specialized 2-3 finger trees internally) They can form the basis of all sorts of interesting custom structures by supplying the appropriate monoid[3], but this does make them harder to approach if you are not familiar with the abstractions.<p>[3] A monoid is any structure that has members that can combine associatively. In addition, it must have an element that can combine with any other element and result in the other element. Some examples: (strings, string concatenation, the empty string); (integers, addition, 0); (natural numbers, max, 0); (booleans, and, True); (functions, composition, the identity function). The functional pearl[2] that describes the design of Haskell's diagrams library[4] goes into much more detail if you are interested in their application to programming.<p>[0] <a href="http://apfelmus.nfshost.com/articles/monoid-fingertree.html" rel="nofollow">http://apfelmus.nfshost.com/articles/monoid-fingertree.html</a><p>[1] <a href="http://hackage.haskell.org/package/containers-0.5.4.0/docs/Data-Sequence.html" rel="nofollow">http://hackage.haskell.org/package/containers-0.5.4.0/docs/D...</a><p>[2] <a href="http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf" rel="nofollow">http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf</a><p>[4] <a href="http://projects.haskell.org/diagrams/" rel="nofollow">http://projects.haskell.org/diagrams/</a>