mathlib3 documentation

testing.slim_check.functions

slim_check: generators for functions #

THIS FILE IS SYNCHRONIZED WITH MATHLIB4. Any changes to this file require a corresponding PR to mathlib4.

This file defines sampleable instances for α → β functions and ℤ → ℤ injective functions.

Functions are generated by creating a list of pairs and one more value using the list as a lookup table and resorting to the additional value when a value is not found in the table.

Injective functions are generated by creating a list of numbers and a permutation of that list. The permutation insures that every input is mapped to a unique output. When an input is not found in the list the input itself is used as an output.

Injective functions f : α → α could be generated easily instead of ℤ → ℤ by generating a list α, removing duplicates and creating a permutations. One has to be careful when generating the domain to make if vast enough that, when generating arguments to apply f to, they argument should be likely to lie in the domain of f. This is the reason that injective functions f : ℤ → ℤ are generated by fixing the domain to the range [-2*size .. -2*size], with size the size parameter of the gen monad.

Much of the machinery provided in this file is applicable to generate injective functions of type α → α and new instances should be easy to define.

Other classes of functions such as monotone functions can generated using similar techniques. For monotone functions, generating two lists, sorting them and matching them should suffice, with appropriate default values. Some care must be taken for shrinking such functions to make sure their defining property is invariant through shrinking. Injective functions are an example of how complicated it can get.

source
inductive slim_check.total_function (α : Type u) (β : Type v) :
Type (max u v)

Data structure specifying a total function using a list of pairs and a default value returned when the input is not in the domain of the partial function.

with_default f y encodes x ↦ f x when x ∈ f and x ↦ y otherwise.

We use Σ to encode mappings instead of × because we rely on the association list API defined in data.list.sigma.

Instances for slim_check.total_function
source
@[protected, instance]
def slim_check.total_function.inhabited {α : Type u} {β : Type v} [inhabited β] :
inhabited (slim_check.total_function α β)
Equations
source
def slim_check.total_function.apply {α : Type u} {β : Type v} [decidable_eq α] :
slim_check.total_function α β → α → β

Apply a total function to an argument.

Equations
source
def slim_check.total_function.repr_aux {α : Type u} {β : Type v} [has_repr α] [has_repr β] (m : list (Σ (_x : α), β)) :
string

Implementation of has_repr (total_function α β).

Creates a string for a given finmap and output, x₀ ↦ y₀, .. xₙ ↦ yₙ for each of the entries. The brackets are provided by the calling function.

Equations
source
@[protected]
def slim_check.total_function.repr {α : Type u} {β : Type v} [has_repr α] [has_repr β] :
slim_check.total_function α β → string

Produce a string for a given total_function. The output is of the form [x₀ ↦ f x₀, .. xₙ ↦ f xₙ, _ ↦ y].

Equations
source
@[protected, instance]
def slim_check.total_function.has_repr (α : Type u) (β : Type v) [has_repr α] [has_repr β] :
has_repr (slim_check.total_function α β)
Equations
source
def slim_check.total_function.list.to_finmap' {α : Type u} {β : Type v} (xs : list (α × β)) :
list (Σ (_x : α), β)

Create a finmap from a list of pairs.

Equations
source
def slim_check.total_function.total.sizeof {α : Type u} {β : Type v} [slim_check.sampleable α] [slim_check.sampleable β] :
slim_check.total_function α β → ℕ

Redefine sizeof to follow the structure of sampleable instances.

Equations
source
@[protected, instance]
def slim_check.total_function.has_sizeof {α : Type u} {β : Type v} [slim_check.sampleable α] [slim_check.sampleable β] :
has_sizeof (slim_check.total_function α β)
Equations
source
@[protected]
def slim_check.total_function.shrink {α : Type u} {β : Type v} [slim_check.sampleable α] [slim_check.sampleable β] [decidable_eq α] :
slim_check.shrink_fn (slim_check.total_function α β)

Shrink a total function by shrinking the lists that represent it.

