yarrow.finite_function
An implementation of finite functions as arrays. All yarrow datastructures are ultimately built from finite functions. For an overview, see Wilson and Zanasi [WZ23], Section 2.2.2.
Finite functions can be thought of as a thin wrapper around integer arrays whose elements are within a specified range. Here’s an example of contructing a finite function:
>>> print(FiniteFunction(3, [0, 1, 2, 0]))
[0 1 2 0] : 4 → 3
Mathematically, this represents a function from the set of 4 elements to the set
of 3 elements, and so its “type” is 4 → 3
.
There are several constructors for finite functions corresponding to useful
morphisms in category theory.
For example, the identity
map is like numpy’s arange
:
>>> print(FiniteFunction.identity(5))
[0 1 2 3 4] : 5 → 5
and the terminal
map is an array of zeroes:
>>> print(FiniteFunction.terminal(5))
[0 0 0 0 0] : 5 → 1
Finite functions form a symmetric monoidal category. They can be composed sequentially:
>>> print(FiniteFunction.identity(5) >> FiniteFunction.terminal(5))
[0 0 0 0 0] : 5 → 5
And in parallel:
>>> FiniteFunction.identity(5) @ FiniteFunction.terminal(5)
FiniteFunction(6, [0 1 2 3 4 5 5 5 5 5])
- class yarrow.finite_function.AbstractFiniteFunction(target, table, dtype='int64')
Finite functions parametrised over the underlying array type (the “backend”). This implementation assumes there is a cls._Array member implementing various primitives. For example, cls._Array.sum() should compute the sum of an array.
- property source
The source (aka “domain”) of this finite function
- property type
Get the source and target of this finite function.
- Returns:
(f.source, f.target)
- Return type:
tuple
- classmethod identity(n: int)
Return the identity finite function of type n → n. :param n: The object of which to return the identity map :type n: int
- Returns:
Identity map at n
- Return type:
- compose(g: AbstractFiniteFunction)
Compose this finite function with another
- Parameters:
g – A FiniteFunction for which self.target == g.source
- Returns:
The composition f ; g.
- Raises:
ValueError – if self.target != g.source
- classmethod initial(b, dtype='int64')
Compute the initial map
? : 0 → b
- classmethod inj0(a, b)
Compute the injection
ι₀ : a → a + b
- classmethod inj1(a, b)
Compute the injection
ι₁ : b → a + b
- inject0(b)
Directly compute (f ; ι₀) instead of by composition.
>>> f.inject0(b) == f >> ι₀
- inject1(a)
Directly compute (f ; ι₁) instead of by composition.
>>> f.inject1(a) == f >> ι₁
- coproduct(g)
Given maps
f : A₀ → B
andg : A₁ → B
compute the coproductf.coproduct(g) : A₀ + A₁ → B
- static unit()
return the unit object of the category
- tensor(g)
Given maps
f : A₀ → B₀
andg : A₁ → B₁
compute the tensor productf.tensor(g) : A₀ + A₁ → B₀ + B₁
- classmethod twist(a, b)
- coequalizer(g)
Given finite functions
f, g : A → B
, return the coequalizerq : B → Q
which is the unique arrow such thatf >> q = g >> q
having a unique arrow to any other such map.
- classmethod terminal(a, dtype='int64')
Compute the terminal map
! : a → 1
.
- argsort()
Given a finite function
f : A → B
Return the stable sorting permutationp : A → A
such thatp >> f
is monotonic.
- classmethod coproduct_list(fs: List[AbstractFiniteFunction], target=None)
Compute the coproduct of a list of finite functions with a common target
- classmethod tensor_list(fs: List[AbstractFiniteFunction])
- injections(a: AbstractFiniteFunction)
Given a finite function
s : N → K
representing the objects of the coproductΣ_{n ∈ N} s(n)
whose injections have the typeι_x : s(x) → Σ_{n ∈ N} s(n)
, and given a finite mapa : A → N
, compute the coproduct of injectionsinjections(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.
- class yarrow.finite_function.FiniteFunction(target, table, dtype='int64')
Finite functions backed by numpy arrays
- yarrow.finite_function.argsort(f: AbstractFiniteFunction)
Applies a stable ‘argsort’ to the underlying array of a finite function. When that finite function is a permutation, this inverts it.
- yarrow.finite_function.bincount(f: AbstractFiniteFunction)
bincount the underlying array of a finite function
- Parameters:
f – A finite function of type
A → B
- Returns:
A finite function of type
B → A+1
- Return type: