# 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)