29

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.

Rob Lachlan
  • 14,289
  • 5
  • 49
  • 99

1 Answers1

27

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

tosh
  • 5,222
  • 2
  • 28
  • 34
Chouser
  • 5,093
  • 1
  • 32
  • 24
  • 2
    I wish I could be there. Can you be arm twisted into putting your slides on the web later? – Rob Lachlan Oct 20 '10 at 05:31
  • 1
    I believe slides *and* videos will be made available after the conference. – fogus Oct 20 '10 at 13:51
  • @fogus @Rob Indeed, I got confirmation a few days ago that the talks will will be taped. – Rayne Oct 20 '10 at 14:37
  • @Chouser: the video of the talk is no longer available at blip.tv. It can be found [here](http://www.youtube.com/watch?v=UXdr_K0Lwg4). Maybe you'd like to update your answer. – nansen Apr 30 '13 at 12:33