### 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 `r`

_{1}, then to the second-last element and`r`

_{1}, resulting in`r`

_{2}, etc, and finally to the first element and`r`

_{n-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