Predeclared in LISTS

Functions

accumulate(f, initial, xs) → {value}

Applies binary function f to the elements of xs from right-to-left order, first applying f to the last element and the value initial, resulting in r1, then to the second-last element and r1, resulting in r2, etc, and finally to the first element and rn-1, where n is the length of the list. Thus, accumulate(f,zero,list(1,2,3)) results in f(1, f(2, f(3, zero))). Iterative process; time: Theta(n) (apart from f), space: Theta(n) (apart from f), where n is the length of xs.
Parameters:
Name Type Description
f function binary function
initial value initial value
xs list given list
Returns:
result of accumulating xs using f starting with initial
Type
value

append(xs, ys) → {list}

Returns a list that results from appending the list ys to the list xs. Iterative process; time: Theta(n), space: Theta(n), where n is the length of xs. In the result, null at the end of the first argument list is replaced by the second argument, regardless what the second argument consists of.
Parameters:
Name Type Description
xs list given first list
ys list given second list
Returns:
result of appending xs and ys
Type
list

build_list(f, n) → {list}

Makes a list with n elements by applying the unary function f to the numbers 0 to n - 1, assumed to be a nonnegative integer. Iterative process; time: Theta(n) (apart from f), space: Theta(n) (apart from f).
Parameters:
Name Type Description
f function unary function
n number given nonnegative integer
Returns:
resulting list
Type
list

display_list(xs, s) → {value}

Optional second argument. Similar to display, but formats well-formed lists nicely if detected; time, space: Theta(n), where n is the total number of data structures such as pairs in x.
Parameters:
Name Type Description
xs value list structure to be displayed
s string to be displayed, preceding xs
Returns:
xs, the first argument value
Type
value

draw_data() → {value}

visualizes the arguments in a separate drawing area in the Source Academy using box-and-pointer diagrams; time, space: Theta(n), where n is the total number of data structures such as pairs in the arguments.
Parameters:
Name Type Description
value1,value2,...,value_n value given values
Returns:
given x
Type
value

enum_list(start, end) → {list}

Returns a list that enumerates numbers starting from start using a step size of 1, until the number exceeds (>) end. Iterative process; time: Theta(n), space: Theta(n), where n is end - start.
Parameters:
Name Type Description
start number starting number
end number ending number
Returns:
list from start to end
Type
list

equal(x, y) → {boolean}

Returns true if both have the same structure with respect to pair, and identical values at corresponding leave positions (places that are not themselves pairs), and false otherwise. For the "identical", the values need to have the same type, otherwise the result is false. If corresponding leaves are boolean values, these values need to be the same. If both are undefined or both are null, the result is true. Otherwise they are compared with === (using the definition of === in the respective Source language in use). Time, space: Theta(n), where n is the total number of data structures such as pairs in x and y.
Parameters:
Name Type Description
x value given value
y value given value
Returns:
whether x is structurally equal to y
Type
boolean

filter(pred, xs) → {list}

Returns a list that contains only those elements for which the one-argument function pred returns true. Iterative process; time: Theta(n) (apart from pred), space: Theta(n) (apart from pred), where n is the length of xs.
Parameters:
Name Type Description
pred function unary function returning boolean value
xs list given list
Returns:
list with those elements of xs for which pred holds.
Type
list

for_each(f, xs) → {boolean}

Applies unary function f to every element of the list xs. Iterative process; time: Theta(n) (apart from f), space: Theta(1) (apart from f), where n is the length of xs. f is applied element-by-element: for_each(fun, list(1, 2)) results in the calls fun(1) and fun(2).
Parameters:
Name Type Description
f function unary
xs list given list
Returns:
true
Type
boolean
**primitive**; returns head (first component) of given pair p; time: Theta(1)Theta(1).
Parameters:
Name Type Description
p pair given pair
Returns:
head of p
Type
value

is_list(xs) → {xs}

