Like Lisp lists, Mythryl lists are implemented as a chain of paired value cells. Consequently, accessing the n-th cell in a list takes O(N) time.
Unlike Lisp lists, Mythryl lists are strongly typed; all the elements of a Mythryl list must be of the same type.
Mythryl lists have properties complementary to those of Mythryl tuples and records:
A complete Mythryl list may be constructed using square brackets. The two primitive list access functions are head which returns the first element in the list and tail which returns the rest of the list:
linux$ my
eval: x = [ "one", "two", "three" ]; # Construct a three-element list.
["one", "two", "three"]
eval: head x; # Access the first element.
"one"
eval: x = tail x; # Get the rest of the list.
["two", "three"]
eval: head x; # Access first element of the rest of the list.
"two"
eval: x = tail x; # Get the rest of second list.
["three"]
eval: head x; # Access first element of third list.
"three"
More commonly Mythryl lists are built up and processed incrementally using the ! constructor, which adds one element to the front of a list:
linux$ my
eval: x = []; # Construct an empty list.
[]
eval: x = "three" ! x; # Prepend the string "three".
["three"]
eval: x = "two" ! x; # Prepend the string "two".
["two", "three"]
eval: x = "one" ! x; # Prepend the string "one".
["one", "two", "three"]
eval: my (foo ! x) = x; # Decompose string into head and tail parts.
eval: foo; # Show head part.
"one"
eval: x; # Show tail part.
["two", "three"]
eval: my (foo ! x) = x; # Again decompose into head and tail parts.
eval: foo; # Show new head part.
"two"
eval: x; # Show new tail part.
["three"]
Prepending a value to an existing list is a constant-time operation (O(1)); a single new cell is created which holds the new value and points to the existing list. Consequently lists can and frequently do share parts:
linux$ my
eval: x = [ "one", "two", "three" ];
["one", "two", "three"]
eval: y = "zero" ! x;
["zero", "one", "two", "three"]
eval: z = "Zero" ! x;
["Zero", "one", "two", "three"]
Here list x is three cells long and lists y and z are each four cells long, but only a total of five cells of storage are used between the three of them.
This sharing can make lists quite economical in aggregate even though an individual list uses twice as much memory per elementary value stored as a tuple or record.
Lists are the standard Mythryl datastructure used to store and process a sequence of same-type values; you should use them whenever you do not have a special reason to do otherwise.
(The most frequent reason not to use a list is when you need constant-time — O(1) — random access to sequence elements; in that case you will usually use a vector. Occasionally you may use a vector just because it consumes half as much memory per elementary value stored as does a list.)
Because lists are used pervasively throughout most Mythryl programs, the Mythryl standard library provides many convenience functions for processing them. Two of the most frequently used are those to compute the length of a list and to reverse a list:
linux$ my
eval: x = [ "one", "two", "three" ];
["one", "two", "three"]
eval: list::length x;
3
eval: reverse x;
["three", "two", "one"]
eval:
Two more are the function apply, which calls a given function once on each element of a list, and map which is similar but constructs a new list containing the results of those calls:
linux$ my
eval: x = [ "one", "two", "three" ];
["one", "two", "three"]
eval: apply print x;
onetwothree
eval: map string::to_upper x;
["ONE", "TWO", "THREE"]
Mythryl programmers habitually avoid the need for many explicit loops by using these two functions to iterate over lists, making their code shorter and simpler.
The infix operator @ is used to concatenate two lists. This involves making a copy of the the first list, and consequently takes time and space proportional to the length of the first list:
linux$ my
eval: [ "one", "two", "three" ] @ [ "four", "five", "six" ];
["one", "two", "three", "four", "five", "six"]
The fold_left and fold_right operators are used to add, multiply, concatenate or otherwise pairwise-combine the contents of a list in order to produce a single result:
linux$ my
eval: x = [ "one", "two", "three" ];
["one", "two", "three"]
eval: fold_forward string::(+) "" x;
"threetwoone"
eval: fold_backward string::(+) "" x;
"onetwothree"
Here the empty strings are the initial value to be combined pairwise with the string elements. The difference between the two functions is the order in which the list elements are processed.
The same functions may be used with integer, floating point or any other kind of value:
linux$ my
eval: x = [ 1, 2, 3, 4 ];
[1, 2, 3, 4]
eval: fold_forward int::(+) 0 x;
10
eval: fold_forward int::(*) 1 x;
24
eval: x = [ 1.0, 2.0, 3.0, 4.0 ];
[1.0, 2.0, 3.0, 4.0]
eval: fold_forward float::(+) 0.0 x;
10.0
eval: fold_forward float::(*) 1.0 x;
24.0
Note that the initial value needs to be zero when summing a list and one when computing the product of a list.
As with apply and map, fold_left and fold_right can save you the effort of writing many explicit loops, making your code shorter and simpler.