Data Structures

Macros Arrays

Once you have a handle on functions and the primitive value types, you may be wondering how to work with collections of things. Janet has a small number of core data structure types that are very versatile. Tables, structs, arrays, tuples, strings, and buffers, are the 6 main built-in data structure types. These data structures can be arranged in a useful table describing their relationship to each other.

Interface	Mutable	Immutable
Indexed	Array	Tuple
Dictionary	Table	Struct
Bytes	Buffer	String (Symbol, Keyword)

Indexed types are linear lists of elements than can be accessed in constant time with an integer index. Indexed types are backed by a single chunk of memory for fast access, and are indexed from 0 as in C. Dictionary types associate keys with values. The difference between dictionaries and indexed types is that dictionaries are not limited to integer keys. They are backed by a hash table and also offer constant time lookup (and insertion for the mutable case). Finally, the 'bytes' abstraction is any type that contains a sequence of bytes. A 'bytes' value or byteseq associates integer keys (the indices) with integer values between 0 and 255 (the byte values). In this way, they behave much like arrays and tuples. However, one cannot put non-integer values into a byteseq.

The table below summarizes the big-O complexity of various operations and other information on the built-in data structures. All primitive operations on data structures will run in constant time regardless of the number of items in the data structure.

Data Structure	Access	Insert/Append	Delete	Space Complexity	Mutable
Array *	O(1)	O(1)	O(1)	O(n)	Yes
Tuple	O(1)	-	-	O(n)	No
Table	O(1)	O(1)	O(1)	O(n)	Yes
Struct	O(1)	-	-	O(n)	No
Buffer	O(1)	O(1)	O(1)	O(n)	Yes
String/Keyword/Symbol	-	-	-	O(n)	No

*: Append and delete for an array correspond to array/push and array/pop. Removing or inserting elements at random indices will run in O(n) time where n is the number of elements in the array.

(def my-tuple (tuple 1 2 3))

(def my-array @(1 2 3))
(def my-array (array 1 2 3))

(def my-struct {
 :key "value"
 :key2 "another"
 1 2
 4 3})

(def another-struct
 (struct :a 1 :b 2))

(def my-table @{
 :a :b
 :c :d
 :A :qwerty})
(def another-table
 (table 1 2 3 4))

(def my-buffer @"thisismutable")
(def my-buffer2 @``This is also mutable``)

To read the values in a data structure, use the get or in functions. The first parameter is the data structure itself, and the second parameter is the key. An optional third parameter can be used to specify a default if the value is not found.

(get @{:a 1} :a) # -> 1
(get {:a 1} :a)  # -> 1
(in  {:a 1} :a)  # -> 1
(get @[:a :b :c] 2) # -> :c
(in  @[:a :b :c] 2) # -> :c
(get (tuple "a" "b" "c") 1) # -> "b"
(get @"hello, world" 1) # -> 101
(get "hello, world" 1)  # -> 101
(in  "hello, world" 1)  # -> 101
(get {:a :b} :a)    # -> :b
(get {:a :b} :c :d) # -> :d
(in  {:a :b} :c :d) # -> :d

The in function (added in v1.5.0) for tables and structs behaves identically to get. However, the in function for arrays, tuples, and string-likes will throw errors on bad keys --- so to better detect errors, prefer in for these.

(get @[:a :b :c] 3) # -> nil
(in  @[:a :b :c] 3) # -> raises error

To update a mutable data structure, use the put function. It takes 3 arguments, the data structure, the key, and the value, and returns the data structure. The allowed types of keys and values depend on the data structure passed in.

(put @[] 100 :a)
(put @{} :key "value")
(put @"" 100 92)

Note that for arrays and buffers, putting an index that is outside the length of the data structure will extend the data structure and fill it with nils in the case of the array, or 0s in the case of the buffer.

Copying

Copying of indexed and dictionary types involves "shallow" copying by default. This means that any references to contained indexed or dictionary types are copied instead of the content being recursively duplicated. This is both for efficiency reasons and because it's not always obvious or well-defined as to how copying should occur.

One way to copy arrays is via the array/slice function.

(def arr @[:a :b])
(def arr1 @[:x arr])
(def arr2 (array/slice arr1))

# change inner array content
(array/push arr :c)

arr # -> @[:a :b :c]

# arr1 and arr2 both "contain" arr
arr1 # -> @[:x @[:a :b :c]]
arr2 # -> @[:x @[:a :b :c]]

Tables may be copied via the table/clone function.

(def arr @[:a :b])
(def tab1 @{:x arr})
(def tab2 (table/clone tab1))

# change array content
(array/push arr :c)

arr # -> @[:a :b :c]

# tab1 and tab2 both "contain" arr
tab1 # -> @{:x @[:a :b :c]}
tab2 # -> @{:x @[:a :c :c]}

For simple cases, recursive or "deep" copies can be made by applying the marshal and unmarshal functions.

(def arr @[:a :b])
(def tab1 @{:x arr})
(def tab2 (unmarshal (marshal tab1)))

# change array content
(array/push arr :c)

arr # -> @[:a :b :c]

# tab1 "contains" arr, tab2 has "replica" of old arr
tab1 # -> @{:x @[:a :b :c]}
tab2 # -> @{:x @[:b :c]}

Macros Arrays