#### 3.7` `lists

##### 3.7.1` `The List Datatype

A List is an immutable, fixed-length collection indexed by non-negative integers.

As in most programming languages, you can use Lists in Pyret without understanding much, if anything, about how they are implemented internally in the language.

However, in functional languages such as Pyret a particular implementation of lists – the linked list – has a central role for both historical and practical reasons, and a fuller understanding of linked lists goes hand in hand with a fuller understanding of Pyret. If you have not encountered linked lists before and would like to know more, we recommend checking out the section on lists in Programming and Programming Languages (PAPL).

In lieu of a full explanation on this page, here are a few quick points to help parse some of the following examples:

A List is made up of elements, usually referred to as elts in examples.

Elements are of two types: link and empty.

Every link actually has two parts: a first value and the rest of the List.

The rest of the List is itself a link, or if you have reached the end of the List, the rest will be empty.

##### 3.7.2` `The list Constructor

This illustrates the underlying structure created when you define a List with [list: ...]

Constructs a List out of elts by chaining links, ending in a single empty.

check: [list: ] is empty [list: 1] is link(1, empty) [list: 1, 2] is link(1, link(2, empty)) end

Note: Explicitly writing the trailing empty is both unnecessary and wrong; the constructor notation needs only the elements of the List.

##### 3.7.3` `List Methods

These methods are available on all Lists, both "link" and "empty" instances and are accessed by dot operators.

Returns the number of elements in the List.

check: [list: 'a', 'b'].length() is 2 empty.length() is 0 link("a", empty).length() is 1 end

Applies function f to each element of the list from left to right, and constructs a new List out of the return values in the corresponding order.

a represents the type of the elements in the original List, b is the type of the elements in the new List.

check: [list: 1, 2].map(num-tostring) is [list: "1", "2"] [list: 1, 2].map(lam(n): n + 1 end) is [list: 2, 3] [list: 1, 2].map(_ + 1) is [list: 2, 3] empty.map(lam(x): raise("This never happens!") end) is empty end

Applies f to each element of the List from left to right, and returns nothing. Because it returns nothing, use each instead of map when the function f is needed only for its side-effects.

check: var x = 1 [list: 1, 2].each(lam(n): x := x + n end) is nothing x is 4 end

Applies function f to each element of List from left to right, constructing a new List out of the elements for which f returned true.

The original List elements are of type a and the function f must return a Boolean.

check: fun length-is-one(s :: String) -> Boolean: string-length(s) == 1 end [list: "ab", "a", "", "c"].filter(length-is-one) is [list: "a", "c"] [list: empty, link(1, empty), empty].filter(is-link) is [list: link(1, empty)] end

Returns link(elt, self).

check: empty.push("a") is link("a", empty) link("a", empty).push("b") is link("b", link("a", empty)) end

In other words, returns a List with elt appended to the beginning of the original List.

check: [list: 'a', 'b'].push('c') is [list: 'c', 'a', 'b'] end

Produces a record containing two Lists, consisting of the items before and the items at-or-after the splitting index of the current List. The index is 0-based, so splitting a List at index n will produce a prefix of length exactly n. Moreover, appending the two Lists together will be equivalent to the original List.

check: [list: 'a', 'b', 'c', 'd'].split-at(2) is {prefix: [list: "a", "b"], suffix: [list: "c", "d"]} one-four = link(1, link(2, link(3, link(4, empty)))) one-four.split-at(0) is {prefix: empty, suffix: one-four} one-four.split-at(4) is {prefix: one-four, suffix: empty} one-four.split-at(2) is {prefix: link(1, link(2, empty)), suffix: link(3, link(4, empty))} one-four.split-at(-1) raises "Invalid index" one-four.split-at(5) raises "Index too large" end

Given a length n, returns a new List containing the first n items of the List.

check: [list: 1, 2, 3, 4, 5, 6].take(3) is [list: 1, 2, 3] [list: 1, 2, 3].take(6) raises "Index too large" [list: 1, 2, 3].take(-1) raises "Invalid index" end

Given a length n, returns a List containing all but the first n items of the List.

check: [list: 1, 2, 3, 4, 5, 6].drop(3) is [list: 4, 5, 6] end

check: [list: 1, 2, 3].get(0) is 1 [list: ].get(0) raises "too large" [list: 1, 2, 3].get(-1) raises "invalid argument" end

