syntaxRange Syntax
该范围为左闭、右开,表示Std.Rco:
term ::= ...
| `a...b` is the range of elements greater than or equal to `a` and less than `b`.
See also `Std.Rco`.
term...term
该范围为左闭、右开,表示Std.Rco:
term ::= ...
| `a...<b` is the range of elements greater than or equal to `a` and less than `b`.
See also `Std.Rco`.
term...<term
该范围为左闭、右闭,表示Std.Rcc:
term ::= ...
| `a...=b` is the range of elements greater than or equal to `a` and less than or equal to
`b`. See also `Std.Rcc`.
term...=term
该范围是左闭右无限,表示 Std.Rci:
term ::= ...
| `a...*` is the range of elements greater than or equal to `a`. See also `Std.Rci`. term...*
该范围有左开、右开,表示Std.Roo:
term ::= ...
| `a<...b` is the range of elements greater than `a` and less than `b`.
See also `Std.Roo`.
term<...term
该范围有左开、右开,表示Std.Roo:
term ::= ...
| `a<...<b` is the range of elements greater than `a` and less than `b`.
See also `Std.Roo`.
term<...<term
该范围为左开、右闭,表示Std.Roc:
term ::= ...
| `a<...=b` is the range of elements greater than `a` and less than or equal to `b`.
See also `Std.Roc`.
term<...=term
该范围为左开、右无限,表示 Std.Roi:
term ::= ...
| `a<...*` is the range of elements greater than `a`. See also `Std.Roi`. term<...*
该范围为左无穷、右开,表示 Std.Rio:
term ::= ...
| `*...b` is the range of elements less than `b`. See also `Std.Rio`. *...term
该范围为左无穷、右开,表示 Std.Ric:
term ::= ...
| `*...<b` is the range of elements less than `b`. See also `Std.Rio`. *...<term
该范围是左无穷、右闭的,表示 Std.Ric:
term ::= ...
| `*...=b` is the range of elements less than or equal to `b`. See also `Std.Ric`. *...=term
该范围两边都是无穷大,表示 Std.Rii:
term ::= ...
| `*...*` is the range that is unbounded in both directions. See also `Std.Rii`. *...*
20.18.1. 范围类型🔗
🔗structure
A range of elements of α with a closed lower bound and an open upper bound.
a...b or a...<b is the range of all values greater than or equal to a : α and
less than b : α. This is notation for Rco.mk a b.
Constructor
Fields
lower : α
The lower bound of the range. lower is included in the range.
upper : α
The upper bound of the range. upper is not included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given left-closed right-open range as an array in ascending order.
🔗def
Returns the elements of the given left-closed right-open range as a list in ascending order.
🔗def
Returns the number of elements contained in the given left-closed right-open range.
🔗def
Checks whether the range contains any value.
This function returns a meaningful value given LawfulUpwardEnumerable and
LawfulUpwardEnumerableLT instances.
🔗structure
A range of elements of α with closed lower and upper bounds.
a...=b is the range of all values greater than or equal to a : α and less than or
equal to b : α. This is notation for Rcc.mk a b.
Constructor
Fields
lower : α
The lower bound of the range. lower is included in the range.
upper : α
The upper bound of the range. upper is included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given closed range as an array in ascending order.
🔗def
Returns the elements of the given closed range as a list in ascending order.
🔗def
Returns the number of elements contained in the given closed range.
🔗def
Checks whether the range contains any value.
This function returns a meaningful value given LawfulUpwardEnumerable and
LawfulUpwardEnumerableLE instances.
🔗structure
An upward-unbounded range of elements of α with a closed lower bound.
a...* is the range of all values greater than or equal to a : α.
This is notation for Rci.mk a.
Constructor
Fields
lower : α
The lower bound of the range. lower is included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given left-closed right-unbounded range as an array in ascending order.
🔗def
Returns the elements of the given left-closed right-unbounded range as a list in ascending order.
🔗def
Returns the number of elements contained in the given left-closed right-unbounded range.
🔗def
Checks whether the range contains any value.
This function exists for completeness and always returns false:
The closed lower bound is contained in the range, so
left-closed right-unbounded ranges are never empty.
🔗structure
A range of elements of α with an open lower and upper bounds.
a<...b or a<...<b is the range of all values greater than a : α and less than
b : α. This is notation for Roo.mk a b.
Constructor
Fields
lower : α
The lower bound of the range. lower is not included in the range.
upper : α
The upper bound of the range. upper is not included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given open range as an array in ascending order.
🔗def
Returns the elements of the given open range as a list in ascending order.
🔗def
Returns the number of elements contained in the given open range.
🔗def
Checks whether the range contains any value.
This function returns a meaningful value given LawfulUpwardEnumerable and
LawfulUpwardEnumerableLT instances.
🔗structure
A range of elements of α with an open lower bound and a closed upper bound.
a<...=b is the range of all values greater than a : α and less than or equal to
b : α. This is notation for Roc.mk a b.
Constructor
Fields
lower : α
The lower bound of the range. lower is not included in the range.
upper : α
The upper bound of the range. upper is included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given left-open right-closed range as an array in ascending order.
🔗def
Returns the elements of the given left-open right-closed range as a list in ascending order.
🔗def
Returns the number of elements contained in the given left-open right-closed range.
🔗def
Checks whether the range contains any value.
This function returns a meaningful value given LawfulUpwardEnumerable and
LawfulUpwardEnumerableLT instances.
🔗structure
An upward-unbounded range of elements of α with an open lower bound.
a<...* is the range of all values greater than a : α.
This is notation for Roi.mk a.
Constructor
Fields
lower : α
The lower bound of the range. lower is not included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given left-open right-unbounded range as an array in ascending order.
🔗def
Returns the elements of the given left-open right-unbounded range as a list in ascending order.
🔗def
Returns the number of elements contained in the given left-open right-unbounded range.
🔗def
Checks whether the range contains any value.
This function returns a meaningful value given a LawfulUpwardEnumerable instance.
🔗structure
A downward-unbounded range of elements of α with an open upper bound.
*...b or *...<b is the range of all values less than b : α.
This is notation for Rio.mk b.
Constructor
Fields
upper : α
The upper bound of the range. upper is not included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given closed range as an array in ascending order.
🔗def
Returns the elements of the given closed range as a list in ascending order.
🔗def
Returns the number of elements contained in the given closed range.
🔗def
Checks whether the range contains any value.
This function returns a meaningful value given LawfulUpwardEnumerable,
LawfulUpwardEnumerableLT and LawfulUpwardEnumerableLeast? instances.
🔗structure
A downward-unbounded range of elements of α with a closed upper bound.
*...=b is the range of all values less than or equal to b : α.
This is notation for Ric.mk b.
Constructor
Fields
upper : α
The upper bound of the range. upper is included in the range.
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given closed range as an array in ascending order.
🔗def
Returns the elements of the given closed range as a list in ascending order.
🔗def
Returns the number of elements contained in the given closed range.
🔗def
Checks whether the range contains any value.
This function exists for completeness and always returns false:
The closed upper bound is contained in the range, so
left-unbounded right-closed ranges are never empty.
🔗structure
A full range of all elements of α. Its only inhabitant is the range *...*, which is
notation for Rii.mk.
Constructor
🔗def
Returns an iterator over the given range. This iterator will emit the elements of the range
in increasing order.
🔗def
Returns the elements of the given full range as an array in ascending order.
🔗def
Returns the elements of the given full range as a list in ascending order.
🔗def
Returns the number of elements contained in the full range.
🔗def
Checks whether the range contains any value.
This function returns a meaningful value given LawfulUpwardEnumerable and
LawfulUpwardEnumerableLeast? instances.
20.18.2. 范围相关的 Type 类🔗
🔗type class
This typeclass provides the function succ? : α → Option α that computes the successor of
elements of α, or none if no successor exists.
It also provides the function succMany?, which computes n-th successors.
succ? is expected to be acyclic: No element is its own transitive successor.
If α is ordered, then every element larger than a : α should be a transitive successor of a.
These properties and the compatibility of succ? with succMany? are encoded in the typeclasses
LawfulUpwardEnumerable, LawfulUpwardEnumerableLE and LawfulUpwardEnumerableLT.
Instance Constructor
Methods
succ? : α → Option α
Maps elements of α to their successor, or none if no successor exists.
succMany? : Nat → α → Option α
Maps elements of α to their n-th successor, or none if no successor exists.
This should semantically behave like repeatedly applying succ?, but it might be more efficient.
LawfulUpwardEnumerable ensures the compatibility with succ?.
If no other implementation is provided in UpwardEnumerable instance, succMany? repeatedly
applies succ?.
🔗def
According to UpwardEnumerable.LE, a is less than or equal to b if b is a or a transitive
successor of a.
🔗def
According to UpwardEnumerable.LT, a is less than b if b is a proper transitive successor of
a. 'Proper' means that b is the n-th successor of a, where n > 0.
Given LawfulUpwardEnumerable α, no element of α is less than itself.
🔗type class
This typeclass ensures that an UpwardEnumerable α instance is well-behaved.
Instance Constructor
Methods
🔗type class
The typeclass Least? α optionally provides a smallest element of α, least? : Option α.
The main use case of this typeclass is to use it in combination with UpwardEnumerable to
obtain a (possibly infinite) ascending enumeration of all elements of α.
Instance Constructor
Methods
least? : Option α
Returns the smallest element of α, or none if α is empty.
Only empty types are allowed to define least? := none. If α is ordered and nonempty, then
the value of least? should be the smallest element according to the order on α.
🔗type class
This propositional typeclass ensures that UpwardEnumerable.succ? will never return none.
In other words, it ensures that there will always be a successor.
Instance Constructor
Methods
🔗type class
This propositional typeclass ensures that UpwardEnumerable.succ? is injective.
Instance Constructor
Methods
🔗type class
This type class ensures that right-unbounded ranges (i.e., for a bound a,
a...*, a<...* and *...*) are always finite.
This is a prerequisite for many functions and instances, such as
Rci.toList or ForIn'.
Instance Constructor
Methods
finite : ∀ (init : α), ∃ n, Std.PRange.succMany? n init = none
For every elements init, there exists a chain of successors that
results in an element that has no successors.
🔗type class
This typeclass provides support for the size function for ranges with closed lower bound
(Ric.size,
Rio.size and
Rii.size).
The returned size should be equal to the number of elements returned by toList. This
condition is captured by the typeclass
LawfulHasSize.
Instance Constructor
Methods
size : α → Nat
Returns the number of elements starting from lo that satisfy the given upper bound.
🔗type class
This type class ensures that right-closed ranges (i.e., for bounds a and b,
a...=b, a<...=b and *...=b) are always finite.
This is a prerequisite for many functions and instances, such as
Rcc.toList or ForIn'.
Instance Constructor
Methods
finite : ∀ (init hi : α), ∃ n, (Std.PRange.succMany? n init).elim True fun x => ¬x ≤ hi
For every pair of elements init and hi, there exists a chain of successors that
results in an element that either has no successors or is greater than hi.
🔗type class
This typeclass provides support for the size function for ranges with closed lower bound
(Rcc.size,
Rco.size and
Rci.size).
The returned size should be equal to the number of elements returned by toList. This
condition is captured by the typeclass
LawfulHasSize.
Instance Constructor
Methods
size : α → α → Nat
Returns the number of elements starting from lo that satisfy the given upper bound.
20.18.4. 范围和切片🔗
范围语法可与支持切片的数据结构一起使用以选择结构的切片。
Slicing Lists
列表可以使用任何间隔类型进行切片:
def groceries :=
["apples", "bananas", "coffee", "dates", "endive", "fennel"]
["bananas", "coffee", "dates"]#eval groceries[1...4] |>.toList
["bananas", "coffee", "dates"]
["bananas", "coffee", "dates", "endive"]#eval groceries[1...=4] |>.toList
["bananas", "coffee", "dates", "endive"]
["bananas", "coffee", "dates", "endive", "fennel"]#eval groceries[1...*] |>.toList
["bananas", "coffee", "dates", "endive", "fennel"]
["coffee", "dates"]#eval groceries[1<...4] |>.toList
["coffee", "dates"]
["coffee", "dates", "endive"]#eval groceries[1<...=4] |>.toList
["coffee", "dates", "endive"]
["apples", "bananas", "coffee", "dates", "endive"]#eval groceries[*...=4] |>.toList
["apples", "bananas", "coffee", "dates", "endive"]
["apples", "bananas", "coffee", "dates"]#eval groceries[*...4] |>.toList
["apples", "bananas", "coffee", "dates"]
["apples", "bananas", "coffee", "dates", "endive", "fennel"]#eval groceries[*...*] |>.toList
["apples", "bananas", "coffee", "dates", "endive", "fennel"]
Custom Slices
Triple 包含三个相同类型的值:
structure Triple (α : Type u) where
fst : α
snd : α
thd : α
deriving Repr
三元组中的位置可以是任何字段,或者紧接在 thd 之后:
inductive TriplePos where
| fst | snd | thd | done
deriving Repr
三元组的切片由三元组、起始位置和停止位置组成。
包含起始位置,不包含停止位置:
structure TripleSlice (α : Type u) where
triple : Triple α
start : TriplePos
stop : TriplePos
deriving Repr
通过实现每个支持的范围类型的 Sliceable 类的实例,TriplePos 的范围可用于从三元组中选择一个切片。
例如,Std.Rco.Sliceable 允许使用左闭、右开范围对 Triple 进行切片:
instance : Std.Rco.Sliceable (Triple α) TriplePos (TripleSlice α) where
mkSlice triple range :=
{ triple, start := range.lower, stop := range.upper }
def abc : Triple Char := ⟨'a', 'b', 'c'⟩
open TriplePos in
{ triple := { fst := 'a', snd := 'b', thd := 'c' }, start := TriplePos.snd, stop := TriplePos.thd }#eval abc[snd...thd]
{ triple := { fst := 'a', snd := 'b', thd := 'c' }, start := TriplePos.snd, stop := TriplePos.thd }
无限范围只有一个下界:
instance : Std.Rci.Sliceable (Triple α) TriplePos (TripleSlice α) where
mkSlice triple range :=
{ triple, start := range.lower, stop := .done }
open TriplePos in
{ triple := { fst := 'a', snd := 'b', thd := 'c' }, start := TriplePos.snd, stop := TriplePos.done }#eval abc[snd...*]
{ triple := { fst := 'a', snd := 'b', thd := 'c' }, start := TriplePos.snd, stop := TriplePos.done }
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being left-closed right-open.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Rco β → γ
Slices carrier from range.lower (inclusive) to range.upper (exclusive).
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being closed.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Rcc β → γ
Slices carrier from range.lower to range.upper, both inclusive.
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being left-closed right-unbounded.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Rci β → γ
Slices carrier from range.lower (inclusive).
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being open.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Roo β → γ
Slices carrier from range.lower to range.upper, both exclusive.
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being left-open right-closed.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Roc β → γ
Slices carrier from range.lower (exclusive) to range.upper (inclusive).
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being left-open right-unbounded.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Roi β → γ
Slices carrier from range.lower (exclusive).
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being left-unbounded right-open.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Rio β → γ
Slices carrier up to range.upper (exclusive).
🔗type class
This typeclass indicates how to obtain slices of elements of α over ranges in the index type
β, the ranges being left-unbounded right-closed.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Ric β → γ
Slices carrier up to range.upper (inclusive).
🔗type class
This typeclass indicates how to obtain slices of elements of α over the full range in the
index type β.
The type of the resulting slices is γ.
Instance Constructor
Methods
mkSlice : α → Std.Rii β → γ
Slices carrier with no bounds.