What should I use Clojure's finger trees for?

Question

Clojure's new contrib library group has a finger tree library. What are the use cases for finger trees in clojure? When should finger trees be used instead of one of clojure's other peristent data strucures: vectors, sets, maps, persistentqueues, etc.

The Joy of Clojure mentions that Finger trees can be used for indexed collections where cheap insertions and deletions are required. They have also been described as the "swiss army knife of data structures." Examples of this would be very much appreciated.

Answer 1

2-3 finger trees are described in a paper by Ralf Hinze and Ross Paterson. They provide not only a complete description of the data structure itself, but several examples of how it can be used ...in Haskell. Most of the features they describe are already available in the Clojure library, but the documentation simply isn't there yet.

I'll be introducing Clojure finger trees at Clojure Conj this weekend.

Update: There are now some examples shown at http://github.com/clojure/data.finger-tree#readme

Update: Slides from the talk: https://github.com/Chouser/talk-finger-tree/blob/master/finger-trees.pdf

Update: Video of the talk: http://www.youtube.com/watch?v=UXdr_K0Lwg4