Returns a new List with the same values as the given List but with the nth element set to the given value, or raises an error if n is out of range.

check: [list: 1, 2, 3].set(0, 5) is [list: 5, 2, 3] [list: ].set(0, 5) raises "too large" end

Computes f(last-elt, ... f(second-elt, f(first-elt, base))...). For empty, returns base.

In other words, .foldl uses the function f, starting with the base value, of type Base, to calculate the return value of type Base from each item in the List, of input type Elt, starting the sequence from the left (hence, foldl).

check: [list: 3, 2, 1].foldl(lam(elt, acc): elt + acc end, 10) is 16 fun combine(elt, acc) -> String: tostring(elt) + " - " + acc end [list: 3, 2, 1].foldl(combine, "END") is "1 - 2 - 3 - END" empty.foldl(combine, "END") is "END" [list: 3, 2, 1].foldl(link, empty) is link(1, link(2, link(3, empty))) end

Computes f(first-elt, f(second-elt, ... f(last-elt, base))). For empty, returns base.

In other words, .foldr uses the function f, starting with the base value, of type Base, to calculate the return value of type Base from each item in the List, of input type Elt, starting the sequence from the right (hence, foldr).

check: [list: 3, 2, 1].foldr(lam(elt, acc): elt + acc end, 10) is 16 fun combine(elt, acc) -> String: tostring(elt) + " - " + acc end [list: 3, 2, 1].foldr(combine, "END") is "3 - 2 - 1 - END" empty.foldr(combine, "END") is "END" [list: 3, 2, 1].foldr(link, empty) is link(3, link(2, link(1, empty))) end

Passing a Roughnum as an argument will raise an error.

check: [list: 1, 2, 3].member(2) is true [list: 2, 4, 6].member(3) is false [list: ].member(empty) is false [list: 1, 2, 3].member(~1) raises "Roughnums" [list: ~1, 2, 3].member(1) raises "Roughnums" [list: 1, 2, 3].member(4) is false [list: 1, 2, 3].member(~4) raises "Roughnums" [list: 'a'].member('a') is true [list: false].member(false) is true [list: nothing].member(nothing) is true end

Produces a new List with all the elements of the current List, followed by all the elements of the other List.

check: [list: 1, 2].append([list: 3, 4]) is [list: 1, 2, 3, 4] empty.append([list: 1, 2]) is [list: 1, 2] [list: 1, 2].append(empty) is [list: 1, 2] end

check: [list: 1, 2, 3].last() is 3 empty.last() raises "last of empty list" end

check: [list: 1, 2, 3].reverse() is [list: 3, 2, 1] empty.reverse() is empty end

check: [list: 1, 5, 3, 2, 4].sort() is [list: 1, 2, 3, 4, 5] [list: "aaaa", "B", "a"].sort() is [list: "B", "a", "aaaa"] [list: 'a', 1].sort() raises "binop-error" [list: true, false].sort() raises "binop-error" end

Like sort, but the comparison and equality operators can be specified. This allows for sorting Lists whose contents are not comparable by <, or sorting by custom comparisons, for example, sorting by string length instead of alphabetically.

check: fun length-comparison(s1 :: String, s2 :: String) -> Boolean: string-length(s1) > string-length(s2) end fun length-equality(s1 :: String, s2 :: String) -> Boolean: string-length(s1) == string-length(s2) end [list: 'a', 'aa', 'aaa'].sort-by(length-comparison, length-equality) is [list: 'aaa', 'aa', 'a'] end

check: [list: 1, 2, 3].join-str("; ") is "1; 2; 3" [list: "a", true, ~5.3].join-str(" : ") is "a : true : ~5.3" empty.join-str("nothing at all") is "" end

check: [list: 1, 2, 3].join-str-last(", ", " and ") is "1, 2 and 3" [list: "a", true, ~5.3].join-str-last(" : ", " # ") is "a : true # ~5.3" empty.join-str-last("nothing at all", "really nothing") is "" [list: 1, 2].join-str-last("a", "b") is "1b2" [list: 1].join-str-last("a", "b") is "1" end

##### 3.7.4` `List Functions

These functions are available on the lists module object. Some of the functions require the lists module to be imported, as indicated in the examples.

Returns the number of elements in the List.

import lists as L check: L.length([list: 'a', 'b']) is 2 L.length(empty) is 0 L.length(link("a", empty)) is 1 end

