3.7 lists

8.11.1

contents ← prev up next →

3.7 lists

Usage:

include lists

import lists as ...

3.7.1 The List Datatype

data List<a>:

| empty
| link(first :: a, rest :: List<a>)

end

empty :: List<a>
link :: (first :: a, rest :: List<a>) -> List<a>
is-empty :: (val :: Any) -> Boolean
is-link :: (val :: Any) -> Boolean
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

[list: elt :: a, ...] -> List<a>

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.

Examples:

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.

.length :: () -> Number

Returns the number of elements in the List.

Examples:

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

.map :: (f :: (a -> b)) -> List

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.

Examples:

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

.each :: (f :: (a -> Nothing)) -> Nothing

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.

Examples:

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

.filter :: (f :: (a -> Boolean)) -> List<a>

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.

Examples:

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

.push :: (elt :: a) -> List<a>

Returns link(elt, self).

Examples:

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.

Examples:

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

.split-at :: (n :: Number) -> {prefix :: List<a>, suffix :: List<a>}

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.

Examples:

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

.take :: (n :: Number) -> List<a>

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

Examples:

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

.drop :: (n :: Number) -> List<a>

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

Examples:

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

.get :: (n :: Number) -> a

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

Examples:

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

.set :: (n :: Number, e :: a) -> List<a>

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.

Examples:

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

.foldl :: (f :: (a, Base -> Base), base :: Base) -> Base

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).

Examples:

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

.foldr :: (f :: (a, Base -> Base), base :: Base) -> Base

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).

Examples:

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

.member :: (elt :: a) -> Boolean

Passing a Roughnum as an argument will raise an error.

Returns true if the current List contains the given value, as compared by ==.

Examples:

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

.append :: (other :: List<a>) -> List<a>

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

Examples:

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

.last :: () -> a

Returns the last item of the List.

Examples:

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

.reverse :: () -> List<a>

Produces a new List with the items of the original List in reversed order.

Examples:

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

.sort :: () -> List<a>

Produces a new List whose contents are the same as those of the current List, sorted by < and ==. This requires that the items of the List be comparable by < (see Binary Operators).

Examples:

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

.sort-by :: (cmp :: (a, a -> Boolean), eq :: (a, a -> Boolean)) -> List<a>

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.

Examples:

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

.join-str :: (sep :: String) -> String

Combines the values of the current List by converting them to strings with tostring and joining them with the given separator sep.

Examples:

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

.join-str-last :: (sep :: String, last-sep :: String) -> String

Combines the values of the current List by converting them to strings with tostring and joining them with the given separator sep. If the list has more than one element, the function will use last-sep to join the last element instead of the regular sep.

Examples:

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.

length :: (lst :: List<a>) -> Number

Returns the number of elements in the List.

Examples:

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

get :: (lst :: List<a>, n :: Number) -> a

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

Examples:

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

set :: (
lst :: List<a>,
n :: Number,
v :: a
)
-> List<a>

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

Examples:

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

sort :: (lst :: List<A>) -> List<A>

Produces a new List whose contents are the same as those of the current List, sorted by < and ==. This requires that the items of the List be comparable by < (see Binary Operators).

Examples:

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

sort-by :: (
lst :: List<A>,
cmp :: (A, A -> Boolean),
eq :: (A, A -> Boolean)
)
-> List<A>

Examples:

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

join-str :: (lst :: List<A>, sep :: String) -> String

Examples:

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

range :: (start :: Number, stop :: Number) -> List<Number>

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

Examples:

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

range-by :: (
start :: Number,
stop :: Number,
delta :: Number
)
-> List<Number>

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

Examples:

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

repeat :: (n :: Number, e :: a) -> List<a>

Creates a list with n copies of e

Examples:

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

distinct :: (lst :: List<a>) -> List<a>

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.

Examples:

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

filter :: (f :: (a -> Boolean), lst :: List<a>) -> List<a>

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

Examples:

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

partition :: (f :: (a -> Boolean), lst :: List<a>) -> {is-true :: List<a>, is-false :: List<a>}

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

Examples:

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

find :: (f :: (a -> Boolean), lst :: List<a>) -> Option<a>

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

Examples:

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

split-at :: (n :: Number, lst :: List<a>) -> {prefix :: List<a>, suffix :: List<a>}

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

Examples:

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

last :: (lst :: List<A>) -> A

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

Examples:

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

push :: (l :: List<A>, elt :: A) -> List<A>

Constructs a list with the given element prepended to the front of the given list.

Examples:

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

append :: (front :: List<A>, back :: List<A>) -> List<A>

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

any :: (f :: (a -> Boolean), lst :: List<a>) -> Boolean

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

Examples:

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

all :: (f :: (a -> Boolean), lst :: List<a>) -> Boolean

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

Examples:

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

all2 :: (
f :: (a, b -> Boolean),
lst1 :: List,
lst2 :: List
)
-> Boolean

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.

Examples:

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

map :: (f :: (a -> b), lst :: List<a>) -> List

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

Examples:

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

map2 :: (
f :: (a, b -> c),
l1 :: List<a>,
l2 :: List
)
-> List<c>

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.

Examples:

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

map3 :: (
f :: (a, b, c -> d),
l1 :: List<a>,
l2 :: List,
l3 :: List<c>
)
-> List<d>

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.

Examples:

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

