Struct FiniteFunction

pub struct FiniteFunction<K: ArrayKind> {
    pub table: K::Index,
    pub target: K::I,
}

A finite function is an array of indices in a range {0..N} for some N ∈ Nat

Fields

table: K::Index

target: K::I

Implementations

impl<K: ArrayKind> FiniteFunction<K>

pub fn new(table: K::Index, target: K::I) -> Option<FiniteFunction<K>>

Construct a FiniteFunction from a table of indices

pub fn terminal(a: K::I) -> Self

The length-a array of zeroes !_a : a → 1. TODO: doctest

pub fn constant(a: K::I, x: K::I, b: K::I) -> Self

Construct the constant finite function f : a → x + 1 + b, an array of length a mapping all elements to x.

Note that the target of the finite function must be at least x+1 to be valid. This is equivalent to !_a ; ι₁ ; ι₀, where

• !_a : a → 1 is the terminal map
• ι₁ : 1 → x+1 and ι₀ : x+1 → x+1+b are injections.

let (x, a, b) = (2, 3, 2);

let actual = FiniteFunction::<VecKind>::constant(a, x, b);
let expected = FiniteFunction::new(VecArray(vec![2, 2, 2]), x + b + 1).unwrap();
assert_eq!(actual, expected);

// Check equal to `!_a ; ι₁ ; ι₀`
let i1 = FiniteFunction::<VecKind>::inj1(x, 1);
let i0 = FiniteFunction::inj0(x + 1, b);
let f  = FiniteFunction::terminal(a);
let h  = f.compose(&i1).expect("b").compose(&i0).expect("c");
assert_eq!(actual, h);

pub fn inject0(&self, b: K::I) -> FiniteFunction<K>

Directly construct f ; ι₀ instead of computing by composition.

assert_eq!(Some(f.inject0(b)), &f >> &i0);

pub fn inject1(&self, a: K::I) -> FiniteFunction<K>

Directly construct f ; ι₁ instead of computing by composition.

assert_eq!(Some(f.inject1(a)), &f >> &i1);

pub fn to_initial(&self) -> FiniteFunction<K>

Given a finite function f : A → B, return the initial map initial : 0 → B.

pub fn coequalizer(&self, other: &Self) -> Option<FiniteFunction<K>>

pub fn coequalizer_universal(&self, f: &Self) -> Option<Self>

where K::Type<K::I>: Array<K, K::I> + PartialEq,

pub fn transpose(a: K::I, b: K::I) -> FiniteFunction<K>

transpose(a, b) is the “transposition permutation” for an a → b matrix stored in row-major order.

Let M be an a*b-dimensional input thought of as a matrix in row-major order – having b rows and a columns. Then transpose(a, b) computes the “target indices” of the transpose. So for matrices M : a → b and N : b → a, setting the indices N[transpose(a, b)] = M is the same as writing N = M.T.

pub fn injections(&self, a: &FiniteFunction<K>) -> Option<Self>

Given a finite function s : N → K representing the objects of the finite coproduct Σ_{n ∈ N} s(n) whose injections have the type ι_x : s(x) → Σ_{n ∈ N} s(n), and given a finite map a : A → N, compute the coproduct of injections

injections(s, a) : Σ_{x ∈ A} s(x) → Σ_{n ∈ N} s(n)
injections(s, a) = Σ_{x ∈ A} ι_a(x)

So that injections(s, id) == id

Note that when a is a permutation, injections(s, a) is a “blockwise” version of that permutation with block sizes equal to s. “”“

pub fn cumulative_sum(&self) -> Self

Given a finite function f : A → B, compute the cumulative sum of f, a finite function cumulative_sum(f) : A → sum_i(f())

let f = FiniteFunction::<VecKind>::new(VecArray(vec![3, 0, 1, 4]), 5).unwrap();
let c = f.cumulative_sum();
assert_eq!(c.table, VecArray(vec![0, 3, 3, 4]));
assert_eq!(c.target(), 8);