Returns the nth element of the given list, or raises an error if n is out of range

import lists as L check: L.get([list: 1, 2, 3], 0) is 1 L.get([list: ], 0) raises "too large" L.get([list: 1, 2, 3], -1) raises "invalid argument" end

Returns a new list with the same values as the given list but with the nth element set to the given value, or raises an error if n is out of range

import lists as L check: L.set([list: 1, 2, 3], 0, 5) is [list: 5, 2, 3] L.set([list: ], 0, 5) raises "too large" end

import lists as L check: L.sort([list: 1, 5, 3, 2, 4]) is [list: 1, 2, 3, 4, 5] L.sort([list: "aaaa", "B", "a"]) is [list: "B", "a", "aaaa"] L.sort([list: 'a', 1]) raises "binop-error" L.sort([list: true, false]) raises "binop-error" end

import lists as L check: fun length-comparison(s1 :: String, s2 :: String) -> Boolean: string-length(s1) > string-length(s2) end fun length-equality(s1 :: String, s2 :: String) -> Boolean: string-length(s1) == string-length(s2) end L.sort-by([list: 'a', 'aa', 'aaa'], length-comparison, length-equality) is [list: 'aaa', 'aa', 'a'] end

check: [list: 1, 2, 3].join-str("; ") is "1; 2; 3" [list: "a", true, ~5.3].join-str(" : ") is "a : true : ~5.3" empty.join-str("nothing at all") is "" end

Creates a list of numbers, starting with start, ending with stop-1

check: range(0, 0) is [list: ] range(0, 1) is [list: 0] range(-5, 5) is [list: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4] end

Creates a list of numbers, starting with start, in intervals of delta, until reaching (but not including) stop

import lists as L check: L.range-by(1, 10, 4) is [list: 1, 5, 9] L.range-by(10, 1, -4) is [list: 10, 6, 2] L.range-by(3, 20, 9) is [list: 3, 12] L.range-by(20, 3, 9) is empty L.range-by(20, 3, -9) is [list: 20, 11] L.range-by(2, 3, 0) raises "interval of 0" end

Creates a list with n copies of e

check: repeat(0, 10) is empty repeat(3, -1) is [list: -1, -1, -1] repeat(1, "foo") is link("foo", empty) repeat(3, empty) is [list: [list: ], [list: ], [list: ]] end

Given a List, returns a new List containing only one copy of each element that is duplicated in the List.

The last (latest in the List) copy is kept. Roughnums are not compared for equality, and so will always appear in the output List.

import lists as L check: L.distinct([list: 3, 1, 2, 2, 3, 2]) is [list: 1, 3, 2] L.distinct([list: ~1, ~1]) is-roughly [list: ~1, ~1] L.distinct([list: ~1, ~1, 1]) is-roughly [list: ~1, ~1, 1] L.distinct([list: ~1, ~1, 1, 1]) is-roughly [list: ~1, ~1, 1] L.distinct([list: ~1, ~2, ~3]) is-roughly [list: ~1, ~2, ~3] end

Returns the subset of lst for which f(elem) is true

check: fun length-is-one(s :: String) -> Boolean: string-length(s) == 1 end filter(length-is-one, [list: "ab", "a", "", "c"]) is [list: "a", "c"] filter(is-link, [list: empty, link(1, empty), empty]) is [list: link(1, empty)] end

Splits the list into two lists, one for which f(elem) is true, and one for which f(elem) is false

check: partition(lam(e): e > 0 end, [list: -1, 1]) is {is-true: [list: 1], is-false: [list: -1]} partition(lam(e): e > 5 end, [list: -1, 1]) is {is-true: [list: ], is-false: [list: -1, 1]} partition(lam(e): e < 5 end, [list: -1, 1]) is {is-true: [list: -1, 1], is-false: [list: ]} end

Returns some(elem) where elem is the first elem in lst for which f(elem) returns true, or none otherwise

check: find(num-is-integer, [list: 2.5, 3.5, 100, 2, 4.5]) is some(100) find(num-is-rational, [list: 2.5, 3.5, 100, 2, 4.5]) is some(2.5) find(num-is-negative, [list: 2.5, 3.5, 100, 2, 4.5]) is none find(lam(n): n <= 2 end, [list: 2.5, 3.5, 100, 2, 4.5]) is some(2) find(lam(n): n < 1 end, [list: 2.5, 3.5, 100, 2, 4.5]) is none end

