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
head(p) → {value}
**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