Equations
source
@[protected, instance]
def slim_check.total_function.pi.sampleable_ext {α : Type u} {β : Type v} [slim_check.sampleable α] [slim_check.sampleable β] [decidable_eq α] [has_repr α] [has_repr β] :
slim_check.sampleable_ext (α → β)
Equations
source
@[simp]
def slim_check.total_function.zero_default {α : Type u} {β : Type v} [has_zero β] :
slim_check.total_function α β → slim_check.total_function α β

Map a total_function to one whose default value is zero so that it represents a finsupp.

Equations
source
@[simp]
def slim_check.total_function.zero_default_supp {α : Type u} {β : Type v} [has_zero β] [decidable_eq α] [decidable_eq β] :
slim_check.total_function α β → finset α

The support of a zero default total_function.

Equations
source
def slim_check.total_function.apply_finsupp {α : Type u} {β : Type v} [has_zero β] [decidable_eq α] [decidable_eq β] (tf : slim_check.total_function α β) :
α →₀ β

Create a finitely supported function from a total function by taking the default value to zero.

Equations
source
@[protected, instance]
def slim_check.total_function.finsupp.sampleable_ext {α : Type u} {β : Type v} [has_zero β] [decidable_eq α] [decidable_eq β] [slim_check.sampleable α] [slim_check.sampleable β] [has_repr α] [has_repr β] :
slim_check.sampleable_ext (α →₀ β)
Equations
source
@[protected, instance]
def slim_check.total_function.dfinsupp.sampleable_ext {α : Type u} {β : Type v} [has_zero β] [decidable_eq α] [decidable_eq β] [slim_check.sampleable α] [slim_check.sampleable β] [has_repr α] [has_repr β] :
slim_check.sampleable_ext (Π₀ (a : α), β)
Equations
source
@[protected, instance]
def slim_check.total_function.pi_pred.sampleable_ext {α : Type u} [slim_check.sampleable_ext (α → bool)] :
slim_check.sampleable_ext (α → Prop)
Equations
source
@[protected, instance]
def slim_check.total_function.pi_uncurry.sampleable_ext {α : Type u} {β : Type v} {γ : Sort w} [slim_check.sampleable_ext (α × β → γ)] :
slim_check.sampleable_ext (α → β → γ)
Equations
source
inductive slim_check.injective_function (α : Type u) :
Type u

Data structure specifying a total function using a list of pairs and a default value returned when the input is not in the domain of the partial function.

map_to_self f encodes x ↦ f x when x ∈ f and x ↦ x, i.e. x to itself, otherwise.

We use Σ to encode mappings instead of × because we rely on the association list API defined in data.list.sigma.

Instances for slim_check.injective_function
source
@[protected, instance]
def slim_check.injective_function.inhabited {α : Type u} :
inhabited (slim_check.injective_function α)
Equations
source
def slim_check.injective_function.apply {α : Type u} [decidable_eq α] :
slim_check.injective_function α → α → α

Apply a total function to an argument.

Equations
source
@[protected]
def slim_check.injective_function.repr {α : Type u} [has_repr α] :
slim_check.injective_function α → string

Produce a string for a given total_function. The output is of the form [x₀ ↦ f x₀, .. xₙ ↦ f xₙ, x ↦ x]. Unlike for total_function, the default value is not a constant but the identity function.

Equations
source
@[protected, instance]
def slim_check.injective_function.has_repr (α : Type u) [has_repr α] :
has_repr (slim_check.injective_function α)
Equations
source
def slim_check.injective_function.list.apply_id {α : Type u} [decidable_eq α] (xs : list (α × α)) (x : α) :
α

Interpret a list of pairs as a total function, defaulting to the identity function when no entries are found for a given function

