8.2 Pairs and Pair Lists

8.15.0.12

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.

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

property

property (pr :: Pair).first

property

property (pr :: Pair).rest

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

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

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

property

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

property

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

property

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

method

method (lst :: PairList).length() :: 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

method

method (lst :: PairList).reverse() :: 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]

method

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

function

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

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 :: NonnegInt) :: PairList

method

method (lst :: PairList).take_last(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

method

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

method

method (lst :: PairList).drop_last(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

method

method (lst :: PairList).has_element(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 as position N.

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

method

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

:: Any

method

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

:: maybe(NonnegInt)

Like List.find and List.find , but for pair lists. 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((_ mod 2 .= 0))
2
> PairList[1, 2, 3].find((_ mod 10 .= 9))
#false
> PairList[1, 2, 3].index((_ mod 2 .= 0))
1
> PairList[1, 2, 3].index((_ mod 10 .= 9))
#false

method

method (lst :: PairList).remove(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]

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

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

) :: PairList

method

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

:: values(PairList, PairList)

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

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

method

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

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

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

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]

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	Runtime System
17	Meta and Macros

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