8.2 Pairs and Pair Lists

9.0.0.3

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

A pair list is indexable using […] to access a list element by position—in O(N) time—via #%index. A pair list also works with the ++ operator to append pair lists. A pair list supports membership tests using the in operator. A pair list can be used as sequence, in which case it supplies its elements in order.

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 :: Any, rst :: Any)

:: Pair.of(Any.like(fst), Any.like(rst))

Constructs a pair containing fst and rst.

> 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.of(Any.like(fst), Any.like(rst))

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 pair list as its second argument, which means that it always forms a pair list. In contrast, Pair.cons allows any value as its second argument—but it creates a pair list if that argument is a pair list.

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

property

property (pr :: Pair).first

:: Any.like_first(pr)

property

property (pr :: Pair).rest

:: Any.like_rest(pr)

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)

annotation

PairList.tuple_of[annot, ..., maybe_ellipsis]

maybe_ellipsis

ellipsis

...

The PairList annotation by itself matches any pair list. The PairList.of variant matches a pair list whose elements all satisfy annot.

The PairList.tuple_of annotation is analogous to the List.tuple_of annotation, but for pair lists.

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.of(Any.like(v))

expression

PairList[expr_or_splice, ...]

repetition

PairList[repet_or_splice, ...]

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.

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

binding operator

PairList[bind_or_splice, ...]

bind_or_splice

bind

splice

repet_bind , ellipsis

& pair_list_bind

& pair_list_repet_bind , ellipsis

ellipsis

...

... ~nonempty

... ~once

Matches a pair list with bind_or_splices in the same way that List matches lists.

> 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]

Unlike a List, a splice that does not impose a predicate or conversion on a matching value is constant-time only when the splice is at the end of the pattern. Matching N elements to a splice in the middle of a pair list takes at least O(N) time. Along those lines, when multiple splices are among the bind_or_splices, a splice using & pair_list_bind requires O(N) time to produce each N-length candidate match to pair_list_bind.

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.of(Any.like(elem) || Any.like_element(lst))

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.

method

method (lst :: PairList).get(n :: Nat)

:: Any.like_element(lst)

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"

property

property PairList.first(lst :: NonemptyPairList)

:: Any.like_element(lst)

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"

property

property PairList.last(lst :: NonemptyPairList)

:: Any.like_element(lst)

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"

property

property PairList.rest(lst :: NonemptyPairList)

:: PairList.of(Any.like_element(lst))

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"]

method

method (lst :: PairList).length() :: Nat

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

method

method (lst :: PairList).reverse()

:: PairList.of(Any.like_element(lst))

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]

method

method (lst :: PairList).append(lst2 :: PairList, ...)

:: PairList.of(Any.like_element(lst) || Any.like_element(lst2))

function

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

:: PairList.of(Any.like_element(lst))

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

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

method

method (lst :: PairList).take(n :: Nat)

:: PairList.of(Any.like_element(lst))

method

method (lst :: PairList).take_last(n :: Nat)

:: PairList.of(Any.like_element(lst))

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

method

method (lst :: PairList).drop(n :: Nat)

:: PairList.of(Any.like_element(lst))

method

method (lst :: PairList).drop_last(n :: Nat)

:: PairList.of(Any.like_element(lst))

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

method

method (lst :: PairList).contains(v :: Any,

eqls :: Function.of_arity(2) = (_ == _))

:: Boolean

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

> PairList[1, 2, 3].contains(2)
#true
> PairList[1, 2, 3].contains(200)
#false
> PairList[10, 20, 30].contains(20.0, (_ .= _))
#true
> 2 in PairList[1, 2, 3]
#true

method

method (lst :: PairList).index(v :: Any,

eqls :: Function.of_arity(2) = (_ == _))

:: maybe(Int)

Like PairList.contains, but instead of returning #true, returns the index of a found element.

> PairList["a", "b", "c"].index("b")
1
> PairList["a", "b", "c"].index("d")
#false
> PairList[10, 20, 30].index(20.0, (_ .= _))
1

method

method (lst :: PairList).find(pred :: Function.of_arity(1))

:: Any.like_element(lst)

method

method (lst :: PairList).find_index(pred :: Function.of_arity(1))

:: maybe(Nat)

Like List.find and List.index, but for pair lists. Searching the list takes O(N) time (multiplied by the cost of pred) to find an element at position N.

> PairList[1, 2, 3].find((_ mod 2 .= 0))
2
> PairList[1, 2, 3].find((_ mod 10 .= 9))
#false
> PairList[1, 2, 3].find_index((_ mod 2 .= 0))
1
> PairList[1, 2, 3].find_index((_ mod 10 .= 9))
#false

method

method (lst :: PairList).remove(v :: Any)

:: PairList.of(Any.like_element(lst))

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]

method

method (lst :: PairList).map(f :: Function.of_arity(1))

:: PairList

method

method (lst :: PairList).for_each(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], (_ + 1))
PairList[2, 3, 4]
> PairList[1, 2, 3].map((_ + 1))
PairList[2, 3, 4]
> PairList[1, 2, 3].for_each(println)
1
2
3

method

method (lst :: PairList).filter(

~keep: keep_pred :: Function.of_arity(1)

= fun (_): #true,

~skip: skip_pred :: Function.of_arity(1)

= fun (_): #false,

) :: PairList.of(Any.like_element(lst))

method

method (lst :: PairList).partition(pred :: Function.of_arity(1))

:: values(PairList.of(Any.like_element(lst)),

PairList.of(Any.like_element(lst)))

List List.filter and List.partition, but for pair lists.

> PairList[1, -1, -2, 2].filter(~keep: (_ > 0))
PairList[1, 2]
> PairList[1, -1, -2, 2].filter(~skip: (_ > 0))
PairList[-1, -2]
> PairList[1, -1, -2, 2].filter(~keep: (_ != -2), ~skip: (_ > 0))
PairList[-1]
> PairList[1, -1, -2, 2].partition((_ > 0))
PairList[1, 2]
PairList[-1, -2]

method

method (lst :: PairList).sort(is_less :: Function.of_arity(2) = (_ < _))

:: PairList.of(Any.like_element(lst))

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], (_ > _))
PairList[3, 2, 1]

function

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

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

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

method

method (lst :: PairList).to_list()

:: List.of(Any.like_element(lst))

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

method

method (lst :: PairList).to_sequence()

:: Sequence.expect_of(Any.like_element(lst))

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

1	Notation and Conventions
2	Implicits and Context
3	Names and Definitions
4	Functions and Operators
5	Comparison and Branching
6	Objects and Annotations
7	Basic Data
8	Collections and Iteration
9	Object Protocols
10	Higher-Order Control
11	Code as Data
12	String Formatting and Matching
13	Input and Output
14	Operating System
15	Threads and Concurrency
16	Reflection and Security
17	Runtime System

8.1	Lists
8.2	Pairs and Pair Lists
8.3	Mutable Lists
8.4	Arrays
8.5	Maps
8.6	Sets
8.7	Repetitions
8.8	Iteration
8.9	Ranges