Splits the list into two lists, one containing the first n elements, and the other containing the rest

check: split-at(2, [list: 'a', 'b', 'c', 'd']) is {prefix: [list: "a", "b"], suffix: [list: "c", "d"]} split-at(0, [list: 1, 2, 3, 4]) is {prefix: empty, suffix: [list: 1, 2, 3, 4]} split-at(4, [list: 1, 2, 3, 4]) is {prefix: [list: 1, 2, 3, 4], suffix: empty} split-at(2, [list: 1, 2, 3, 4]) is {prefix: [list: 1, 2], suffix: [list: 3, 4]} split-at(-1, [list: 1, 2, 3, 4]) raises "Invalid index" split-at(5, [list: 1, 2, 3, 4]) raises "Index too large" end end

Returns the last element in lst. Raises an error if the List is empty.

import lists as L check: L.last([list: 1, 3, 5]) is 5 L.last([list: 1]) is 1 L.last([list: ]) raises "last of empty list" end

check: push(empty, "a") is link("a", empty) push(link("a", empty), "b") is link("b", link("a", empty)) end

Produce a new List with the elements of front followed by the elements of back.

import lists as L check: L.append([list: 1, 2, 3], [list: 4, 5, 6]) is [list: 1, 2, 3, 4, 5, 6] L.append([list:], [list:]) is [list:] L.append([list: 1], [list: 2]) is [list: 1, 2] end

Note that it does not change either List:

check: l = [list: 1, 2, 3] append(l, [list: 4]) l is [list: 1, 2, 3, 4] # this test fails end

Returns true if f(elem) returns true for any elem of lst

import lists as L check: L.any(is-number, [list: 1, 2, 3]) is true L.any(is-string, [list: 1, 2, 3]) is false L.any(lam(n): n > 1 end, [list: 1, 2, 3]) is true L.any(lam(n): n > 3 end, [list: 1, 2, 3]) is false end

Returns true if f(elem) returns true for all elems of lst

import lists as L check: L.all(is-number, [list: 1, 2, 3]) is true L.all(is-string, [list: 1, 2, 'c']) is false L.all(lam(n): n > 1 end, [list: 1, 2, 3]) is false L.all(lam(n): n <= 3 end, [list: 1, 2, 3]) is true end

Returns true if f(elem1, elem2) returns true for all corresponding elems of lst1 and list2. Returns true when either list is empty

When the Lists are of different length, the function is only called when both Lists have a value at a given index. In other words, Pyret iterates over the shortest List and stops.

import lists as L check: L.all2(lam(n, m): n > m end, [list: 1, 2, 3], [list: 0, 1, 2]) is true L.all2(lam(n, m): (n + m) == 3 end, [list: 1, 2, 3], [list: 2, 1, 0]) is true L.all2(lam(n, m): (n + m) == 3 end, [list: 1, 2], [list: 2, 1, 0]) is true L.all2(lam(n, m): (n + m) == 3 end, [list: 1, 2, 6], [list: 2, 1]) is true L.all2(lam(n, m): n > m end, [list: 1, 2, 3], [list: 0, 1, 2]) is true L.all2(lam(n, m): n > m end, [list: 1, 2, 0], [list: 0, 1]) is true L.all2(lam(n, m): n < m end, [list: 1], [list: 2, 0]) is true L.all2(lam(n, m): n < m end, [list: 1, 2, 3], empty) is true end

Returns a list made up of f(elem) for each elem in lst

check: map(num-tostring, [list: 1, 2]) is [list: "1", "2"] map(lam(x): x + 1 end, [list: 1, 2]) is [list: 2, 3] end

Returns a list made up of f(elem1, elem2) for each elem1 in l1, elem2 in l2

When the Lists are of different length, the function is only called when both Lists have a value at a given index. In other words, Pyret iterates over the shortest List and stops.

check: map2(string-append, [list: "mis", "mal"], [list: "fortune", "practice"]) is [list: "misfortune", "malpractice"] map2(_ + _, [list: "mis", "mal"], [list: "fortune", "practice"]) is [list: "misfortune", "malpractice"] map2(string-append, [list: "mis", "mal"], [list: "fortune"]) is [list: "misfortune"] map2(string-append, [list: "mis", "mal"], empty) is empty end