let f = FiniteFunction::<VecKind>::new(VecArray(vec![]), 5).unwrap();
let c = f.cumulative_sum();
assert_eq!(c.table, VecArray(vec![]));
assert_eq!(c.target(), 0);

Trait Implementations

impl<K: ArrayKind> Add<&FiniteFunction<K>> for &FiniteFunction<K>

type Output = Option<FiniteFunction<K>>

The resulting type after applying the + operator.

fn add(self, rhs: &FiniteFunction<K>) -> Option<FiniteFunction<K>>

Performs the + operation.

impl<K: ArrayKind> Arrow for FiniteFunction<K>

type Object = <K as ArrayKind>::I

fn source(&self) -> Self::Object

fn target(&self) -> Self::Object

fn identity(a: Self::Object) -> Self

the identity morphism on a

fn compose(&self, other: &Self) -> Option<Self>

Compose morphisms in diagrammatic order: self ; other

impl<K: ArrayKind> BitOr<&FiniteFunction<K>> for &FiniteFunction<K>

type Output = FiniteFunction<K>

The resulting type after applying the | operator.

fn bitor(self, rhs: &FiniteFunction<K>) -> FiniteFunction<K>

Performs the | operation.

impl<K: ArrayKind> Clone for FiniteFunction<K>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: ArrayKind> Coproduct for FiniteFunction<K>

fn inj0(a: Self::Object, b: Self::Object) -> Self

Coproduct injection 0.

As an array, the indices 0..a

fn inj1(a: Self::Object, b: Self::Object) -> Self

Coproduct injection 1.

As an array, the indices a..(a+b)

assert_eq!(
    FiniteFunction::<VecKind>::inj1(3, 5).table,
    VecArray(vec![3,4,5,6,7]),
    )

fn initial_object() -> Self::Object

fn initial(a: Self::Object) -> Self

Construct the initial arrow initial_a : 0 → a from some object a

fn coproduct(&self, other: &Self) -> Option<Self>

Construct the coproduct of two arrows, or None if they didn’t share a codomain.

impl<K: ArrayKind> Debug for FiniteFunction<K>

where K::Index: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K: ArrayKind, T> From<FiniteFunction<K>> for SemifiniteArrow<K, T>

fn from(val: FiniteFunction<K>) -> Self

Converts to this type from the input type.

impl<K: ArrayKind> HasLen<K> for FiniteFunction<K>

fn len(&self) -> K::I

fn is_empty(&self) -> bool

impl<K: ArrayKind> Monoidal for FiniteFunction<K>

fn unit() -> Self::Object

the monoidal unit object

fn tensor(&self, other: &Self) -> Self

f \otimes g of two morphisms

impl<K: ArrayKind> PartialEq for FiniteFunction<K>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: ArrayKind> Shr<&FiniteFunction<K>> for &FiniteFunction<K>

type Output = Option<FiniteFunction<K>>

The resulting type after applying the >> operator.

fn shr(self, rhs: &FiniteFunction<K>) -> Option<FiniteFunction<K>>

Performs the >> operation.

impl<K: ArrayKind, T> Shr<&SemifiniteFunction<K, T>> for &FiniteFunction<K>

where K::Type<T>: Array<K, T>,

A FiniteFunction can be precomposed with a SemifiniteFunction to re-index it.

type Output = Option<SemifiniteFunction<K, T>>

The resulting type after applying the >> operator.

fn shr( self, other: &SemifiniteFunction<K, T>, ) -> Option<SemifiniteFunction<K, T>>

Performs the >> operation.

impl<K: ArrayKind> SymmetricMonoidal for FiniteFunction<K>

fn twist(a: K::I, b: K::I) -> Self

Construct the symmetry \sigma_{a,b} from a and b.

impl<K: Eq + ArrayKind> Eq for FiniteFunction<K>

where K::Index: Eq, K::I: Eq,