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:

AbstractFiniteFunction

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 and g : A₁ → B compute the coproduct f.coproduct(g) : A₀ + A₁ → B

static unit()

return the unit object of the category

tensor(g)

Given maps f : A₀ → B₀ and g : A₁ → B₁ compute the tensor product f.tensor(g) : A₀ + A₁ → B₀ + B₁

classmethod twist(a, b)

coequalizer(g)

Given finite functions f, g : A → B, return the coequalizer q    : B → Q which is the unique arrow such that f >> q = g >> q having a unique arrow to any other such map.

classmethod terminal(a, dtype='int64')

Compute the terminal map ! : a → 1.

classmethod singleton(x, b, dtype='int64')

return the singleton array [x] whose domain is b.

argsort()

Given a finite function f : A → B Return the stable sorting permutation p : A → A such that p >> f is monotonic.

classmethod interleave(N: int)

classmethod cointerleave(N)

classmethod coproduct_list(fs: List[AbstractFiniteFunction], target=None)

Compute the coproduct of a list of finite functions. O(n) in size of the result.

Warning

Does not speed up to O(log n) in the parallel case.

classmethod tensor_list(fs: List[AbstractFiniteFunction])

Compute the tensor product of a list of finite functions. O(n) in size of the result.

Warning

Does not speed up to O(log n) in the parallel case.

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 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.

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:

AbstractFiniteFunction

yarrow.finite_function.cumsum(f: AbstractFiniteFunction) → AbstractFiniteFunction