open_hypergraphs.finite_function

An implementation of finite functions as arrays. All 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 open_hypergraphs.finite_function.FiniteFunction(target, table)

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.

Dtype: Any

Array: Type[ArrayBackend]

target: None | int

property dtype: Any

property source: int

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) → FiniteFunction

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:

FiniteFunction

compose(g: FiniteFunction) → FiniteFunction

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: None | int, dtype=None) → FiniteFunction

Compute the initial map ? : 0 → b

to_initial() → FiniteFunction

Turn a finite function f : A → B into the initial map ? : 0 → B.

>>> f.to_initial() == FiniteFunction.initial(f.target) >> f

classmethod inj0(a: int, b: int) → FiniteFunction

Compute the injection ι₀ : a → a + b

classmethod inj1(a: int, b: int) → FiniteFunction

Compute the injection ι₁ : b → a + b

inject0(b: int) → FiniteFunction

Directly compute (f ; ι₀) instead of by composition.

>>> f.inject0(b) == f >> ι₀

inject1(a: int) → FiniteFunction

Directly compute (f ; ι₁) instead of by composition.

>>> f.inject1(a) == f >> ι₁

coproduct(g: FiniteFunction) → FiniteFunction

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

static unit() → int

return the unit object of the category

tensor(g: FiniteFunction) → FiniteFunction

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

classmethod twist(a: int, b: int) → FiniteFunction

coequalizer(g: FiniteFunction) → FiniteFunction

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.

coequalizer_universal(f: FiniteFunction) → FiniteFunction

Given a coequalizer q : B → Q of morphisms a, b : A → B and some f : B → B’ such that f(a) = f(b), Compute the universal map u : Q → B’ such that q ; u = f.

classmethod terminal(a: int) → FiniteFunction

Compute the terminal map ! : a → 1.

classmethod singleton(x: int, b: int | None, dtype=None) → FiniteFunction

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

classmethod constant(x: int, a: int, b: int | None, dtype=None) → FiniteFunction

constant(x, a, b) is the constant function of type a → b mapping all inputs to the value x.

argsort() → Self

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

classmethod transpose(a: int, b: int, dtype=None) → FiniteFunction

transpose(a, b) is the “transposition permutation” for an a → b matrix.

Given an b*a-dimensional input thought of as a matrix in row-major order with b rows and a columns, transpose(a, b) computes the “target indices” in the transpose. So if we have a matrix M : A → B and a matrix N : B → A, then setting indexes N[transpose(a, b)] = M is the same as writing N = M.T

classmethod coproduct_list(fs: List[FiniteFunction], target=None, dtype=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[FiniteFunction])

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: FiniteFunction)

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.

class open_hypergraphs.finite_function.HasFiniteFunction(*args, **kwargs)

Classes which have a chosen finite function implementation

classmethod FiniteFunction() → Type[FiniteFunction]

class open_hypergraphs.finite_function.IndexedCoproduct(sources: FiniteFunction, values: FiniteFunction)

A finite coproduct of finite functions. You can think of it simply as a segmented array. Categorically, it represents a finite coproduct:

Σ_{i ∈ N} f_i : s(f_i) → Y

as a pair of maps:

sources: N            → Nat     (target is natural numbers)
values : sum(sources) → Σ₀

sources: FiniteFunction

values: FiniteFunction

property dtype

Return the dtype of the underlying table

classmethod initial(target: None | int, dtype=None) → IndexedCoproduct

classmethod singleton(values: FiniteFunction, dtype=None) → IndexedCoproduct

Turn a FiniteFunction f : A → B into an IndexedCoproduct `` Σ_{x ∈ 1} f : A → B

classmethod elements(values: FiniteFunction, dtype=None) → IndexedCoproduct

Turn a FiniteFunction f : A → B into an IndexedCoproduct `` Σ_{a ∈ A} f_a : A → B

property target: None | int

classmethod from_list(target, fs: List[FiniteFunction], dtype=None) → IndexedCoproduct

Create an IndexedCoproduct from a list of FiniteFunction

coproduct(y: IndexedCoproduct) → IndexedCoproduct

tensor(y: IndexedCoproduct) → IndexedCoproduct

classmethod tensor_list(xs: List[IndexedCoproduct])

Concatenate a nonempty sequence of IndexedCoproduct

indexed_values(x: FiniteFunction) → FiniteFunction

Like map_indexes but only computes the values array of an IndexedCoproduct

map_values(x: FiniteFunction) → IndexedCoproduct

Given an IndexedCoproduct of finite functions:

Σ_{i ∈ X} f_i : Σ_{i ∈ X} A_i → B

and a finite function:

b : B → C

return a new IndexedCoproduct representing:

Σ_{i ∈ X} f_i : Σ_{i ∈ W} A_i → C

map_indexes(x: FiniteFunction) → IndexedCoproduct

Given an IndexedCoproduct of finite functions:

Σ_{i ∈ X} f_i : Σ_{i ∈ X} A_i → B

and a finite function:

x : W → X

return a new IndexedCoproduct representing:

Σ_{i ∈ X} f_{x(i)} : Σ_{i ∈ W} A_{x(i)} → B

flatmap(y: IndexedCoproduct) → IndexedCoproduct

Compose two IndexedCoproducts.

class open_hypergraphs.finite_function.HasIndexedCoproduct(*args, **kwargs)

Classes which have a chosen indexed coproduct implementation

abstract classmethod IndexedCoproduct() → Type[IndexedCoproduct]