Equations
source
@[simp]
theorem slim_check.injective_function.list.apply_id_cons {α : Type u} [decidable_eq α] (xs : list (α × α)) (x y z : α) :
slim_check.injective_function.list.apply_id ((y, z) :: xs) x = ite (y = x) z (slim_check.injective_function.list.apply_id xs x)
source
theorem slim_check.injective_function.list.apply_id_zip_eq {α : Type u} [decidable_eq α] {xs ys : list α} (h₀ : xs.nodup) (h₁ : xs.length = ys.length) (x y : α) (i : ℕ) (h₂ : xs.nth i = option.some x) :
slim_check.injective_function.list.apply_id (xs.zip ys) x = y ↔ ys.nth i = option.some y
source
theorem slim_check.injective_function.apply_id_mem_iff {α : Type u} [decidable_eq α] {xs ys : list α} (h₀ : xs.nodup) (h₁ : xs ~ ys) (x : α) :
slim_check.injective_function.list.apply_id (xs.zip ys) x ∈ ys ↔ x ∈ xs
source
theorem slim_check.injective_function.list.apply_id_eq_self {α : Type u} [decidable_eq α] {xs ys : list α} (x : α) :
x ∉ xs → slim_check.injective_function.list.apply_id (xs.zip ys) x = x
source
theorem slim_check.injective_function.apply_id_injective {α : Type u} [decidable_eq α] {xs ys : list α} (h₀ : xs.nodup) (h₁ : xs ~ ys) :
function.injective (slim_check.injective_function.list.apply_id (xs.zip ys))
source
def slim_check.injective_function.perm.slice {α : Type u} [decidable_eq α] (n m : ℕ) :
(Σ' (xs ys : list α), xs ~ ys ∧ ys.nodup) → (Σ' (xs ys : list α), xs ~ ys ∧ ys.nodup)

Remove a slice of length m at index n in a list and a permutation, maintaining the property that it is a permutation.

Equations
source
def slim_check.injective_function.slice_sizes  :
ℕ → lazy_list ℕ+

A lazy list, in decreasing order, of sizes that should be sliced off a list of length n

Equations
source
@[protected]
def slim_check.injective_function.shrink_perm {α : Type} [decidable_eq α] [has_sizeof α] :
slim_check.shrink_fn (Σ' (xs ys : list α), xs ~ ys ∧ ys.nodup)

Shrink a permutation of a list, slicing a segment in the middle.

The sizes of the slice being removed start at n (with n the length of the list) and then n / 2, then n / 4, etc down to 1. The slices will be taken at index 0, n / k, 2n / k, 3n / k, etc.

Equations
source
@[protected, instance]
def slim_check.injective_function.has_sizeof {α : Type u} [has_sizeof α] :
has_sizeof (slim_check.injective_function α)
Equations
source
@[protected]
def slim_check.injective_function.shrink {α : Type} [has_sizeof α] [decidable_eq α] :
slim_check.shrink_fn (slim_check.injective_function α)

Shrink an injective function slicing a segment in the middle of the domain and removing the corresponding elements in the codomain, hence maintaining the property that one is a permutation of the other.

Equations
source
@[protected]
def slim_check.injective_function.mk {α : Type u} (xs ys : list α) (h : xs ~ ys) (h' : ys.nodup) :
slim_check.injective_function α

Create an injective function from one list and a permutation of that list.

Equations
source
@[protected]
theorem slim_check.injective_function.injective {α : Type u} [decidable_eq α] (f : slim_check.injective_function α) :
function.injective f.apply
source
@[protected, instance]
def slim_check.injective_function.pi_injective.sampleable_ext  :
slim_check.sampleable_ext {f // function.injective f}
Equations
source
@[protected, instance]
def slim_check.injective.testable {α : Type u} {β : Type v} (f : α → β) [I : slim_check.testable (slim_check.named_binder "x" (∀ (x : α), slim_check.named_binder "y" (∀ (y : α), slim_check.named_binder "H" (f x = f y → x = y))))] :
slim_check.testable (function.injective f)
Equations
source
@[protected, instance]
def slim_check.monotone.testable {α : Type u} {β : Type v} [preorder α] [preorder β] (f : α → β) [I : slim_check.testable (slim_check.named_binder "x" (∀ (x : α), slim_check.named_binder "y" (∀ (y : α), slim_check.named_binder "H" (x ≤ y → f x ≤ f y))))] :
slim_check.testable (monotone f)
Equations
source
@[protected, instance]
def slim_check.antitone.testable {α : Type u} {β : Type v} [preorder α] [preorder β] (f : α → β) [I : slim_check.testable (slim_check.named_binder "x" (∀ (x : α), slim_check.named_binder "y" (∀ (y : α), slim_check.named_binder "H" (x ≤ y → f y ≤ f x))))] :
slim_check.testable (antitone f)
Equations