6.31 Pairs and Pair Lists

8.12

6.31 Pairs and Pair Lists🔗ℹ

A pair combines two values: a “first” value and a “rest” value. A pair list is a listable value that is constructed with pairs and the empty pair list; every non-empty pair list is a pair, a pair is a pair list only if its “rest” is a list.

The . operator can be used on a pair expression as equivalent to calling Pair functions:

pr.first
is
Pair.first(pr)
pr.rest
is
Pair.rest(pr)

The . operator can be used on a pait list expression as equivalent to calling PairList functions:

lst.length()
is
PairList.length(lst)
lst.get(n)
is
PairList.get(lst, n)
lst.first
is
PairList.first(lst)
lst.last
is
PairList.last(lst)
lst.rest
is
PairList.rest(lst)
lst.reverse()
is
PairList.reverse(lst)
lst.append(lst2, ...)
is
PairList.append(lst, lst2, ...)
lst.take(n)
is
PairList.take(lst, n)
lst.take_last(n)
is
PairList.take_last(lst, n)
lst.drop(n)
is
PairList.drop(lst, n)
lst.drop_last(n)
is
PairList.drop_last(lst, n)
lst.has_element(v, eqls, ...)
is
PairList.has_element(lst, v, eqls, ...)
lst.find(pred)
is
PairList.find(lst, pred)
lst.remove(v)
is
PairList.remove(lst, v)
lst.map(func)
is
PairList.map(lst, func)
lst.for_each(func)
is
PairList.for_each(lst, func)
lst.sort(arg, ...)
is
PairList.sort(lst, arg, ...)
lst.to_list()
is
PairList.to_list(lst)
lst.to_sequence()
is
PairList.to_sequence(lst)

annotation

Pair

annotation

Pair.of(fst_annot, rst_annot)

Matches any pair in the form without of. The of variant matches a pair whose components satisfy fst_annot and rst_annot.

function

fun Pair(fst_v :: Any, rst_v :: Any) :: Pair

Constructs a pair containing fst_v and rst_v.

> def pr = Pair(1, 2)
> pr
Pair(1, 2)
> pr.first
1
> pr.rest
2

binding operator

Pair(fst_bind, rst_bind)

Matches a pair whose first component matches fst_bind and rest component matches rst_bind.

> def Pair(x, y) = Pair(1, 2)
> y
2
> def Pair(sx :: String, sy :: String) = Pair(1, 2)
def: value does not satisfy annotation
value: Pair(1, 2)
annotation: matching(Pair((_ :: String), (_ :: String)))
> def Pair(lx, ly) = PairList[1, 2]
> y
2

function

fun Pair.cons(fst :: Any, rst :: Any) :: Pair

binding operator

Pair.cons(fst_bind, rst_bind)

Aliases for Pair in expression and binding positions.

Note that the difference between Pair.cons and PairList.cons is that PairList.cons requires a list as is second argument, which means that it always forms a list. In contrast, Pair.cons allows any value as its second argument—but it creates a list if that argument is a list.

> Pair.cons(1, 2)
Pair(1, 2)
> Pair.cons(1, [2, 3])
Pair(1, [2, 3])

function

fun Pair.first(pr :: Pair)

function

fun Pair.rest(pr :: Pair)

Returns the first or second component of pr.

> Pair.first(Pair("a", "b"))
"a"
> Pair.rest(Pair("a", "b"))
"b"

annotation

PairList

annotation

PairList.of(annot)

Matches any pair list in the form without of. The of variant matches a pair list whose elements satisfy annot.

Static information associated by PairList or PairList.of makes an expression acceptable as a sequence to for in static mode.

function

fun PairList(v :: Any, ...) :: PairList

expression

PairList[expr_or_splice, ...]

repetition

PairList[repet_or_splice, ...]

expr_or_splice	=	expr
	\|	repet , ellipses
	\|	& listable_expr

ellipses	=	ellipsis
	\|	ellipses , ellipsis

ellipsis

...

