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.


(f.source, f.target)

Return type:


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


Identity map at n

Return type:


compose(g: AbstractFiniteFunction)

Compose this finite function with another


g – A FiniteFunction for which self.target == g.source


The composition f ; g.


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


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

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

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

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

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


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

classmethod twist(a, b)

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.


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.


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.


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


f – A finite function of type A B


A finite function of type B A+1

Return type:


yarrow.finite_function.cumsum(f: AbstractFiniteFunction) AbstractFiniteFunction