WhizzML Reference Manual
4.7 Lists
List values can be expressed as literals using square brackets (as in [1 2 3]) or constructed via procedures such as list and cons, among others (see below). The basic accessors are head and tail, but, as we will see, it is also possible to access list elements by position, count their number, and so on and so forth.
(list? obj) \(\rightarrow \) boolean
Predicate to check whether a given object is a list.
4.7.1 Constructors
(list obj1 …) \(\rightarrow \) list
(list* obj1 …list-or-set-args) \(\rightarrow \) list
(cons obj list) \(\rightarrow \) list
(append list obj) \(\rightarrow \) list
(concat list1 …) \(\rightarrow \) list (flatten list) \(\rightarrow \) list
The first constructor, list, simply constructs a list whose elements are the arguments passed in the call. To prepend obj to list and return the resulting list, use cons, and to append an element to the end of a list, use append. When you have a list listargs and want to prepend to it several values obj1…, you can use list*. concat returns the result of concatenating all its arguments, which must be lists, and flatten. Finally, flatten takes any nested combination of lists and returns their contents as a single list.
(list 1 "hello" true) ;; => [1 "hello" true]
(list* "hello" "hi" ["goodbye"]) ;; => ["hello" "hi" "goodbye"]
(cons 3 [2 1]) ;; => [3 2 1]
(append [1 2] 3) ;; => [1 2 3]
(concat [1 1] [] ["a"] []) ;; => [1 1 "a"]
(flatten [1 [2 3] [[[4]] [5 6]]]) ;; => [1 2 3 4 5 6]
Thus, when xs is a list, we have the equivalences
(list* x0 ... xn xs) => (concat (list x0) ... (list xn) xs)
=> (cons x0 (cons x1 ... (cons xn xs)))
Note that list* also accepts as its last argument a set, in which case the set is first converted to a sequence, with unspecified order, and then the concatenation of the previous elements to the new sequence performed:
(list* 1 2 #[3 "a"]) ;; => [1 2 "a" 3]
(list* #[1 false 3]) ;; => [1 3 false]
(list* #[]) ;; => []
As shown in the examples above, when called with a single set argument, list* becomes WhizzML’s set to list coercion procedure 1 .
It is also possible to create new lists by repeating a single element or function call.
(repeat int obj) \(\rightarrow \) list
(repeatedly int proc) \(\rightarrow \) list
The repeat procedure constructs a new list by copying obj the number of times given by int, while repeatedly calls the procedure proc that number of times and constructs a list with the results of those calls.
Values for n that are less than zero are treated as zero, and will cause these functions to return an empty list.
(repeat 5 1) ;; => [1 1 1 1 1]
(repeat 3 [1 2]) ;; => [[1 2] [1 2] [1 2]]
(repeat "0" x) ;; => []
(repeatedly 5 (lambda () 1)) ;; => [1 1 1 1 1]
(repeatedly 2 rand) ;; => [0.25771884387359023 0.2169657724443823]
Lists of integers can be constructed with range:
(range int [int] [int]) \(\rightarrow \) list
If a single integer argument is given the result is all integers greater than or equal to 0, and less than the argument. If two arguments are given they specify the start (inclusive) and end (exclusive) of the sequence. A third argument may be passed to specify a step size.
(range 10) ;; => [0 1 2 3 4 5 6 7 8 9]
(range -2 4) ;; => [-2 -1 0 1 2 3]
(range 6 20 3) ;; => [6 9 12 15 18]
(range 5 -5 -2) ;; [5 3 1 -1 -3]
4.7.2 Accessors
(head list [obj]) \(\rightarrow \) object
(tail list) \(\rightarrow \) list
(last list [obj]) \(\rightarrow \) object
(butlast list) \(\rightarrow \) list
To access the first element of a list, use head. To get all the elements of a list but its head, ask for its tail. The dual of those operations are last, which returns the last element of a given list, and butlast, which returns a list containing all elements of a given list but the last one. All these standard procedures expect as argument a non-empty list, and will signal error code -20 if passed an empty list and, in the case of head and last, no default value. Both head and last accept an optional argument obj that is returned when list is empty instead of throwing an error.
(head ["a" "b" "c"]) ;; => "a"
(head [] 42) ;; => 42
(tail ["a" "b" "c"]) ;; => ["b" "c"]
(cons (head ["a" "b" "c"]) (tail ["a" "b" "c"])) ;; => ["a" "b" "c"]
(last [1 2]) ;; => 2
(last [] "a") ;; => "a"
(butlast [1 2]) ;; => [1]
(butlast [true]) ;; => []
We have the identities:
(= lst (cons (head lst) (tail lst))) ;; => true for all lists lst
(= lst (append (butlast lst) (last lst))) ;; => true for all lists lst
(nth list int [obj]) \(\rightarrow \) object
Indexed access to the elements of a list is provided by nth, with an optional value to return for out-of-bounds indexes. The index is zero-based: the head of a list is accessed via (nth lst 0). nth raises error code -30 if int is equal or greater than the length of list and no default value (obj) is provided.
As discussed in section 2.5 , explicit calls to nth are rarely needed, because one can directly apply list values to an index to obtain their elements:
(["a" "b" "c"] 0) ;; => "a"
(["a" "b" "c"] 3 "d") ;; => "d"
(let (l [1 2 3])
[(l 2) (l 0) (l 1) (l 12 42)]) ;; => [3 1 2 42]
See also subsection 2.7.1 for a way to access list elements via sequential destructuring in let forms.
(insert list int obj) \(\rightarrow \) list
The insert procedure inserts a given element at its int-th position. Note that lists, as all WhizzML values, are immutable: insert constructs and returns a new list, leaving its arguments untouched.
The insertion index int is zero-based, so that (insert lst 0 x) is the same as (cons x lst) and (insert lst (count lst) x) is equivalent to (append lst x).
If the insertion position is greater than the list length, the element is just appended to the end of the list.
(insert [1 2 3] 1 "a") ;; => [1 "a" 2 3]
(insert [1 2 3] 5 "t") ;; => [1 2 3 5 "t"]
(take int list) \(\rightarrow \) list
(drop int list) \(\rightarrow \) list
These procedures return new lists obtained by either taking or droping the first (if int is positive) or last (if int is negative) int elements of list. Both take and drop accept int larger (in absolute value) than the size of the collection, in which case they return either the entire collection or an empty list.
(take 4 [1 2 3 4 5]) ;; => [1 2 3 4]
(take -2 [1 2 3 4 5]) ;; => [4 5]
(drop 3 [1 2 3 4 5]) ;; => [4 5]
(drop -3 [1 2 3 4 5]) ;; => [1 2]
(take 4 [1 2]) ;; => [1 2]
(drop 20 [1 2]) ;; => []
(drop -3 [1 2]) ;; => []
(take -10 [1 2 3]) ;; => [1 2 3]
We have the trivial equivalences:
n < 0 => (take n l) == (drop (+ (count l) n) l)
n < 0 => (drop n l) == (take (+ (count l) n) l)
4.7.3 Membership
(member? obj list-or-set) \(\rightarrow \) boolean
The standard procedure member? performs a linear search of obj, using structural equality (=), over list-or-set, which can be either a list or a set.
(member? 3 [1 2 8 4 3 2]) ;; => true
(member? {"a" 2} ["foo" {"a" 2}]) ;; => true
(member? "foo" []) ;; => false
(remove-duplicates list) \(\rightarrow \) list
The remove-duplicates standard procedure ensures all elements in the returned list are distinct, preserving order. The first occurence of each unique element is kept.
(remove-duplicates [1 2 1 1 3 2]) ;; => [1 2 3]
(remove-duplicates [1 2 false]) ;; => [1 2 false]
(some proc list) \(\rightarrow \) object
The some procedure takes a procedure of one argument and a list as its arguments. It applies the input function to the list elements in order, returning the result of the application if it is anything other than false. If no element in the list causes the input function to evaluate to something other than false, some returns false.
(some odd? [2 4 6 7 8]) ;; => true
(some (lambda (n) (if (odd? n) n false)) [2 4 6 7 8]) ;; => 7
(some (lambda (n) (if (odd? n) n false)) [2 4 6 8]) ;; => false
4.7.4 Length
(count list) \(\rightarrow \) integer
(empty? list) \(\rightarrow \) boolean
(count {"a" 2 "b" 3}) ;; => 2
(count [18 -23]) ;; => 2
(count "whizzml") ;; => 6
(empty? {}) ;; => true
(empty? "") ;; => true
(empty? []) ;; => true
(empty? [[]]) ;; => false
4.7.5 Extrema finding
(min-key proc list) \(\rightarrow \) object
(max-key proc list) \(\rightarrow \) object
The min-key (max-key) method returns the element x in the input list for which the value of (proc x) is less than (greater than) or equal to the value of (proc y) for any element y in the input list. This can be useful for, e.g., getting the largest value for a key in a list of maps.
(define lst [{"a" 2 "b" 9} {"a" 9 "b" 3}])
(min-key (lambda (x) (get x "a")) lst) ;; => {"a" 2 "b" 9}
(max-key (lambda (x) (get x "b")) lst) ;; => {"a" 2 "b" 9}
4.7.6 Sorting and reordering
(reverse list) \(\rightarrow \) list
This standard procedure returns a new list with the same elements as list, but in reverse order.
(sort list) \(\rightarrow \) list
Lists of numbers, strings, or lists can be sorted by sort, but in general the lists (and the lists of lists) must be homogenous or an exception will be thrown.
(sort [2 3 1]) ;; => [1 2 3]
(sort [[1] [0 0] [0]]) ;; => [[0] [1] [0 0]]
(sort-by-key str-key list-of-maps) \(\rightarrow \) list
Using sort-by-key, one can sort a list of maps by a specfic key in the given maps. Note that primative values and maps not containing the specified key are equivalent under the specified ordering and come before all other values in the returned list.
(sort-by-key "a" [{"a" 2} {"a" 3} {"a" 1}]
;; => [{"a" 1} {"a" 2} {"a" 3}])
(sort-by-key "a" [1 {"a" 3} {"b" 1} {"a" 1}]
;; => [1 {"b" 1} {"a" 1} {"a" 3}])
4.7.7 Folding with reduce and iterate
(reduce proc obj list) \(\rightarrow \) object
The reduce procedure is the familiar left fold for lists, which can be defined in pure WhizzML as:
(define (reduce fn init lst)
(loop (l lst r init)
(if (empty? l) r (recur (tail l) (fn r (head l))))))
So reduce applies its first argument, a function of two arguments, to its second argument and the first element of the list given as third argument. Then it applies the function to the result of that call and the second element of the list, and so on repeteadly until the list is exhausted; i.e., reduce follows the following reduction pattern:
(reduce fn init lst) => (reduce (fn init (head lst)) (tail lst))
Iteration over a list with an accumulator is so frequent that WhizzML provides also a syntactic form, iterate , that makes writing folding expressions over one or more lists easier. Its syntax is as follows:
(iterate (<acc> <init-value> <var0> <list0> <var1> <list1>...)
<body>)
Here, <acc> is a variable name, the accumulator, which takes the initial value <init-value> , and <var1> …are variable names that take, in order, the values of each of the elements of <list0> , <list1> …, which must be all expressions evaluating to lists. These variable names can be used in <body> , and the result of evaluating it for each set of their values is assigned again to <acc> for the next iteration. In other words, the above iterate skeleton is approximately equivalent to the following loop:
(loop (<acc> <init-value>
vs0 <list0>
vs1 <list1>
...)
(if (some empty? vs0 vs1 ...)
<acc>
(let (<var0> (head vs0)
<var1> (head vs1)
...)
(recur (prog <body>) (tail vs0) (tail vs1) ...))))
where vs0, vs1…are local variable names that are not free in <body> . So, for instance:
(iterate (a 0 x (range 4) y [1 8 9 3]) (+ a x y))
is equivalent to the loop:
(loop (a 0
xs (range 4)
ys [1 8 9 3])
(if (empty? xs)
a
(let (x (head xs)
y (head ys))
(recur (+ a x y) (tail xs) (tail ys)))))
We can also rewrite a single-list iterate as a reduce call:
(reduce (lambda (<acc> <var0>)
<body>)
<init-value>
<list0>)
So, for single lists, iterate lets you write your reductions in a more compact form, specially when <<> body> is not trivial. But iterate is more powerful than reduce in that it can traverse (in parallel) more than one list, and also allows early exits of the iteration with break.
Indeed, the reason why the above loop or reduce forms are not exactly equivalent to the corresponding iterate form is that in the body of iterate you can use the reserved form break to exit early from the iteration; break takes a single argument which will be the value of the full iterate expression. For instance:
(iterate (a 0 x [1 20 -1]) (+ a x)) ;; => 20
(iterate (a 0 x [1 20 -1])
(if (negative? x)
(break 0)
(+ a x))) ;; => 0
4.7.8 Filtering
(filter proc list) \(\rightarrow \) list
The filter procedure returns a filtered version of the input list, where the filtered version includes only items x for which (proc x) does not evaluate to false.
(filter (lambda (x) (> x 5)) [10 5 4 3 10 7]) ;; => [10 10 7]
(filter (lambda (x) (> x 10)) [10 5 4 3 10 7]) ;; => []
4.7.9 Other list traversal procedures
(every? proc list) \(\rightarrow \) bool
The every? standard predicate traverses the given list, applying to every element the predicate proc, and returning true is all applications evaluate to a non-false value:
(every? odd? [1 3 5 7]) ;; => true
(every? odd? []) ;; => true
(every? odd? [1 2 3 4 5]) ;; => false