Constructs a pair list of the given vs values or results of the expr_or_splices. A & or ... form can appear within […] to splice a repetition or existing listable value into the constructed pair list, the same as in a function call (see #%call). Pair-list constructions can also serve as repetitions, where repet_or_splice is like expr_or_splice, but with repetitions in place of expressions.

The #%brackets form is implicitly used when […] is used in in an expression position. See also Implicit Forms.

> def lst = PairList(1, 2, 3)
> lst
PairList[1, 2, 3]
> lst[0]
1
> lst ++ PairList[4, 5]
PairList[1, 2, 3, 4, 5]
> PairList[1, 2, 3]
PairList[1, 2, 3]

binding operator

PairList(bind, ...)

binding operator

PairList(bind, ..., rest)

binding operator

PairList[bind, ...]

binding operator

PairList[bind, ..., rest]

rest	=	repet_bind , ellipsis
	\|	& pair_list_bind

ellipsis

...

Matches a pair list with as many elements as binds, or if rest is included, at least as many elements as binds, where the rest (if present) matches the rest of the pair list.

When & pair_list_bind is used, the rest of the list must match the pair_list_bind. Static information associated by PairList is propagated to pair_list_bind.

When repet_bind is used and does not impose a predicate or conversion on a matching value (e.g., repet_bind is an identifier), then the corresponding elements of a matching value are not traversed, which means that matching can be constant-time. Using this repetition for the tail a new list similarly avoids traversing the elements.

The #%brackets form is implicitly used when […] is used in in a binding position. See also Implicit Forms.

> def PairList(1, x, y) = PairList[1, 2, 3]
> y
3
> def PairList[1, also_x, also_y] = PairList[1, 2, 3]
> also_y
3
> def PairList(1, & xs) = PairList[1, 2, 3]
> xs
PairList[2, 3]
> def PairList(1, x, ...) = PairList[1, 2, 3]
> PairList[x, ...]
PairList[2, 3]

annotation

NonemptyPairList

annotation

NonemptyPairList.of(annot)

Like PairList as an annotation, but matches only non-empty pair lists.

> PairList[1] :: NonemptyPairList
PairList[1]
> PairList[] :: NonemptyPairList
::: value does not satisfy annotation
value: PairList[]
annotation: NonemptyPairList

reducer

PairList

A reducer used with for, accumulates each result of a for body into a result pair list.

function

fun PairList.cons(elem :: Any, lst :: PairList) :: PairList

Creates a list like lst, but with elem added to the front. Adding a element to the front for a pair list takes O(1) time.

> PairList.cons(1, PairList[2, 3])
PairList[1, 2, 3]

binding operator

PairList.cons(elem_bind, list_bind)

Matches a non-empty pair list where elem_bind matches the first element of the pair list and list_bind matches the rest of the pair list. Static information associated by PairList is propagated to list_bind.

> def Pair.cons(x, y) = PairList[1, 2, 3]
> x
1
> y
PairList[2, 3]

value

def PairList.empty :: PairList = PairList[]

binding operator

PairList.empty

A name and pattern for the empty pair list.

function

fun PairList.get(lst :: PairList, n :: NonnegInt) :: Any

Equivalent to lst[n] (with the default implicit #%index form). Returns the nth element of lst (starting from 0). Accessing a pair list element by position takes O(N) time.

> PairList["a", "b", "c"].get(1)
"b"
> PairList["a", "b", "c"][1]
"b"

function

fun PairList.first(lst :: NonemptyPairList) :: Any

Returns the first element of lst. Accessing the first element takes O(1) time.

> PairList.first(PairList["a", "b", "c"])
"a"
> PairList["a", "b", "c"].first
"a"

function

fun PairList.last(lst :: NonemptyPairList) :: Any

Returns the last element of lst. Accessing the last element takes O(N) time.

> PairList.last(PairList["a", "b", "c"])
"c"
> PairList["a", "b", "c"].last
"c"

function

fun PairList.rest(lst :: NonemptyPairList) :: PairList

Returns a pair list like lst, but without its first element. For a given pair list, List.rest always produces the same value in the sense of ===, and accessing that values takes O(1) time.

> PairList.rest(PairList["a", "b", "c"])
PairList["b", "c"]
> PairList["a", "b", "c"].rest
PairList["b", "c"]

repetition

PairList.repet(list_expr)

Creates a repetition from a pair list. This is a shorthand for using ... with a PairList binding.

> def lst = PairList[1, 2, 3]
> block:
let PairList[x, ...] = lst
PairList[x+1, ...]
PairList[2, 3, 4]
> [PairList.repet(lst) + 1, ...]
[2, 3, 4]

function

fun PairList.length(lst :: PairList) :: NonnegInt

Returns the number of items in lst. Computing this length takes O(N) time.

> PairList.length(PairList[1, 4, 8])
3
> PairList.length(PairList[])
0
> PairList[1, 4, 8].length()
3
> PairList[].length()
0

function

fun PairList.reverse(lst :: PairList) :: PairList

Returns a pair list with the same items as lst, but in reversed order. Reversing a list takes O(N) time.

> PairList.reverse(PairList[1, 4, 8])
PairList[8, 4, 1]
> PairList[1, 4, 8].reverse()
PairList[8, 4, 1]

function

fun PairList.append(lst :: PairList, ...) :: PairList

Appends the lsts in order. See also ++. Appending takes O(N) time.

> PairList.append(PairList[1, 2, 3], PairList[4, 5], PairList[6])
PairList[1, 2, 3, 4, 5, 6]
> PairList[1, 2, 3].append(PairList[4, 5], PairList[6])
PairList[1, 2, 3, 4, 5, 6]

function

fun PairList.take(lst :: PairList, n :: NonnegInt) :: PairList

function

fun PairList.take_last(lst :: PairList, n :: NonnegInt) :: PairList

Like List.take and List.take_last, but for pair lists. Producing the result list takes O(N) time, where N is the n argument for taking from the left or the length of the pair list for taking from the right.

> PairList[1, 2, 3, 4, 5].take(2)
PairList[1, 2]
> PairList[1, 2, 3, 4, 5].take_last(2)
PairList[4, 5]
> PairList[1].take(2)
PairList.take: list is shorter than the number of elements to take
list length: 1
number to take: 2

function

fun PairList.drop(lst :: PairList, n :: NonnegInt) :: PairList

function

fun PairList.drop_last(lst :: PairList, n :: NonnegInt) :: PairList

Like List.drop and List.drop_last, but for pair lists. Producing the result list takes O(N) time, where N is the n argument for dropping from the left or the length of the pair list for dropping from the right.

> PairList[1, 2, 3, 4, 5].drop(2)
PairList[3, 4, 5]
> PairList[1, 2, 3, 4, 5].drop_last(2)
PairList[1, 2, 3]
> PairList[1].drop(2)
PairList.drop: list is shorter than the number of elements to drop
list length: 1
number to drop: 2

function

fun PairList.has_element(lst :: PairList, v :: Any,

eqls :: Function.of_arity(2) = fun (x, y): x == y)

:: Boolean

Returns #true if lst has an element equal to v, #false otherwise, where eqls determines equality. Searching the list takes O(N) time (multiplified by the cost of eqls) to find an element as position N.

> PairList[1, 2, 3].has_element(2)
#true
> PairList[1, 2, 3].has_element(200)
#false

function

fun PairList.find(lst :: PairList, pred :: Function.of_arity(1)) :: Any

Returns the first element of lst for which pred return true, #false otherwise. Searching the list takes O(N) time (multiplied by the cost of pred) to find an element as position N.

> PairList[1, 2, 3].find(fun (x): x mod 2 .= 0)
2
> PairList[1, 2, 3].find(fun (x): x mod 10 .= 9)
#false

function

fun PairList.remove(lst :: PairList, v :: Any) :: PairList

Returns a pair list like lst, but with the first element equal to v (if any) removed. Searching the pair list takes O(N) time.

> [1, 2, 3, 2].remove(2)
[1, 3, 2]

function

fun PairList.map(lst :: PairList, f :: Function.of_arity(1))

:: PairList

function

fun PairList.for_each(lst :: PairList, f :: Function.of_arity(1))

:: Void

Like Function.map and Function.for_each, but with a single pair list of arguments first, with the function supplied second.

> PairList.map(PairList[1, 2, 3], fun (x): x + 1)
PairList[2, 3, 4]
> PairList[1, 2, 3].map(fun (x): x + 1)
PairList[2, 3, 4]
> PairList[1, 2, 3].for_each(println)
1
2
3

function

fun PairList.sort(lst :: PairList,

is_less :: Function.of_arity(2) = math.less)

:: PairList

Sorts lst using is_less to compare elements. Sorting takes O(N log N) time.

> PairList.sort(PairList[1, 3, 2])
PairList[1, 2, 3]
> PairList.sort(PairList[1, 3, 2], math.greater)
PairList[3, 2, 1]

function

fun PairList.iota(n :: NonnegInt) :: PairList.of(NonnegInt)

Returns a pair list containing the integers 0 to n (exclusive) in order.

> PairList.iota(3)
PairList[0, 1, 2]
> PairList.iota(0)
PairList[]

function

fun PairList.to_list(lst :: PairList) :: List

Implements Listable by returning a list with the same elements as lst in the same order. The conversion takes O(N) time.

function

fun PairList.to_sequence(lst :: PairList) :: Sequence

Implements Sequenceable by returning a sequence of lst’s elements in order.

1	Rhombus Essentials
2	Collections and Iteration
3	Syntax Objects and Macros
4	Classes and Interfaces
5	Static Information and Binding
6	Core Reference
7	Meta and Macros Reference
8	Rhombus Static by Default
9	Libraries
10	Naming Conventions

6.1	General Forms
6.2	Definitions
6.3	Namespaces
6.4	Import
6.5	Export
6.6	Functions
6.7	Operators
6.8	Classes and Interfaces
6.9	Veneers
6.10	Mutable Variables and Assignment
6.11	Repetitions
6.12	Block
6.13	Conditionals
6.14	Matching
6.15	Iteration
6.16	Recursion
6.17	Context Parameters
6.18	Exceptions
6.19	Continuations
6.20	Implicit Forms
6.21	Static and Dynamic Lookup
6.22	Modules and Submodules
6.23	Booleans
6.24	Numbers
6.25	Characters
6.26	Strings
6.27	Keywords
6.28	Symbols
6.29	Byte Strings
6.30	Lists
6.31	Pairs and Pair Lists
6.32	Mutable Lists
6.33	Arrays
6.34	Maps
6.35	Sets
6.36	Boxes
6.37	Indexables
6.38	Listables
6.39	Sequences
6.40	Appendables
6.41	Comparables
6.42	Paths
6.43	Source Locations
6.44	Void
6.45	Equality
6.46	Dot
6.47	Multiple Values
6.48	Annotations
6.49	Enumerations
6.50	Input and Output
6.51	Eval
6.52	Syntax Objects
6.53	Syntax Classes
6.54	Simple Expression Macros
6.55	Unit Testing

lst.length()	is	PairList.length(lst)
lst.get(n)	is	PairList.get(lst, n)
lst.first	is	PairList.first(lst)
lst.last	is	PairList.last(lst)
lst.rest	is	PairList.rest(lst)
lst.reverse()	is	PairList.reverse(lst)
lst.append(lst2, ...)	is	PairList.append(lst, lst2, ...)
lst.take(n)	is	PairList.take(lst, n)
lst.take_last(n)	is	PairList.take_last(lst, n)
lst.drop(n)	is	PairList.drop(lst, n)
lst.drop_last(n)	is	PairList.drop_last(lst, n)
lst.has_element(v, eqls, ...)	is	PairList.has_element(lst, v, eqls, ...)
lst.find(pred)	is	PairList.find(lst, pred)
lst.remove(v)	is	PairList.remove(lst, v)
lst.map(func)	is	PairList.map(lst, func)
lst.for_each(func)	is	PairList.for_each(lst, func)
lst.sort(arg, ...)	is	PairList.sort(lst, arg, ...)
lst.to_list()	is	PairList.to_list(lst)
lst.to_sequence()	is	PairList.to_sequence(lst)