Clojure’s Persistent Data Structures

Clojure’s Persistent Data Strcutures

Presented at Maryland Data Science

February 12^th, 2014

Slides

Me

Craig Andera

@craigandera

craig@cognitect.com

http://cognitect.com/podcast

Clojure

• A Lisp
• Hosted
• Functional
• Rich Literal Data Types

Clojure Data Types

• The usual suspects

3
1.7
"hi there"

Clojure Data Types

• A few fancier ones

11/2                 ; ratios
:foo                 ; keywords
foo                  ; symbols
#"fo+"               ; regular expressions
#duration "00:30:12" ; BYODT!

Collections

[1 :two "three" 4.0]           ; Vectors
("one" 2 :three [4])           ; Lists
{:one 1 :two 2 :three (1 2 3)} ; Maps
#{:one "two" 9/3}              ; Sets

Evaluation

• Clojure distinguishes between read time and eval time
• Everything except symbols and lists eval as themselves
• Symbols eval to whatever they refer to
• Lists apply the first item to the remainder

Evaluation

(def foo 3)

foo                  ; => 3
(+ 1 2.0)            ; => 3.0
(+ 2.0 (* foo 17/3)) ; => 19.0

Collections are Immutable

• Simple values (numbers, strings) are immutable
• In Clojure, compound values are immutable too
• Key to Clojure’s concurrency model
• You cannot change an immutable value
• Generate new ones instead

Collections are Immutable

(def x [1 2 3])
(def y (conj x 4))

y     ; => [1 2 3 4]
x     ; => [1 2 3]

Collections are Persistent

• New values built from old values + modifications
• New values are not full copies
• New value and old value are both available after ‘changes’
• Maintains performance guarantees for most operations
• All Clojure data structures are persistent

Example: Linked List

• Linked lists are trivially persistent for append at head

(def xs '(2 3 4))
(def ys (conj xs 1))
xs ;=> (2 3 4)
ys ;=> (1 2 3 4)

Example: Linked List

file:collections-linked-list-1.svg

Example: Linked List

file:collections-linked-list-2.svg

Example: Binary Tree

file:collections-tree-1.svg

Example: Binary Tree

file:collections-tree-2.svg

Example: Shared Structure

file:collections-structural-sharing.svg

Advantages

• Don’t have to worry about concurrent modification
• Makes time explicit
• Clojure still offers in-place mutation
  • But it is explicit, rare, and controlled

What About Performance?

• Shared structure means reasonable memory characteristics
• High branching means quick access
  • O(log_32 N) is essentially O(1)
• Other options for the rare times perf insufficient

file:hash-trie.png

Datomic

• Database is immutable and persistent
• Makes the database a value
• Can view the database as it was
  • At any point in its history

file:index-tree-append.png

Colophon

• Typography
  • Carrois Gothic

Questions?

Thanks!

Extras

Data Structures are Functions

• Maps are functions of their keys
• Keywords are functions of maps
• Sets are functions of their elements
• Vectors are functions of their indices

Maps & Keywords are Functions

(def m {:a 1 :b 2})

;; Maps are functions of their keys
(m :b)       ;;=> 2
(m :foo)     ;;=> nil
(m :foo 50)  ;;=> 50    ; default

;; Keywords are functions of maps
(:a m)    ;;=> 1

Sets are Functions

(def s #{3 7 9})

;; Returns the element if it's in the set:
(s 7)   ;;=> 7

;; Returns nil otherwise:
(s 20)  ;;=> nil

Vectors are Functions

(def v [:a :b :c])

(v 2)   ;;=> :c

(v 10)  ;> ERROR

Pictures

(source)

Footer