Finger Trees Custom Persistent Collections - Chris Houser
Why Stack Overflow recommends it
Stack Overflow users link it as the main explanation of finger trees, both for what Clojure's implementation offers and for how persistent deque-like structures work.
Recommended by 2 people across 2 different months, 2010 to 2013.
What it is
Chris Houser, the implementor of Clojure's finger tree library, presents at Clojure Conj on how finger trees fill gaps in Clojure's persistent collections. He covers sorted sets with efficient nth, sequences that grow at either end or in the middle, customizing trees for application needs, and some internals.
What people said
Recommends Chouser · 2010-10 · Stack Overflow · on “What should I use Clojure's finger trees for?”
2-3 finger trees are described in a paper by Ralf Hinze and Ross Paterson [LINK] . 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 [LINK] this weekend. Update: There are now some examples shown at [LINK] Update: Slides from the talk: [LINK] Update: Video of the talk: [this video]
Recommends avh4 · 2013-09 · Stack Overflow · on “Why no immutable double linked list in Scala collections?”
As others have noted, there is no persistent implementation of a double-linked list. You will need some kind of tree to get close to the characteristics you want. In particular, you may want to look at finger trees [LINK] , which provide O(1) access to the front and back, amortized O(1) insertion to the front and back, and O(log n) insertion elsewhere. (That's in contrast to most other commonly-used trees which have O(log n) access and insertion everywhere.) See also: video explanation of finger trees [this video] (by the implementor of finger trees in clojure.contrib) finger tree implementation in Scala [LINK] (I haven't used it personally, but it's the top google hit)
Cites nansen · 2013-04 · Stack Overflow · on “What should I use Clojure's finger trees for?”
@Chouser: the video of the talk is no longer available at blip.tv. It can be found here [this video] . Maybe you'd like to update your answer.