Returns a list made up of f(e1, e2, e3) for each e1 in l1, e2 in l2, e3 in l3

When the Lists are of different length, the function is only called when all Lists have a value at a given index. In other words, Pyret iterates over the shortest List and stops.

check: fun full-name(first, middle, last) -> String: first + " " + middle + " " + last end full-name("Thomas", "Alva", "Edison") is "Thomas Alva Edison" map3(full-name, [list: "Martin", "Mohandas", "Pelé"], [list: "Luther", "Karamchand"], [list: "King", "Gandhi"]) is [list: "Martin Luther King", "Mohandas Karamchand Gandhi"] end

Returns a list made up of f(e1, e2, e3, e4) for each e1 in l1, e2 in l2, e3 in l3, e4 in l4

When the Lists are of different length, the function is only called when all Lists have a value at a given index. In other words, Pyret iterates over the shortest List and stops.

check: fun title-name(title, first, middle, last) -> String: title + " " + first + " " + middle + " " + last end map4(title-name, [list: "Reverend", "Mahātmā"], [list: "Martin", "Mohandas", "Pele"], [list: "Luther", "Karamchand"], [list: "King", "Gandhi"]) is [list: "Reverend Martin Luther King", "Mahātmā Mohandas Karamchand Gandhi"] end

Returns a list made up of f(n, e1), f(n+1, e2) .. for e1, e2 ... in lst

Like map, but also includes a numeric argument for the position in the List that is currently being mapped over.

check: map_n(num-expt, 0, [list: 2, 2, 2, 2]) is [list: 0, 1, 4, 9] map_n(lam(n, elem): n * elem end, 0, [list: 2, 2, 2, 2]) is [list: 0, 2, 4, 6] map_n(_ * _, 0, [list: 2, 2, 2, 2]) is [list: 0, 2, 4, 6] map_n(_ * _, 1, [list: 2, 2, 2, 2]) is [list: 2, 4, 6, 8] map_n(_ + _, 10, [list: 2, 2, 2, 2]) is [list: 12, 13, 14, 15] end

Returns a list made up of f(i, e1, e2) for each e1 in l1, e2 in l2, and i counting up from n

Like map_n, but for two-argument functions.

When the Lists are of different length, the function is only called when all Lists have a value at a given index. In other words, Pyret iterates over the shortest List and stops.

check: map2_n(lam(n, a, b): n * (a + b) end, 10, [list: 2, 2, 2, 2], [list: 0, 3, 9, 12]) is [list: 20, 55, 132, 182] end

Returns a list made up of f(i, e1, e2, e3) for each e1 in l1, e2 in l2, e3 in l3, and i counting up from n

check: fun combine(n, l1, l2, l3) -> String: string-repeat(l1, n) + string-repeat(l2, n) + string-repeat(l3, n) end combine(2, 'a', 'b', 'c') is "aabbcc" map3_n(combine, 1, [list: 'a', 'a'], [list: 'b', 'b'], [list: 'c', 'c']) is [list: 'abc', 'aabbcc'] end

Returns a list made up of f(i, e1, e2, e3, e4) for each e1 in l1, e2 in l2, e3 in l3, e4 in l4, and i counting up from n

check: fun combine(n, l1, l2, l3, l4) -> String: string-repeat(l1, n) + string-repeat(l2, n) + string-repeat(l3, n) + string-repeat(l4, n) end combine(2, 'a', 'b', 'c', 'd') is "aabbccdd" map4_n(combine, 1, repeat(3, 'a'), repeat(3, 'b'), repeat(3, 'c'), repeat(3, 'd')) is [list: 'abcd', 'aabbccdd', 'aaabbbcccddd'] end

Calls f for each elem in lst, and returns nothing

check: one-four = [list: 1, 2, 3, 4] block: var counter = 0 each(lam(n): counter := counter + n end, one-four) counter is 1 + 2 + 3 + 4 counter is 10 end block: var counter = 1 each(lam(n): counter := counter * n end, one-four) counter is 1 * 2 * 3 * 4 counter is 24 end end

Calls f on each pair of corresponding elements in l1 and l2, and returns nothing. Stops after the shortest list

check: var counter = 0 each2(lam(x, y): counter := counter + x + y end, [list: 1, 1, 1], [list: 10, 10, 10, 10]) counter is 33 end