map4 :: (
f :: (a, b, c, d -> e),
l1 :: List<a>,
l2 :: List,
l3 :: List<c>,
l4 :: List<d>
)
-> List<e>

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.

Examples:

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

map_n :: (
f :: (Number, a -> b),
n :: Number,
lst :: List<a>
)
-> List

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.

Examples:

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

map2_n :: (
f :: (Number, a, b -> c),
n :: Number,
l1 :: List<a>,
l2 :: List
)
-> List<c>

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.

Examples:

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

map3_n :: (
f :: (Number, a, b, c -> d),
n :: Number,
l1 :: List<a>,
l2 :: List,
l3 :: List<c>
)
-> List<d>

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

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.

Examples:

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

map4_n :: (
f :: (Number, a, b, c, d -> e),
n :: Number,
l1 :: List<a>,
l2 :: List,
l3 :: List<c>,
l4 :: List<d>
)
-> List<e>

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

Examples:

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

each :: (f :: (a -> Nothing), lst :: List<a>) -> Nothing

Calls f for each elem in lst, and returns nothing

Examples:

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

each2 :: (
f :: (a, b -> Nothing),
lst1 :: List<a>,
lst2 :: List
)
-> Nothing

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

Examples:

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

each3 :: (
f :: (a, b, c -> Nothing),
lst1 :: List<a>,
lst2 :: List,
lst3 :: List<c>
)
-> Nothing

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

Examples:

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

each4 :: (
f :: (a, b, c, d -> Nothing),
lst1 :: List<a>,
lst2 :: List,
lst3 :: List<c>,
lst4 :: List<d>
)
-> Any

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

Examples:

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

each_n :: (
f :: (Number, a -> Nothing),
num :: Number,
lst :: List<a>
)
-> Nothing

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.

Examples:

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

each2_n :: (
f :: (Number, a, b -> Nothing),
num :: Number,
lst1 :: List<a>,
lst2 :: List
)
-> Nothing

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

Examples:

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

each3_n :: (
f :: (Number, a, b, c -> Nothing),
num :: Number,
lst1 :: List<a>,
lst2 :: List,
lst3 :: List<c>
)
-> Nothing

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

Examples:

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

each4_n :: (
f :: (a, b, c, d -> Nothing),
num :: Number,
lst1 :: List<a>,
lst2 :: List,
lst3 :: List<c>,
lst4 :: List<d>
)
-> Nothing

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

Examples:

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

Examples:

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

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

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(... f(f(base, first-elt), second-elt) ..., last-elt). 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.

Examples:

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

foldl :: (
f :: (Base, Elt -> Base),
base :: Base,
lst :: List<Elt>
)
-> Base

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.

foldr :: (
f :: (Base, Elt -> Base),
base :: Base,
lst :: List<Elt>
)
-> Base

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(f(... f(base, last-elt) ..., second-elt), first-elt). 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.

Examples:

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

fold2 :: (
f :: (Base, Elt1, Elt2 -> Base),
base :: Base,
l1 :: List<Elt1>,
l2 :: List<Elt2>
)
-> Base

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

Examples:

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

fold3 :: (
f :: (Base, Elt1, Elt2, Elt3 -> Base),
base :: Base,
l1 :: List<Elt1>,
l2 :: List<Elt2>,
l3 :: List<Elt3>
)
-> Base

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

Examples:

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

fold4 :: (
f :: (Base, Elt1, Elt2, Elt3, Elt4 -> Base),
base :: Base,
l1 :: List<Elt1>,
l2 :: List<Elt2>,
l3 :: List<Elt3>,
l4 :: List<Elt4>
)
-> Base

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

Examples:

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

fold_n :: (
f :: (Number, Base, Elt -> Base),
num :: Number,
base :: Base,
lst :: List<Elt>
)
-> Base

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.

Examples:

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

member :: (lst :: List<a>, elt :: a) -> Boolean

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

Passing a Roughnum as elt will raise an error.

Examples:

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.

Examples:

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

member-always :: (lst :: List<a>, elt :: a) -> Boolean

member-identical :: (lst :: List<a>, elt :: a) -> Boolean

member-now :: (lst :: List<a>, elt :: a) -> Boolean

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

member3 :: (lst :: List<a>, elt :: a) -> EqualityResult

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

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

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

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

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

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

reverse :: (lst :: List<a>) -> List<a>

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

Examples:

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

remove :: (lst :: List<a>, elt :: a) -> List<a>

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).

Examples:

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

shuffle :: (lst :: List<a>) -> List<a>

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

Examples:

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

contents ← prev up next →

1	Getting Started
2	Language Concepts
3	Builtins and Libraries
4	Pyret Style Guide
5	Internals
6	Glossary

3.1	Global Utilities
3.2	Numbers
3.3	Strings
3.4	Booleans
3.5	Raw Array
3.6	Tables
3.7	lists
3.8	sets
3.9	arrays
3.10	string-dict
3.11	option
3.12	pick
3.13	either
3.14	srcloc
3.15	pprint
3.16	s-exp
3.17	s-exp-structs
3.18	color
3.19	image-structs
3.20	The image libraries
3.21	world
3.22	gdrive-sheets
3.23	data-source
3.24	reactors
3.25	chart
3.26	plot
3.27	statistics
3.28	math

3.7.1	The List Datatype
3.7.2	The list Constructor
3.7.3	List Methods
3.7.4	List Functions