Module /fusion/list
Operations for lists (a.k.a. arrays).
A list is a sequence, an ordered collection of values, with zero-based
integer keys and constant-time lookup of elements. Lists come in three
concrete types: immutable, mutable, or stretchy; a stretchy list IS-A mutable
list. Non-stretchy lists are comparable to Java arrays, while stretchy lists
are comparable to ArrayLists; however, Fusion doesn't guarantee that the
elements of a list are contiguous in memory.
Creating Lists
In standard Fusion, Ion list syntax denotes immutable values:
[] denotes an immutable list of size zero, and [{f:x}] denotes an
immutable list of size 1 holding a struct of size 1. The value of a list
literal is immutable even when some child values are evaluated at run-time.
Quoted forms are also immutable; in (quote [x]) the list's sole element is
the symbol 'x'.
The procedure list has the same effect as a list literal. The
procedure mutable_list creates mutable lists, and stretchy_list creates
stretchy lists:
$ [1, 2]
[1, 2]
$ (mutable_list 1 2)
[1, 2]
$ (stretchy_list 1 2 3)
[1, 2, 3]
Note that the REPL uses a default "ionization strategy" that renders all list types the same, so the results look similar even though the values have different types. Eventually the application will be able to control this strategy; these defaults are designed to allow a Fusion developer to construct data in various combinations of mutability (etc.) and output it as "normal" Ion data.
Using Lists
The procedure list_element returns an element from inside the list. It is a
type-specific (and thus slightly faster) version of the more-generic element
procedure.
$ (list_element ["oompa", "loompa"] 1)
"loompa"
The procedure list_set replaces an element in a mutable (including
stretchy) list:
$ (define immutable [1])
$ (list_set immutable 0 "new value")
// list_set expects mutable list as 1st argument, given [1]
Other arguments were:
0
"new value"
$ (define mutable (mutable_list 1))
$ mutable
[1]
$ (list_set mutable 0 "new value")
$ mutable
["new value"]
$ (list_element mutable 0)
"new value"
The procedure add, when given any type of list, returns a list of the
same type, with a value added to the end. It does not mutate the input list,
and the result doesn't share any structure other than the contained elements.
$ (add mutable "newer")
["new value", "newer"]
$ mutable
["new value"]
$ (define stretchy (stretchy_list true (quote blue)))
$ stretchy
[true, blue]
$ (add stretchy "magoo")
[true, blue, "magoo"]
$ stretchy
[true, blue]
The procedure add_m is a mutating procedure that, like add,
returns a list of the same type with a value added to the end. However, when
possible it achieves this through mutation and/or structure sharing. This means
that when given a stretchy list, it will mutate that list and then return
it.
$ (add_m mutable {})
["new value", {}]
$ mutable
["new value"]
$ (add_m stretchy {})
[true, blue, {}]
$ stretchy
[true, blue, {}]
The semantics of add and add_m are described a bit oddly here because they
are polymorphic operations applicable to other Fusion container types. The
'_m' suffix is Fusion's spelling of the traditional '!' suffix in Scheme
languages, highlighting potential mutation of an argument.
Traversing Lists
Lists support the many traversal operators defined over sequences
and collections, such as map, choose, find, and
fold_left, and generally you should use those when applicable.
To directly traverse a list, you can write a loop that increments a position
variable. For example, here's a (list-only) version of choose:
(define (choose pred lst)
(let loop [(i 0),
(result (stretchy_list))]
(if (= i (size lst))
result
(let [(e (element lst i))]
(loop
(+ 1 i)
(if (pred e)
(add_m result e)
result))))))
This loop uses two variables: i is the current position in the list, and
result contains the chosen elements. When the loop is called, it receives
the incremented position, along with either the extended result (if the
current element e satisfies the predicate) or the earlier result as-is.
Bonus tip: the code above would still work if the use of a strechy_list
was replaced with a normal immutable list. In that case, add_m would
return a new immutable list, which would then be passed as the new result.
Other alternative traversal forms include iterators and comprehensions.
(. value key ...)
Traverses a "path" through a data structure, folding the value through each
key in turn. When the value is void, it is returned immediately and any
further keys are not applied. If a key is a procedure, it must accept one
argument; the procedure is applied to the current value, and the result becomes
the value for the next key. Otherwise, the key and value are passed to elt
to get the next value.
(. [0, 1] 0) => 0
(. (sexp 0 1) 1) => 1
(. {f:2} "f") => 2
(. {f:3} (quote f)) => 3
(. [0, 1, 2, 3] size) => 4
(. (sexp 0 1 2 3) head) => 0
(. (sexp 0 1 2 3) tail) => (1 2 3)
(. (sexp 0 1 2 3) tail tail head) => 2
Since . is a procedure, field names must be quoted or else they will
be evaluated as a variable reference:
(. {f:2} f) => ERROR: Unbound variable reference
(let [(g "f")]
(. {f:2} g)) => 2
(add sequence element)
Returns a sequence with all the elements of sequence and the element. The
result sequence is similar to the input, its size is one greater, and it may
share structure with other sequences.
In general, the position of element within the result is not specified, but
particular sequence types may do so.
- For lists, the
elementbecomes the last element of the result. - For sexps, the
elementbecomes the head of the result.
(add_m list element)
Returns a sequence with all the elements of list and the element. The
result sequence is similar to the input, its size is one greater, and it may
share structure with other sequences. The input sequence may be mutated.
In general, the position of element within the result is not specified, but
particular sequence types may do so.
- For stretchy lists, the
elementis added to the end of the input sequence, which is then returned.
(any pred collection)
Applies the one-argument predicate pred to the elements of collection;
the first time pred returns a truthy value that truthy value is returned and
no more elements are visited. If no call returns a truthy value, then the
result is that of the final predicate call, or false if the collection is
empty.
When collection is a sequence, the elements are visited in order, and the
application of pred to the final element of the sequence is in tail position.
(append sequence ...+)
Returns a sequence with the concatenation of all the elements of the sequences.
The result has same type and annotations as the first sequence.
Any argument that is null.list (or null.sexp) is treated as if it were an
empty list (or empty sexp).
(append_m sequence ...+)
Returns a sequence with the concatenation of all the elements of the sequences,
mutating the first argument when possible.
The result has same type and annotations as the first sequence.
Any argument that is null.list (or null.sexp) is treated as if it were an
empty list (or empty sexp).
(choose pred sequence)
Applies the one-argument predicate pred to each element of sequence,
returning a new sequence of the same type, containing the elements (in order)
for which pred returns truthy.
(do proc collection)
Applies the one-argument procedure proc to the elements of collection,
ignoring any results. Returns void.
When collection is a sequence, the elements are visited in order.
See also: struct_do
(element collection key)
Returns an element within a collection. The collection must be a non-null,
non-empty list, sexp, or struct. The key must have a type appropriate for
the collection: an int for lists or sexps, a string or symbol for structs.
(element [0, 1] 0) => 0
(element (sexp 0 1) 1) => 1
(element {f:2} "f") => 2
(element {f:3} (quote f)) => 3
Since element is a procedure, field names must be quoted or else they will
be evaluated as a variable reference:
(element {f:2} f) => ERROR: Unbound variable reference
(let [(g "f")]
(element {f:2} g)) => 2
An exception is raised if the collection has an unsupported type, if the
key isn't appropriate for the collection, or if the key doesn't identify
an element within the collection.
(element [0, 1] 2) => ERROR
(element [0, 1] "2") => ERROR
(element {f:2} "g") => ERROR
(elt collection key)
Returns an element within a collection, being lenient. The collection must
be a list, sexp, struct, or void. The key must have a type appropriate for
the collection: an int for lists or sexps, a string or symbol for structs.
(elt [0, 1] 0) => 0
(elt (sexp 0 1) 1) => 1
(elt {f:2} "f") => 2
(elt {f:3} (quote f)) => 3
If the collection is empty, null, or void, the result is void. If the key
isn't appropriate for the collection, or if the key doesn't identify an
element within the collection, the result is void.
(elt null.list 0) => void
(elt [0, 1] 2) => void
(elt [0, 1] "2") => void
(elt {f:2} "g") => void
Since elt is a procedure, field names must be quoted or else they will
be evaluated as a variable reference:
(elt {f:2} f) => ERROR: Unbound variable reference
(let [(g "f")]
(elt {f:2} g)) => 2
An exception is raised if the collection has an unsupported type.
(every pred collection)
Applies the one-argument predicate pred to the elements of collection;
the first time pred returns an untruthy value that untruthy value is returned
and no more elements are visited. If no call returns an untruthy value, then the
result is that of the final predicate call, or true if the collection is empty.
When collection is a sequence, the elements are visited in order, and the
application of pred to the final element of the sequence is in tail position.
(find pred collection)
Applies the one-argument predicate pred to each element of collection;
the first time pred returns a truthy value that element is returned.
If no such element is found, the result is void.
When collection is a sequence, the elements are visited in order.
When collection is a struct, the "elements" of the collection are its
values (as opposed to its key-value pairs): the predicate will be applied on
each value, and the result is either one of those values or void.
(first sequence)
Returns the first element in the sequence. Fails if the sequence has no
elements.
(fold_left proc init sequence ...)
Applies the given procedure to zero or more sequences producing a single value
determined by proc. proc must take n+1 arguments where n is the number of
sequences. The proc's first argument is the combined return value and is
initially set to init. Sequences are visited left to right with the result of
fold_left being the value produced by the last application of proc after
one or more sequences runs out of values. If no sequences are given or any
sequence is empty, the result is init.
Adding numbers:
(fold_left + 0 (sexp 1 2 3) [4, 5, 6, 7]) => 21
That performs these procedure calls:
(+ 0 1 4) => 5
(+ 5 2 5) => 12
(+ 12 3 6) => 21
Reversing a linked list:
(fold_left
(lambda (t h) (pair h t))
(quote ())
(sexp 1 2 3 4 5)) => (sexp 5 4 3 2 1)
Vizualizing fold_left:
(fold_left f z (1 2 3 4 5))
. --------------------> f
/ \ / \
1 . f 5
/ \ / \
2 . f 4
/ \ / \
3 . f 3
/ \ / \
4 . f 2
/ \ / \
5 () z 1
(fold_left f z (1 2 3 4 5) (6 7 8 9 0))
. --------------------> f
/|\ /|\
1 6 . f 5 0
/|\ /|\
2 7 . f 4 9
/|\ /|\
3 8 . f 3 8
/|\ /|\
4 9 . f 2 7
/|\ /|\
5 0 () z 1 6
(has_key collection key)
Determines whether a collection has a mapping for a given key.
When has_key returns true, then (element collection key) will succeed.
Note that the keys of a sequence are the zero-based integer indices of the elements within the sequence, not the elements themselves.
(has_key {f:12} "f") ==> true
(has_key [3,true,2014T] 0) ==> true
(has_key [3,true,2014T] 3) ==> false
(has_key [3,true,2014T] null) ==> false
(is_collection value)
Determines whether value is a collection (struct, list, or sexp), returning
true or false.
(is_empty collection)
Returns true if the size of the collection is zero, otherwise returns
false.
(is_immutable_list value)
Determines whether value is an immutable list, returning true or false.
(is_list value)
Determines whether value is a list, returning true or false.
(is_mutable_list value)
Determines whether value is a mutable list, returning true or false.
(is_sequence value)
Determines whether value is a sequence, returning true or false.
(is_stretchy_list value)
Determines whether value is a stretchy list, returning true or false.
(last sequence)
Returns the last element in the sequence. Fails if the sequence has no
elements.
(list value ...)
Makes a fresh, immutable list containing the given values.
(list_element list pos)
Returns the element of list at (zero-based) position pos. An exception is
thrown if the position is out of bounds.
(list_from_iterator iterator)
Creates a stretchy list with the elements of iterator, in the same order.
At present, this procedure will fail if the iterator returns multiple results.
(list_iterator list)
Returns an iterator over the elements of list.
(list_set list pos value)
Changes the slot of a mutable list at (zero-based) position pos so it
holds value. An exception is thrown if the position is out of bounds.
(map proc sequence)
Applies the one-argument procedure proc to each element of sequence,
returning a new sequence of the same type, containing the results in order.
(mutable_list value ...)
Makes a fresh, mutable list containing the given values.
(none pred collection)
Applies the one-argument predicate 'pred' to the elements of collection. Returns false if the predicate returns a truthy value for any element, true if none do, and true if the collection is empty.
(size collection)
Returns the number of elements in the collection.
The size of null.list (etc.) is zero. If collection is an improper sexp,
an exception is thrown.
Warning: Computing the size of an sexp takes linear time, since it must traverse the linked list of pairs to count elements.
(stretchy_list value ...)
Makes a fresh, stretchy list containing the given values.
(subseq seq from to)
Returns a sequence holding the elements of the non-null sequence seq between
positions from and to. The following precondition applies:
0 <= from <= to <= (size seq)
The result may share structure with seq and has the same type as seq.