= Data Structures
Rich Hickey
2015-01-01
:type: reference
:toc: macro
:toclevels: 1
:icons: font
:prevpagehref: other_functions
:prevpagetitle: Other Functions
:nextpagehref: datatypes
:nextpagetitle: Datatypes

ifdef::env-github,env-browser[:outfilesuffix: .adoc]

toc::[]

Clojure has a rich set of data structures. They share a set of properties:

* They are immutable
* They are read-able
* They support proper value equality semantics in their implementation of equals
* They provide good hash values
* In addition, the collections:
** Are manipulated via interfaces.
** Support sequencing
** Support persistent manipulation.
** Support metadata
** Implement java.lang.Iterable
** Implement the non-optional (read-only) portion of java.util.Collection or java.util.Map

[[nil]]
== nil

nil is a possible value of any data type in Clojure. nil has the same value as Java null. The Clojure conditional system is based around nil and false, with nil and false representing the values of logical falsity in conditional tests - anything else is logical truth. In addition, nil is used as the end-of-sequence sentinel value in the sequence protocol.

[[Numbers]]
== Numbers

Clojure provides full support for JVM primitive values by default, allowing high performance, idiomatic Clojure code for numeric applications.

Clojure also supports the Java boxed number types derived from java.lang.Number, including BigInteger and BigDecimal, plus its own Ratio type. There is some special handling:

=== Longs

By default Clojure operates with natural numbers as instances of Java's long primitive type. When a primitive integer operation results in a value that is too large to be contained in a primitive value, a java.lang.ArithmeticException is thrown. Clojure provides a set of alternative math operators suffixed with an apostrophe: +', -', *', inc', and dec'. These operators auto-promote to BigInt upon overflow, but are less efficient than the regular math operators.

=== Ratio

Represents a ratio between integers. Division of integers that can't be reduced to an integer yields a ratio, i.e. 22/7 = 22/7, rather than a floating point or truncated value.

=== Contagion

BigInts and floating point types are "contagious" across operations. That is, any integer operation involving a BigInt will result in a BigInt, and any operation involving a double or float will result in a double.

=== BigInt and BigDecimal literals

Numeric literals for BigInt and BigDecimal are specified using a postfix N and M respectively.

[cols="<*", options="header", role="table"]
|===
| Example expression | Return value
| `(== 1 1.0 1M)` | `true`
| `(/ 2 3)` | `2/3`
| `(/ 2.0 3)` | `0.6666666666666666`
| `(map #(Math/abs %) (range -3 3))` | `(3 2 1 0 1 2)`
| `(class 36786883868216818816N)` | `clojure.lang.BigInt`
| `(class 3.14159265358M)` | `java.math.BigDecimal`
|===

=== Related functions