**primitive**; returns true if xs is a list as defined in the textbook, and false otherwise. Iterative process; time: Theta(n), space: Theta(1), where n is the length of the chain of tail operations that can be applied to xs. is_list recurses down the list and checks that it ends with the empty list null
Parameters:
Name Type Description
xs value given candidate
Returns:
whether is a list
Type
xs

is_null(x) → {boolean}

**primitive**; returns true if x is the empty list null, and false otherwise; time: Theta(1)Theta(1).
Parameters:
Name Type Description
x value given value
Returns:
whether x is null
Type
boolean

is_pair(x) → {boolean}

**primitive**; returns true if x is a pair and false otherwise; time: Theta(1)Theta(1).
Parameters:
Name Type Description
x value given value
Returns:
whether x is a pair
Type
boolean

length(xs) → {number}

Returns the length of the list xs. Iterative process; time: Theta(n), space: Theta(1), where n is the length of xs.
Parameters:
Name Type Description
xs list given list
Returns:
length of xs
Type
number

list() → {list}

**primitive**; given n values, returns a list of length n. The elements of the list are the given values in the given order; time: Theta(n)Theta(n).
Parameters:
Name Type Description
value1,value2,...,value_n value given values
Returns:
list containing all values
Type
list

list_ref(xs, n) → {value}

Returns the element of list xs at position n, where the first element has index 0. Iterative process; time: Theta(n), space: Theta(1), where n is the length of xs.
Parameters:
Name Type Description
xs list given list
n number given position
Returns:
item in xs at position n
Type
value

list_to_string(xs) → {string}

Returns a string that represents list xs using the text-based box-and-pointer notation [...]. Iterative process; time: Theta(n) where n is the size of the list, space: Theta(m) where m is the length of the string. The process is iterative, but consumes space O(m) because of the result string.
Parameters:
Name Type Description
xs list given list
Returns:
xs converted to string
Type
string

map(f, xs) → {list}

Returns a list that results from list xs by element-wise application of unary function f. Iterative process; time: Theta(n) (apart from f), space: Theta(n) (apart from f), where n is the length of xs. f is applied element-by-element: map(f, list(1, 2)) results in list(f(1), f(2)).
Parameters:
Name Type Description
f function unary
xs list given list
Returns:
result of mapping
Type
list

member(v, xs) → {list}

Returns first postfix sublist whose head is identical to v (using ===); returns null if the element does not occur in the list. Iterative process; time: Theta(n), space: Theta(1), where n is the length of xs.
Parameters:
Name Type Description
v value given value
xs list given list
Returns:
postfix sublist that starts with v
Type
list

pair(x, y) → {pair}

**primitive**; makes a pair whose head (first component) is x and whose tail (second component) is y; time: Theta(1)Theta(1).
Parameters:
Name Type Description
x value given head
y value given tail
Returns:
pair with x as head and y as tail.
Type
pair

remove(v, xs) → {list}

Returns a list that results from xs by removing the first item from xs that is identical (===) to v. Returns the original list if there is no occurrence. Iterative process; time: Theta(n), space: Theta(n), where n is the length of xs.
Parameters:
Name Type Description
v value given value
xs list given list
Returns:
xs with first occurrence of v removed
Type
list

remove_all(v, xs) → {list}

Returns a list that results from xs by removing all items from xs that are identical (===) to v. Returns the original list if there is no occurrence. Iterative process; time: Theta(n), space: Theta(n), where n is the length of xs.
Parameters:
Name Type Description
v value given value
xs list given list
Returns:
xs with all occurrences of v removed
Type
list

reverse(xs) → {list}

Returns list xs in reverse order. Iterative process; time: Theta(n), space: Theta(n), where n is the length of xs. The process is iterative, but consumes space Theta(n) because of the result list.
Parameters:
Name Type Description
xs list given list
Returns:
xs in reverse
Type
list

tail(p) → {value}

**primitive**; returns tail (second component of given pair p; time: Theta(1)Theta(1).
Parameters:
Name Type Description
p pair given pair
Returns:
tail of p
Type
value