Data Structures

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
  • 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


nil

nil is a possible value of any data type in Clojure (since primitives are always boxed). 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.

Nums

All Clojure numbers are derived from clojure.lang.Num, which in turn is derived from java.lang.Number. There are 4 types:

  • FixNum

    Represent integer values that fit in 32 bits. When arithmetic involving FixNums exceeds their capacity, they automatically become BigNums.

  • BigNum

    Represent integers of arbitrary precision.

  • DoubleNum

    Correspond to Java's double.

  • RatioNum

    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 value.

Any numeric operation involving DoubleNums yields a DoubleNum.

(+ nums*)

Returns the sum of nums. (+) returns 0.

(- num subs*)

If no subs are supplied, returns the negation of num, else subtracts the subs from num and returns the result.

(* nums*)

Returns the product of nums. (*) returns 1.

(/ numerator denominators*)

If no denominators are supplied, returns 1/numerator, else returns numerator divided by all of the denominators.

(quot numerator denominator)

(rem numerator denominator)

quot[ient] and rem[ainder] of dividing numerator by denominator.

(== nums+)

Returns non-nil if nums all have the same value, otherwise nil.

user=> (== 1 1.0)
true

(< nums+)

Returns non-nil if nums are in monotonically increasing order, otherwise nil.

(<= nums+)

Returns non-nil if nums are in monotonically non-decreasing order, otherwise nil.

(> nums+)

Returns non-nil if nums are in monotonically decreasing order, otherwise nil.

(>= nums+)

Returns non-nil if nums are in monotonically non-increasing order, otherwise nil.

(min nums+)

(max nums+)

Returns the least/greatest of the nums.

(inc num)

Returns a number one greater than num.

(dec num)

Returns a number one less than num.

(zero? num)

Returns true if num is zero, else false

(pos? num)

Returns true if num is greater than zero, else false

(neg? num)

Returns true if num is less than zero, else false

(bit-and x y)

(bit-or x y)

(bit-xor x y)

(bit-not x)

(bit-shift-right x n)

(bit-shift-left x n)

Bitwise operations on integer types (FixNum and BigNum)

Strings

Clojure strings are Java Strings.

Characters

Clojure characters are Java Characters.

Keywords

Keywords are symbolic identifiers that evaluate to themselves. They provide very fast equality tests. Like Symbols, they have names and optional namespaces, both of which are strings. The leading ':' is not part of the namespace or name. Keywords implement IFn, for invoke() of one argument, which they expect to be a map, in which they look themselves up, i.e. keywords are functions of maps.

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 and global vars. They have names and optional namespaces, both of which are strings. Symbols can have metadata.

(gensym prefix?)

Returns a new symbol with a unique name. If a prefix string is supplied, the name is prefix__# where # is some unique number. If prefix is not supplied, the prefix is "G".

Collections

All of the Clojure collections are immutable and 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 these functions:

(count coll)

Returns the number of items in the collection. (count nil) returns 0.

(conj coll item)

Conj[oin]. Returns a new collection with the item 'added'. (conj nil item) returns (item). The 'addition' may happen at different 'places' depending on the concrete type.

(seq coll)

Sequence. Returns a new ISeq on the collection. If the collection is empty, returns nil. (seq nil) returns nil. seq also works on native Java arrays (of reference types) and any objects that implement Iterable.

Lists (IPersistentList)

Lists are collections. They implement the ISeq interface directly. count is O(1). conj puts the item at the front of the list. In addition, lists support the functions:

(list items*)

Creates a new list containing the items.

(list* items* seq)

Creates a new list containing the items prepended to seq.

(peek list)

Same as first. Returns the first item in the list. If the list is empty, returns nil.

(pop list)

Returns a new list without the first item. If the list is empty, throws an exception. Note - not the same as rest.

Vectors (IPersistentVector)

Vectors are collections. They are sequences of values indexed by contiguous integers. Vectors support O(log32N) access to items by index. count is O(1). conj puts the item at the end of the vector. Vectors also support 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. In addition, vectors support the functions:

(vector items*)

Creates a new vector containing the items.

(assoc vector index val)

Assoc[iate]. Returns a new vector that contains val at index. Note - index must be <= (count vector).

(get vector index)

(nth vector index)

Returns the value at the index. get returns nil if index out of bounds, nth throws an exception. nth also works for Java arrays, and, in O(n) time, for sequences.

(peek vector)

Returns the last item in the vector. If the vector is empty, returns nil.

(pop vector)

Returns a new vector without the last item. If the vector is empty, throws an exception.

(rseq vector)

Returns a seq of the items in the vector in reverse order.

(subvec vector start end?)

Returns a persistent vector of the items in vector from start (inclusive) to end (exclusive). If end is not supplied, defaults to (count vector). This operation is O(1) and very fast, as the resulting vector shares structure with the original and no trimming is done.

Maps (IPersistentMap)

Map 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 O(log32N) vs O(logN), but sorted maps are, well, sorted. count is O(1). 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. seq returns a sequence of map entries, which are key/value pairs. Sorted map also supports rseq, which returns the entries in reverse order. Maps implement IFn, for invoke() of one argument, which they presume is a key and look up in themselves, i.e. maps are functions of their keys. nil keys and values are ok.

Map functions:

(hash-map keyvals*)

(sorted-map keyvals*)

(sorted-map-by comparator keyvals*)

keyval => key val

Returns a new hash/sorted map with supplied mappings.

(assoc map key val)

Assoc[iate]. Returns a new map of the same (hashed/sorted) type, that contains the mapping of key to val.

(dissoc map key)

Dissoc[iate]. Returns a new map of the same (hashed/sorted) type, that does not contain a mapping for key.

(get map key)

Returns the value mapped to key, or nil if key not present.

(contains? map key)

Returns true if key is present, else false.

(find map key)

Returns the map entry for key, or nil if key not present.

(select-keys map keys)

Returns a map containing only those entries in map whose key is in keys

(key map-entry)

Returns the key of the map entry.

(val map-entry)

Returns the value in the map entry.

(keys map)

Returns a sequence of the map's keys.

(vals map)

Returns a sequence of the map's values.

(merge maps+)

Returns a map that consists of the rest of the maps conj-ed onto the first. If a key occurs in more than one map, the mapping from the latter (left-to-right) will be the mapping in the result.

(merge-with f maps+)

Returns a map that consists of the rest of the maps conj-ed onto the first. If a key occurs in more than one map, the mapping(s) from the latter (left-to-right) will be combined with the mapping in the result by calling (f val-in-result val-in-latter).

StructMaps

Often many map instances are required to 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 create-struct or defstruct, then creating instances with struct-map or struct.

(create-struct & keys+)

Returns a structure basis object.

(defstruct name & keys+) - macro

Same as (def name (create-struct keys...)).

(struct-map struct-basis keyvals*)

Returns a new structmap instance with the keys of the structure-basis. keyvals may contain all, some or none of the basis keys - where values are not supplied they will default to nil. keyvals can also contain keys not in the basis.

(struct struct-basis vals*)

Returns a new structmap instance with the keys of the structure-basis. vals can be supplied for basis keys in order - where values are not supplied they will default to nil.

(accessor struct-basis key)

Returns a fn that, given an instance of a structmap with the basis, returns the value at the key. The key must be in the basis. The returned function should be (slightly) more efficient than using get, but such use of accessors should be limited to known performance-critical areas.


(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

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. 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.

(array-map keyvals*)

Constructs an array-map.

Copyright © Rich Hickey