[%hardbreaks]
Computation: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%2B[\+] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%2D[-] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%2A[\*]  https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%2F[/]  https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/inc[inc] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/dec[dec]  https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/quot[quot] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/rem[rem] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/min[min] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/max[max]
Auto-promoting computation: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%2B%27[+'] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%2D%27[-'] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%2A%27[*'] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/inc%27[inc'] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/dec%27[dec']
Comparison: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%3D%3D[==] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%3C[<] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%3C%3D[pass:[<=]] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%3E[>] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/%3E%3D[>=] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/zero%3F[zero?] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/pos%3F[pos?] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/neg%3F[neg?]
Bitwise operations: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bit-and[bit-and] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bit-or[bit-or] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bit-xor[bit-xor] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bit-not[bit-not] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bit-shift-right[bit-shift-right] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bit-shift-left[bit-shift-left]
Ratios: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/numerator[numerator] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/denominator[denominator]
Coercions: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/int[int] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bigdec[bigdec] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/bigint[bigint] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/double[double] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/float[float] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/long[long] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/num[num] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/short[short]

[[Strings]]
== Strings

Clojure strings are Java Strings. See also <<other_functions#printing,Printing>>.
[source,clojure-repl]
----
user=> (map (fn [x] (.toUpperCase x)) (.split "Dasher Dancer Prancer" " "))
("DASHER" "DANCER" "PRANCER")
----

=== Related functions

https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/str[str] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/string?[string?] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/pr-str[pr-str] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/prn-str[prn-str] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/print-str[print-str] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/println-str[println-str] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/with-out-str[with-out-str]

[[Characters]]
== Characters
Clojure characters are Java Characters.

=== Related functions
https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/char[char] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/char-name-string[char-name-string] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/char-escape-string[char-escape-string]

[[Keywords]]
== Keywords
Keywords are symbolic identifiers that evaluate to themselves. They provide very fast equality tests. Like Symbols, they have names and optional <<namespaces#,namespaces>>, both of which are strings. The leading ':' is not part of the namespace or name.

Keywords implement IFn for invoke() of one argument (a map) with an optional second argument (a default value). For example `(:mykey my-hash-map :none)` means the same as `(get my-hash-map :mykey :none)`. See https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/get[get].

=== Related functions
https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/keyword[keyword] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/keyword?[keyword?]
[[Symbols]]

== Symbols
Symbols are identifiers that are normally used to refer to something else. They can be used in program forms to refer to function parameters, let bindings, class names, class members, and global vars. They have names and optional <<namespaces#,namespaces>>, both of which are strings. Symbols can have metadata (see https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/with-meta[with-meta]).

Symbols, just like Keywords, implement IFn for invoke() of one argument (a map) with an optional second argument (a default value). For example `('mysym my-hash-map :none)` means the same as `(get my-hash-map 'mysym :none)`. See https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/get[get].

=== Related functions
https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/symbol[symbol] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/symbol?[symbol?] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/genysm[gensym] (see also the \#-suffix <<reader#,reader>> macro)

[[Collections]]
== Collections

All of the Clojure collections are immutable and https://en.wikipedia.org/wiki/Persistent_data_structure[persistent]. In particular, the Clojure collections support efficient creation of 'modified' versions, by utilizing structural sharing, and make all of their performance bound guarantees for persistent use. The collections are efficient and inherently thread-safe. Collections are represented by abstractions, and there may be one or more concrete realizations. In particular, since 'modification' operations yield new collections, the new collection might not have the same concrete type as the source collection, but will have the same logical (interface) type.

All the collections support https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/count[count] for getting the size of the collection, https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/conj[conj] for 'adding' to the collection, and https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/seq[seq] to get a sequence that can walk the entire collection, though their specific behavior is slightly different for different types of collections.

Because collections support the https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/seq[seq] function, all of the <<sequences#,sequence functions>> can be used with any collection.

[[hash]]
=== Java collection hashes
The Java collection interfaces specify algorithms for https://docs.oracle.com/javase/8/docs/api/java/util/List.html#hashCode()[Lists], https://docs.oracle.com/javase/8/docs/api/java/util/Set.html#hashCode()[Sets], and https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#hashCode()[Maps] in calculating hashCode() values. All Clojure collections conform to these specifications in their hashCode() implementations.

=== Clojure collection hashes
Clojure provides its own hash computations that provide better hash properties for collections (and other types), known as the _hasheq_ value.

The `IHashEq` interface marks collections that provide the `hasheq()` function to obtain the hasheq value. In Clojure, the https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/hash[hash] function can be used to compute the hasheq value.

Ordered collections (vector, list, seq, etc) must use the following algorithm for calculating hasheq (where hash computes hasheq). Note that unchecked-add-int and unchecked-multiply-int are used to get integer overflow calculations.
[source,clojure]
----
(defn hash-ordered [collection]
  (-> (reduce (fn [acc e] (unchecked-add-int
                            (unchecked-multiply-int 31 acc)
                            (hash e)))
              1
              collection)
      (mix-collection-hash (count collection))))
----
Unordered collections (maps, sets) must use the following algorithm for calculating hasheq. A map entry is treated as an ordered collection of key and value. Note that unchecked-add-int is used to get integer overflow calculations.
[source,clojure]
----
(defn hash-unordered [collection]
  (-> (reduce unchecked-add-int 0 (map hash collection))
      (mix-collection-hash (count collection))))
----
The https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/mix-collection-hash[mix-collection-hash] algorithm is an implementation detail subject to change.

[[Lists]]
== Lists (IPersistentList)

Lists are collections. They implement the ISeq interface directly. (Note that the empty list implements ISeq as well, however the `seq` function will always return `nil` for an empty sequence.) https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/count[count] is O(1). https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/conj[conj] puts the item at the front of the list.

=== Related functions

[%hardbreaks]
Create a list: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/list[list] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/list*[list*]
Treat a list like a stack: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/peek[peek] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/pop[pop]
Examine a list: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/list?[list?]

[[Vectors]]
== Vectors (IPersistentVector)

A Vector is a collection of values indexed by contiguous integers. Vectors support access to items by index in log32N hops. https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/count[count] is O(1). https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/conj[conj] puts the item at the end of the vector. Vectors also support https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/rseq[rseq], which returns the items in reverse order. Vectors implement IFn, for invoke() of one argument, which they presume is an index and look up in themselves as if by nth, i.e. vectors are functions of their indices. Vectors are compared first by length, then each element is compared in order.

=== Related functions

[%hardbreaks]
Create a vector: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/vector[vector] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/vec[vec] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/vector-of[vector-of]
Examine a vector: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/get[get] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/nth[nth] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/peek[peek] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/rseq[rseq] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/vector?[vector?]
'change' a vector: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/assoc[assoc] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/pop[pop] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/subvec[subvec] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/replace[replace]

See also <<other_libraries#,zippers>>

[[Maps]]
== Maps (IPersistentMap)

A Map is a collection that maps keys to values. Two different map types are provided - hashed and sorted. Hash maps require keys that correctly support hashCode and equals. Sorted maps require keys that implement Comparable, or an instance of Comparator. Hash maps provide faster access (log32N hops) vs (logN hops), but sorted maps are, well, sorted. https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/count[count] is O(1). https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/conj[conj] expects another (possibly single entry) map as the item, and returns a new map which is the old map plus the entries from the new, which may overwrite entries of the old. https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/conj[conj] also accepts a MapEntry or a vector of two items (key and value). https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/seq[seq] returns a sequence of map entries, which are key/value pairs. Sorted map also supports https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/rseq[rseq], which returns the entries in reverse order. Maps implement IFn, for invoke() of one argument (a key) with an optional second argument (a default value), i.e. maps are functions of their keys. nil keys and values are ok.

=== Related functions

[%hardbreaks]
Create a new map: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/hash-map[hash-map] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/sorted-map[sorted-map] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/sorted-map-by[sorted-map-by]
'change' a map: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/assoc[assoc] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/dissoc[dissoc] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/select-keys[select-keys] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/merge[merge] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/merge-with[merge-with] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/zipmap[zipmap]
Examine a map: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/get[get] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/contains?[contains?] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/find[find] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/keys[keys] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/vals[vals] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/map?[map?]
Examine a map entry: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/key[key] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/val[val]

[[StructMaps]]
== StructMaps

[NOTE]
Most uses of StructMaps would now be better served by <<datatypes#,records>>.

Often many map instances have the same base set of keys, for instance when maps are used as structs or objects would be in other languages. StructMaps support this use case by efficiently sharing the key information, while also providing optional enhanced-performance accessors to those keys. StructMaps are in all ways maps, supporting the same set of functions, are interoperable with all other maps, and are persistently extensible (i.e. struct maps are not limited to their base keys). The only restriction is that you cannot dissociate a struct map from one of its base keys. A struct map will retain its base keys in order.

StructMaps are created by first creating a structure basis object using https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/create-struct[create-struct] or https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/defstruct[defstruct], then creating instances with https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/struct-map[struct-map] or https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/struct[struct].

[source,clojure]
----
(defstruct desilu :fred :ricky)
(def x (map (fn [n]
              (struct-map desilu
                :fred n
                :ricky 2
                :lucy 3
                :ethel 4))
             (range 100000)))
(def fred (accessor desilu :fred))
(reduce (fn [n y] (+ n (:fred y))) 0 x)
 -> 4999950000
(reduce (fn [n y] (+ n (fred y))) 0 x)
 -> 4999950000
----

=== Related functions

[%hardbreaks]
StructMap setup: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/create-struct[create-struct] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/defstruct[defstruct] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/accessor[accessor]
Create individual struct: https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/struct-map[struct-map] https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/struct[struct]

[[ArrayMaps]]
== ArrayMaps

When doing code form manipulation it is often desirable to have a map which maintains key order. An array map is such a map - it is simply implemented as an array of key val key val... As such, it has linear lookup performance, and is only suitable for _very small_ maps. It implements the full map interface. New ArrayMaps can be created with the https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/array-map[array-map] function. Note that an array map will only maintain sort order when un-'modified'. Subsequent assoc-ing will eventually cause it to 'become' a hash-map.

[[Sets]]
== Sets
Sets are collections of unique values.

There is literal support for hash-sets:

[source,clojure]
----
#{:a :b :c :d}
-> #{:d :a :b :c}
----

You can create sets with the https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/hash-set[hash-set] and https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/sorted-set[sorted-set] functions:

[source,clojure]
----
(hash-set :a :b :c :d)
-> #{:d :a :b :c}

(sorted-set :a :b :c :d)
-> #{:a :b :c :d}
----

You can also get a set of the values in a collection using the https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/set[set] function:

[source,clojure]
----
(set [1 2 3 2 1 2 3])
-> #{1 2 3}
----

Sets are collections:
[source,clojure]
----
(def s #{:a :b :c :d})
(conj s :e)
-> #{:d :a :b :e :c}

(count s)
-> 4

(seq s)
-> (:d :a :b :c)

(= (conj s :e) #{:a :b :c :d :e})
-> true
----

Sets support 'removal' with https://clojure.github.io/clojure/clojure.core-api.html#clojure.core/disj[disj], as well as _**contains?**_ and _**get**_, the latter returning the object that is held in the set which compares equal to the key, if found:

[source,clojure]
----
(disj s :d)
-> #{:a :b :c}

(contains? s :b)
-> true

(get s :a)
-> :a
----

Sets are functions of their members, using _**get**_:
[source,clojure]
----
(s :b)
-> :b

(s :k)
-> nil
----

Clojure provides basic set operations like https://clojure.github.io/clojure/clojure.set-api.html#clojure.set/union[union] / https://clojure.github.io/clojure/clojure.set-api.html#clojure.set/difference[difference] / https://clojure.github.io/clojure/clojure.set-api.html#clojure.set/intersection[intersection], as well as some pseudo-relational algebra support for 'relations', which are simply sets of maps - https://clojure.github.io/clojure/clojure.set-api.html#clojure.set/select[select] / https://clojure.github.io/clojure/clojure.set-api.html#clojure.set/index[index] / https://clojure.github.io/clojure/clojure.set-api.html#clojure.set/rename[rename] / https://clojure.github.io/clojure/clojure.set-api.html#clojure.set/join[join].
