Finger Tree data structure
Pull request Compare This branch is 27 commits behind clojure:master.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Finger Tree Quickstart

You'll need git and maven, then execute the following at a shell prompt to fetch finger trees and all its dependencies (including a recent snapshot of Clojure itself) and start a REPL:

git clone git:// fingertree
cd fingertree
mvn clojure:repl

Then load up the finger-tree lib and start playing with it:

(use '
(apply double-list '[a b c d e f g h i j k l m n o p q])


Slides for my Clojure Conj talk about this library are available


The finger-tree lib actually includes several collections built on top of Ralf Hinze and Ross Paterson's finger trees. Here are some examples of each of them:


The double-list is a sequential collection that provides constant-time access to both the left and right ends:

(def dl (double-list 4 5 6 7))

;=> (4 5 6 7)

[(first dl) (rest dl)]
;=> [4 (5 6 7)]

(consl dl 'x)
;=> (x 4 5 6 7)

[(pop dl) (peek dl)]
;=> [(4 5 6) 7]

(conjr dl 'x)
;=> (4 5 6 7 x)


This provides all the features of double-list plus constant-time count and log-n nth:

(def cdl
  (apply counted-double-list '[a b c d e f g h i j k l m]))

(nth cdl 5)
;=> f

(assoc cdl 5 'XX)
;=> (a b c d e XX g h i j k l m)

(def parts
  (let [[left _ right] (ft-split-at cdl 5)]
    {:left left, :right right}))

;=> {:left (a b c d e), :right (g h i j k l m)}

(ft-concat (conjr (:left parts) 'XX) (:right parts))
;=> (a b c d e XX g h i j k l m)

(ft-concat (:left parts) (:right parts))
;=> (a b c d e g h i j k l m)
;             ^-- missing f

(ft-concat (into (:left parts) '[X Y Z]) (:right parts))
;=> (a b c d e X Y Z g h i j k l m)


This is like counted-double-list, but does not support consl or conjr. Instead, conj is used to insert items in sorted order.

(def css (apply counted-sorted-set
                '[m j i e d a f k b c f g h l]))
;=> (a b c d e f g h i j k l m)

(get css 'e)      ; O(log(n))
;=> e

(get css 'ee)     ; O(log(n))
;=> nil

(count css)       ; O(1)
;=> 13

(nth css 5)       ; O(log(n))
;=> f

Build-your-own finger tree

(def empty-cost-tree (finger-tree (meter :cost 0 +)))

(def ct (conj empty-cost-tree
              {:id :h, :cost 5} {:id :i, :cost 1}
              {:id :j, :cost 2} {:id :k, :cost 3}
              {:id :l, :cost 4}))

(measured ct)
;=> 15

(next (split-tree ct #(> % 7)))
;=> ({:cost 2, :id :j}
     ({:cost 3, :id :k} {:cost 4, :id :l}))

(next (split-tree (rest ct) #(> % 7)))
;=> ({:cost 4, :id :l} ())