Calls f on each triple of corresponding elements in l1, l2 and l3, and returns nothing. Stops after the shortest list

check: var counter = 0 each3(lam(x, y, z): counter := counter + x + y + z end, [list: 1, 1, 1], [list: 10, 10, 10, 10], [list: 100, 100]) counter is 222 end

Calls f on each tuple of corresponding elements in l1, l2, l3 and l4, and returns nothing. Stops after the shortest list

check: var counter = 0 each4(lam(w, x, y, z): counter := counter + w + x + y + z end, [list: 1, 1, 1], [list: 10, 10, 10, 10], [list: 100, 100], [list: 1000, 1000]) counter is 2222 end

Calls f(i, e) for each e in lst and with i counting up from num, and returns nothing

Like each, but also includes a numeric argument for the current index in the List.

check: var counter = 0 each_n(lam(i, w): counter := counter + (i * w) end, 1, [list: 1, 1, 1]) counter is 6 end

Calls f(i, e1, e2) for each e1 in lst1, e2 in lst2 and with i counting up from num, and returns nothing

check: var counter = 0 each2_n(lam(i, w, x): counter := counter + (i * (w + x)) end, 1, [list: 1, 1, 1], [list: 10, 10, 10, 10]) counter is 66 end

Calls f(i, e1, e2, e3) for each e1 in lst1, e2 in lst2, e3 in lst3 and with i counting up from num, and returns nothing

check: var counter = 0 each3_n(lam(i, w, x, y): counter := counter + (i * (w + x + y)) end, 1, [list: 1, 1, 1], [list: 10, 10, 10, 10], [list: 100, 100, 100]) counter is 666 end

Calls f(i, e1, e2, e3, e4) for each e1 in lst1, e2 in lst2, e3 in lst3, e4 in lst4 and with i counting up from num, and returns nothing

check: var counter = 0 each4_n(lam(i, w, x, y, z): counter := counter + (i * (w + x + y + z)) end, 1, [list: 1, 1, 1], [list: 10, 10, 10, 10], [list: 100, 100, 100], [list: 1000, 1000, 1000]) counter is 6666 end

- fold-while :: (
- f :: (Base, Elt -> Either<Base, Base>),
- base :: Base,
- lst :: List<Elt>
- )
- -> Base

Takes a function that takes two arguments and returns an Either, and also a base value, and folds over the given list from the left as long as the function returns a left() value, and returns either the final value or the right() value

import lists as L import either as EI check: fun stop-at-not-one(acc :: Number, n :: Number) -> EI.Either: if n == 1: EI.left(acc + n) else: EI.right(acc) end end L.fold-while(stop-at-not-one, 0, [list: 1, 1, 1, 0, 1, 1]) is 3 end

Takes a function, an initial value and a list, and folds the function over the list from the left, starting with the initial value

fold computes f(last-elt, ... f(second-elt, f(first-elt, base))...). For empty, returns base.

In other words, fold uses the function f, starting with the base value, of type Base, to calculate the return value of type Base from each item in the List, of input type Elt, starting the sequence from the left.

check: fold((lam(acc, elt): acc + elt end), 0, [list: 3, 2, 1]) is 6 fold((lam(acc, elt): acc + elt end), 10, [list: 3, 2, 1]) is 16 f fun combine(acc, elt) -> String: tostring(elt) + " - " + acc end fold(combine, "END", [list: 3, 2, 1]) is "1 - 2 - 3 - END" fold(combine, "END", empty) is "END" end

Takes a function, an initial value and a list, and folds the function over the list from the left, starting with the initial value

Another name for fold.

Takes a function, an initial value and a list, and folds the function over the list from the right, starting with the initial value

Computes f(first-elt, f(second-elt, ... f(last-elt, base))). For empty, returns base. In other words, it uses f to combine base with each item in the List starting from the right.

In other words, foldr uses the function f, starting with the base value, of type Base, to calculate the return value of type Base from each item in the List, of input type Elt, starting the sequence from the right.

import lists as L check: L.foldr((lam(acc, elt): acc + elt end), 0, [list: 3, 2, 1]) is 6 L.foldr((lam(acc, elt): acc + elt end), 10, [list: 3, 2, 1]) is 16 fun combine(acc, elt) -> String: tostring(elt) + " - " + acc end L.foldr(combine, "END", [list: 3, 2, 1]) is "3 - 2 - 1 - END" L.foldr(combine, "END", empty) is "END" end

