Finger trees are a versatile family of fully persistent collections. This library includes everything you need to make your own, as well a few ready-to-use collection types:
-
double-list is a sequential collection that provides constant-time access to both the left and right ends.
-
counted-double-list provides all the features of double-list plus constant-time
countand log-nnth. -
counted-sorted-set is sorted set that also provides log-n
nth
There are examples of all these later in the README.
CLI/deps.edn dependency information:
org.clojure/data.finger-tree {:mvn/version "0.1.0"}If you use leiningen or cake, add this to the :dependencies in your project.clj:
[org.clojure/data.finger-tree "0.1.0"]
If you use maven, add this to the <dependencies> in your pom.xml:
<dependency>
<groupId>org.clojure</groupId>
<artifactId>data.finger-tree</artifactId>
<version>0.1.0</version>
</dependency>
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:
Regardless of how you fetch the dependency, to use a finger-tree
function in your project you'll need to add something like this to
your ns declaration:
(:use [clojure.data.finger-tree :only [double-list]])
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))
dl
;=> (4 5 6 7)
[(first dl) (rest dl)]
;=> [4 (5 6 7)]
(conjl dl 'x)
;=> (x 4 5 6 7)
[(pop dl) (peek dl)]
;=> [(4 5 6) 7]
(conj 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}))
parts
;=> {:left (a b c d e), :right (g h i j k l m)}
(ft-concat (conj (: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 conjl. 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]))
css
;=> (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
(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} ())