Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
123 lines (82 sloc) 2.99 KB

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])


Thanks to heroku for hosting the slides for my Clojure Conj talk about this library. The rather raw sources and enormous PDF of the slides are at github.


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} ())
Jump to Line
Something went wrong with that request. Please try again.