Takes a function, an initial value and two lists, and folds the function over the lists in parallel from the left, starting with the initial value and ending when either list is empty

check: fold2(lam(acc, elt1, elt2): acc + elt1 + elt2 end, 11, [list: 1, 1, 1], [list: 10, 10, 10, 10]) is 44 end

Takes a function, an initial value and three lists, and folds the function over the lists in parallel from the left, starting with the initial value and ending when any list is empty

check: fold3(lam(acc, elt1, elt2, elt3): acc + elt1 + elt2 + elt3 end, 111, [list: 1, 1, 1], [list: 10, 10, 10, 10], [list: 100, 100, 100]) is 444 end

Takes a function, an initial value and four lists, and folds the function over the lists in parallel from the left, starting with the initial value and ending when any list is empty

check: fold4(lam(acc, elt1, elt2, elt3, elt4): acc + elt1 + elt2 + elt3 + elt4 end, 1111, [list: 1, 1, 1], [list: 10, 10, 10, 10], [list: 100, 100, 100], [list: 1000, 1000]) is 3333 end

Takes a function, an initial value and a list, and folds the function over the list from the left, starting with the initial value and passing along the index (starting with the given num)

Like fold, but takes a numeric argument for the position in the List that is currently being visited.

import lists as L check: # for comparison, here is a map_n example: map_n(lam(index, elt): index * elt end, 0, [list: 2, 2, 2, 2]) is [list: 0, 2, 4, 6] # this fold_n version adds up the result L.fold_n(lam(index, acc, elt): acc + (index * elt) end, 0, 0, [list: 2, 2, 2, 2]) is 12 L.fold_n(lam(index, acc, elt): acc + (index * elt) end, 0, 10, [list: 2, 2, 2, 2]) is 22 L.fold_n(lam(index, acc, elt): acc + (index * elt) end, 10, 0, [list: 2, 2, 2, 2]) is 92 # 20+22+24+26=92 end

Returns true if List lst contains the element elt, as compared by ==.

Passing a Roughnum as elt will raise an error.

check: member([list: 1, 2, 3], 2) is true member([list: 2, 4, 6], 3) is false [list: ].member(empty) is false [list: 1, 2, 3].member(~1) raises "Roughnums" [list: ~1, 2, 3].member(1) is false [list: 'a'].member('a') is true [list: false].member(false) is true [list: nothing].member(nothing) is true end

- member-with :: (
- lst :: List<a>,
- elt :: a,
- eq :: (a, a -> EqualityResult)
- )
- -> EqualityResult

member with a custom equality function. Returns an equality.Equal if function eq returns equality.Equal for elt and any one element of List lst.

import lists as L import equality as EQ check: fun equal-length(a :: String, b :: String) -> EQ.EqualityResult: if string-length(a) == string-length(b): EQ.Equal else: EQ.NotEqual("Different lengths.", a, b) end end equal-length('tom', 'dad') is EQ.Equal equal-length('tom', 'father') satisfies EQ.is-NotEqual L.member-with([list: 'father', 'pater', 'dad'], 'tom', equal-length) is EQ.Equal L.member-with([list: 'father', 'pater'], 'tom', equal-length) satisfies EQ.is-NotEqual end

Analogous to member, but uses equal-always or identical to perform the comparison.

Analogous to member-with, but uses equal-always3 to perform the comparison.

Analogous to member-with, but uses identical3 to perform the comparison.

Analogous to member-with, but uses equal-now3 to perform the comparison.

Returns a new List with all the elements of the original List in reverse order.

import lists as L check: l = [list: 1, 2, 3, 4] L.reverse(l) is [list: 4, 3, 2, 1] end

Returns the list without the element if found, or the whole list if it is not

Returns a new List with all the elements of the original that are not equal to the specified element (using == as the comparison).

import lists as L check: l = [list: 1, 2, 3, 4, 3, 2, 1] L.remove(l, 2) is [list: 1, 3, 4, 3, 1] end

Returns a new List with all the elements of the original List in random order.

import lists as L import sets as S check: l = [list: 1, 2, 3, 4] l-mixed = L.shuffle(l) S.list-to-set(l-mixed) is S.list-to-set(l) l-mixed.length() is l.length() end