Equivalences involving List
-like types #
This file defines some additional constructive equivalences using Encodable
and the pairing
function on ℕ
.
If α
is encodable, then so is List α
. This uses the pair
and unpair
functions from
Data.Nat.Pairing
.
Equations
- List.encodable = { encode := Encodable.encodeList, decode := Encodable.decodeList, encodek := ⋯ }
Explicit encoding function for Multiset α
Instances For
Explicit decoding function for Multiset α
Instances For
If α
is encodable, then so is Multiset α
.
Equations
- Multiset.encodable = { encode := Encodable.encodeMultiset, decode := Encodable.decodeMultiset, encodek := ⋯ }
A listable type with decidable equality is encodable.
Equations
- Encodable.encodableOfList l H = { encode := fun (a : α) => List.idxOf a l, decode := l.get?, encodek := ⋯ }
Instances For
A finite type is encodable. Because the encoding is not unique, we wrap it in Trunc
to
preserve computability.
Equations
- One or more equations did not get rendered due to their size.
Instances For
A noncomputable way to arbitrarily choose an ordering on a finite type.
It is not made into a global instance, since it involves an arbitrary choice.
This can be locally made into an instance with attribute [local instance] Fintype.toEncodable
.
Instances For
If α
is encodable, then so is Vector α n
.
If α
is countable, then so is Vector α n
.
If α
is encodable, then so is Fin n → α
.
Equations
Equations
- Encodable.finPi n π = Encodable.ofEquiv { f : Fin n → (i : Fin n) × π i // ∀ (i : Fin n), (f i).fst = i } (Equiv.piEquivSubtypeSigma (Fin n) π)
When α
is finite and β
is encodable, α → β
is encodable too. Because the encoding is not
unique, we wrap it in Trunc
to preserve computability.
Equations
Instances For
When α
is finite and all π a
are encodable, Π a, π a
is encodable too. Because the
encoding is not unique, we wrap it in Trunc
to preserve computability.
Equations
- One or more equations did not get rendered due to their size.
Instances For
If α
is denumerable, then so is List α
.
Equations
Outputs the list of differences of the input list, that is
lower [a₁, a₂, ...] n = [a₁ - n, a₂ - a₁, ...]
Equations
Instances For
Outputs the list of partial sums of the input list, that is
raise [a₁, a₂, ...] n = [n + a₁, n + a₁ + a₂, ...]
Equations
Instances For
If α
is denumerable, then so is Multiset α
. Warning: this is not the same encoding as used
in Multiset.encodable
.
Equations
- One or more equations did not get rendered due to their size.
Outputs the list of differences minus one of the input list, that is
lower' [a₁, a₂, a₃, ...] n = [a₁ - n, a₂ - a₁ - 1, a₃ - a₂ - 1, ...]
.
Equations
Instances For
Outputs the list of partial sums plus one of the input list, that is
raise [a₁, a₂, a₃, ...] n = [n + a₁, n + a₁ + a₂ + 1, n + a₁ + a₂ + a₃ + 2, ...]
. Adding one each
time ensures the elements are distinct.
Equations
Instances For
Makes raise' l n
into a finset. Elements are distinct thanks to raise'_sorted
.
Instances For
If α
is denumerable, then so is Finset α
. Warning: this is not the same encoding as used
in Finset.encodable
.
Equations
- One or more equations did not get rendered due to their size.
The type lists on unit is canonically equivalent to the natural numbers.
Equations
- Equiv.listUnitEquiv = { toFun := List.length, invFun := fun (n : ℕ) => List.replicate n (), left_inv := Equiv.listUnitEquiv.proof_1, right_inv := ⋯ }