Contents

### Context

#### Categorical algebra

internalization and categorical algebra

universal algebra

categorical semantics

#### Mapping space

internal hom/mapping space

# Contents

## Idea

In a cartesian closed category/type theory $\mathcal{C}$, given any object/type $B$ there is a monad

$Maps(B,-) \colon \mathcal{C} \to \mathcal{C}$

given by forming the internal hom out of $B$, hence the “space of functions” out of $B$. This is sometimes called the function monad. Its unit is given by sending values to constant functions with that value, and the monad operation is given by evaluating on the diagonal.

In the context of monads in computer science this monad is called the reader monad or environment monad. It serves to write programs in which all operations may “read in” a state of type $B$ (an “environment” variable).

## Definition

as a monad on $\mathcal{C} =$ Sets.

Then we describe it, more generally as the monad induced by a right base change adjunction

In this form the construction makes sense more generally (see for instance the quantum reader monad).

We write

$Maps(-,-) \;\colon\; \mathcal{C}^{op} \times \mathcal{C} \longrightarrow \mathcal{C}$

for the corresponding internal hom. In Sets this is the operation of forming function sets.

Fix $B \in \mathcal{C}$.

### In components

1. The underlying-functor of the $B$-reader monad is

$\bigcirc_B \;\colon\; D \;\mapsto\; Maps(B,D) \,.$
2. The unit of the monad is given by constructing constant functions:

$\begin{array}{ccc} D & \xrightarrow{ \;\; \eta^{\bigcirc_B}_D \;\; } & Maps(B,D) \\ d &\mapsto& \big( b \;\mapsto\; d \big) \mathrlap{ \;=\; const_d } \end{array}$
3. The monad multiplication is given by “evaluating diagonally:

$\begin{array}{ccc} Maps\big( B ,\, Maps(B,D) \big) &\xrightarrow{\;\;\; \mu^{\bigcirc_B} \;\;\;}& Maps(B,D) \\ f(-)(-) &\mapsto& \big( b \;\mapsto\; f(b)(b) \big) \mathrlap{\,.} \end{array}$

To check that this definition satisfies the monad-axioms:

$\begin{array}{ccc} Maps(B,D) &\xrightarrow{\;\;\; \eta^{\bigcirc_B}_{Maps(D,B)} \;\;\;}& Maps\big( B, Maps(B,D) \big) &\xrightarrow{\;\;\; \mu^{ \bigcirc_B }_{D} \;\;\;}& Maps(B,D) \\ \big( b' \mapsto f(b') \big) &\mapsto& \Big( b \mapsto \big( b' \mapsto f(b') \big) \Big) &\mapsto& \big( b \mapsto f(b) \big) \end{array}$

and

$\begin{array}{ccc} Maps(B,D) &\xrightarrow{\;\;\; Maps\big( B, \eta^{\bigcirc_B}_{D} \big) \;\;\;}& Maps\big( B, Maps(B,D) \big) &\xrightarrow{\;\;\; \mu^{ \bigcirc_B }_{D} \;\;\;}& Maps(B,D) \\ \big( b \mapsto f(b) \big) &\mapsto& \Big( b \mapsto \big( b' \mapsto f(b) \big) \Big) &\mapsto& \big( b \mapsto f(b) \big) \end{array}$
$\begin{array}{ccc} Maps\Big( B, Maps\big(B, Maps(B,D) \big) \Big) &\xrightarrow{\;\;\; \mu^{\bigcirc_B}_{ Maps(B,D) } \;\;\;}& Maps\big(B, Maps(B,D) \big) &\xrightarrow{\;\;\; \mu^{\bigcirc_B}_{ D } \;\;\;}& Maps(B,D) \\ \Big( b \mapsto \big( b' \mapsto (b'' \mapsto f(b, b', b'')) \big) \Big) &\mapsto& \big( b' \mapsto (b'' \mapsto f(b', b', b'')) \big) &\mapsto& \big( b'' \mapsto f(b'', b'', b'') \big) \end{array}$

and

$\begin{array}{ccc} Maps\Big( B, Maps\big(B, Maps(B,D) \big) \Big) &\xrightarrow{\;\;\; Maps\big( B, \mu^{\bigcirc_B}_{ D } \big) \;\;\;}& Maps\big(B, Maps(B,D) \big) &\xrightarrow{\;\;\; \mu^{\bigcirc_B}_{ D } \;\;\;}& Maps(B,D) \\ \Big( b \mapsto \big( b' \mapsto (b'' \mapsto f(b, b', b'')) \big) \Big) &\mapsto& \big( b' \mapsto (b'' \mapsto f(b', b'', b'')) \big) &\mapsto& \big( b'' \mapsto f(b'', b, b) \big) \end{array}$

### Via base change

For $B \in Sets$, write $\mathcal{C}_B$ for the category of $B$-indexed sets $(D_b)_{b \colon B}$ of objects of $\mathcal{C}$. (More generally, if $\mathcal{C}$ is a locally cartesian closed category (categorical semantics for dependent type theory), take $\mathcal{C}_B$ be the slice category over $B$.)

The right base change adjunction (context extension $\dashv$ dependent product) is

$\begin{array}{ccc} \mathcal{C}_B & \underoverset {\underset{(p_B)_\ast = \prod_{B}}{\longrightarrow}} {\overset{ (p_B)^\ast }{\longleftarrow}} {\;\;\; \bot \;\;\;} & \mathcal{C} \\ (D_b)_{b \colon B} &\mapsto& \prod_{b \colon B} D_b \end{array}$

Under the evident identification of maps $f \colon B \to D$ with tuples $\big( f(b) \big)_{b \colon B}$, the reader monad is the monad induced from this adjunction:

$\bigcirc_B \;\simeq\; (p_B)_\ast (p_B)^\ast \,.$

###### Remark

One may also think of this as being the polynomial functor associated with this span:

$\ast \leftarrow B \rightarrow \ast \rightarrow \ast \,.$

###### Remark

The comonad obtained by composing the other way around, $(p_B)^\ast (p_B)_\ast$, is the modal operator usually called necessity

From the universal property of the Cartesian product, one finds that:

$\begin{array}{ccc} b \colon B \; \vdash \; & D &\xrightarrow{\;\;\; id_D \;\;\;}& D \\ && \updownarrow \\ & D &\xrightarrow{\;\;\; \eta^{ \bigcirc_B }_D \;\;\;}& \prod_{b \colon B} D \\ & d &\mapsto& (d, \cdots, d) \end{array}$

$\begin{array}{ccc} & \prod_{b' \colon B} D_{b'} &\xrightarrow{\;\;\; id \;\;\;}& \prod_{b' \colon B} D_{b'} \\ && \updownarrow \\ b \colon B \;\dashv\; & \prod_{b' \colon B} D_{b'} &\xrightarrow{\;\;\; \epsilon^{ \star_B }_D \;\;\;}& D_{b} \\ & (d_{b'})_{b' \colon B} &\mapsto& d_{b} \end{array}$

$\begin{array}{ccc} \prod_{b \colon B} (p_B)^\ast \prod_{b' \colon B} (p_B)^\ast D &\xrightarrow{\;\;\; \prod_{b \colon B} \big( \epsilon^{\star_B} \big) (p_B)^\ast \;\;\;}& \prod_{b' \colon B} (p_B)^\ast C \\ \big( (f_{b'})_{b} \big)_{b', b \colon B} &\mapsto& \big( (f_{b})_{b} \big)_{b \colon B} \end{array}$

## Properties

In a cartesian closed category/type theory $\mathcal{C}$, the reader monad $[B,-] \colon \mathcal{C}\to \mathcal{C}$ is right adjoint to the coreader comonad $B\times (-)$.

The composite of coreader comonad followed by reader monad is the state monad $[B,B \times (-)]$ This monad models the situation where a program may not only depend on a immutable parameter $b \colon B$ but may be allowed to change it.

Just as the coreader comonad canonically becomes a monad when $B$ is a monoid, so the reader monad becomes a comonad in that case, and then it is sometimes called the “traced comonad”.

### Relation to random variables in probability theory

It makes sense to think of $[B,-]$ as producing spaces of random variables (Verdier 14) depending on possible worlds $b \in B$ [Toronto & McCarthy 10b, slide 24].

(While, from the perspective of modal type theory, its siblings $W^\ast \prod_W$ and $W^\ast \sum_W$ may be called necessity and possibility, respectively).

The intuition behind the Reader monad, for a mathematician, is perhaps stochastic variables. A stochastic variable is a function from a probability space to some other space. So we see a stochastic variable as a monadic value. [Verdier 14]

you could interpret this by regarding random variables as reader monad computations. [Toronto & McCarthy 10b, slide 35]

Toronto & McCarthy 10a, 2.2, Toronto 14, 6.2 call the function monad the random variable idiom.

This is also brought out by the relation of linear reader algebras to quantum measurement, see below. For more see also at nondeterministic computation the section Via indefiniteness effects.

For $B$ a set, the Kleisli category for the $B$-reader monad has $B$-tuples of functions as morphisms: (On the left we are showing the situation of the comparison functor and on the right we are using the “bind”-notation from monads in computer science.)

A special case is when $W$ is a 2 element set, where the $W$-reader algebras on $Set$ correspond to idempotent semigroups, also known as rectangular bands.

But the definition of the reader monad makes sense also for other hyperdoctrines such as for dependent linear types: For the resulting “linear” or “quantum” version of the reader monad the situation is different, see below.

## Examples

As remarked above, while the $B$-reader monad on toposes such as Set is induced from the base change adjunction as $\bigcirc_B(-) \,\coloneqq\, \underset{B}{\prod} \big( B \times (-) \big)$, the functor $\underset{B}{\prod} \;\colon\; Set_{/B} \xrightarrow{\phantom{--}} Set$ is not in general a monadic functor, so that $B$-reader-algebras are not in general equivalent to $B$-indexed sets.

However, this situation changes for $B$-readers analogously defined in other hyperdoctrines.

We discuss the example of the reader monad induced by $B$-dependent linear types which have biproducts, such as $B$-indexed sets of vector spaces (these we may think of as “quantum reader monads”, see the discussion at Quantum Modal Logic). We follow CQTS (2022):

###### Proposition

(quantum $\bigcirc_B$-algebras are $B$-dependent linear types)
For $B \;\in\;$ FiniteSets, the category of algebras for the $B$-reader monad

$\array{ \bigcirc_B \colon & Vect &\xrightarrow{\phantom{---}}& Vect \\ & \mathscr{H} &\mapsto& Maps\big(B, \mathscr{H} \big) \mathrlap{ \; \simeq \; \underset{b \colon B}{\bigoplus} \mathscr{H} } }$

on the category Vect of vector spaces (over any given ground field) is equivalent to that of vector bundles over $B$ (hence to $B$-indexed sets of vector spaces):

$EM\big( \bigcirc_B \big) \;\;\simeq\;\; Vect_B \,.$

###### Proof

We state first an abstract proof and then a concrete proof.

Abstractly, observe that Vect has (finite) biproducts (given by the direct sum of vector spaces) which together with the assumption that $B$ is finite implies that $\underset{B}{\prod} \;\colon\; Vect_B \xrightarrow{\;} Vect$:

1. is not only a right adjoint but also a left adjoint (hence an ambidextrous adjoint to pullback of vector bundles along $B \to \ast$), hence in particular it preserves all colimits;

2. is a conservative functor (since the $B$-components of any morphism of vector bundles over $V$ can still be extracted via (co-)projections from their image under forming the biproduct over $B$).

Therefore the conditions for the monadicity theorem are met (see there), implying that the functor is monadic functor, which in turn implies the claim.

Alternatively, we now check the claim more concretely by unwinding what it means for a vector space to carry $\bigcirc_B$-algebra structure and for a linear map between vector spaces to be a homomorphism for this structure:

First observe that the $\bigcirc_B$-monad product $\mu \;\colon\; \bigcirc_B \bigcirc_B \xrightarrow{\mu} \bigcirc_B$ on a vector space $\mathscr{H} \,\in\, Vect$ is explicitly given by:

$\array{ \underset{b \colon B}{\bigoplus} \; \underset{b' \colon B}{\bigoplus} \; \mathscr{H} & \xrightarrow{\;\; \mu^{\bigcirc}_{\mathscr{H}} \;\;} & \underset{b'' \colon B}{\bigoplus} \mathscr{H} \\ \big( \psi_{b,b'} \big)_{b,b' \colon B} &\mapsto& \big( \psi_{b'' ,b''} \big)_{b'' \colon B} }$

and that a $\bigcirc_B$-algebra structure on $\mathscr{H}$ is a linear map of this form:

(1)$\rho^\bigcirc_{\mathscr{H}} \;\colon\; \underset{b \colon B}{\oplus} \mathscr{H} \xrightarrow{\phantom{-}(P_b)_{b \colon B}\phantom{-}} \mathscr{H} \,.$

Of such maps, the $\bigcirc_B$-action property (here) demands that the following two linear maps are equal:

$\array{ & \underset{b \colon B}{\bigoplus} \; \underset{b' \colon B}{\bigoplus} \; \mathscr{H} &\xrightarrow{\; \mu^\bigcirc_{\mathscr{H}} \;}& \underset{b'' \colon B}{\bigoplus} \mathscr{H} &\xrightarrow{\; \rho^\bigcirc_{\mathscr{H}} \;}& \mathscr{H} \\ & \big( \psi_{b,b'} \big)_{b,b' \colon B} &\mapsto& \big( \psi_{b'',b''} \big)_{b'',b'' \colon B} &\mapsto& \underset{b'' \colon B}{\sum} P_{b''}(\psi_{b'',b''}) \\ \text{and} & \\ & \underset{b \colon B}{\bigoplus} \; \underset{b' \colon B}{\bigoplus} \; \mathscr{H} &\xrightarrow{\; \bigcirc \rho^\bigcirc_{\mathscr{H}} \;}& \underset{b'' \colon B}{\bigoplus} \mathscr{H} &\xrightarrow{\; \rho^\bigcirc_{\mathscr{H}} \;}& \mathscr{H} \\ & \big( \psi_{b,b'} \big)_{b,b' \colon B} &\mapsto& \big( \underset{b \colon B}{\sum} P_{b}(\psi_{b,b'}) \big)_{b' \colon B} &\mapsto& \underset{b, b' \colon B}{\sum} P_{b'}\big(P_{b}(\psi_{b,b'})\big) \mathrlap{\,.} }$

By considering the value of these maps on tuples of vectors $\big(\psi_{b,b'}\big)_{b,b' \colon B}$ which are non-zero only for single elements $(b,b') \in B \times B$ one finds that the above condition is equivalent to the following condition:

$\underset{ b, b' \colon B }{ \forall } \;\;\;\; P_b \circ P_{b'} \;=\; \left\{ \array{ P_b &\text{if} \; b = b' \\ 0 & \text{otherwise} \,. } \right.$

Moreover, the $\bigcirc_B$-unit $\id \xrightarrow{\;\; \eta^{\bigcirc_B} \;\;} \bigcirc_B$ is given by the diagonal map into the biproduct

$\array{ \mathscr{H} &\xrightarrow{\;\; \eta^{\bigcirc_B}_{\mathscr{H}} \;\;} & \underset{b \colon B}{\bigoplus} \mathscr{H} \\ \psi &\mapsto& (\psi_b \coloneqq \psi)_{b \colon B} }$

so that the unitality property (here) of the $\bigcirc_B$-algebra structure $(P_b)_{b \colon B}$ demands equivalently that the composite

$\array{ \mathscr{H} &\xrightarrow{\; \eta^{\bigcirc_B}_{\mathscr{H}} \;}& \underset{b \colon B}{\bigoplus} \mathscr{H} &\xrightarrow{\; \rho^{\bigcirc_B}_{\mathscr{H}} \;}& \mathscr{H} \\ \psi &\mapsto& \big( \psi \big)_{b \colon B} &\mapsto& \underset{b \colon B}{\sum} \; P_b(\psi) }$

is the identity function on $\mathscr{H}$, hence that this system of projection operators is “complete” in that

$\underset{b \colon B}{\bigoplus} P_b \;=\; id_{\mathscr{H}} \,.$

In summary, this means that for $B$-tuples of linear maps $(P_b \colon \mathscr{H} \to \mathscr{H})_{b \colon B}$ as in (1) to constitute a $\bigcirc_B$-module structure is equivalent to them being systems of orthogonal linear projection operators, whose images

$\mathscr{H}_b \;\coloneqq\; im(P_b) \;\subset\; \mathscr{H}$

span$\;$ $\mathscr{H}$ under direct sum:

$\mathscr{H} \;\simeq\; \underset{b \colon B}{\bigoplus} \mathscr{H}_b \,.$

Such structures, of course, are exactly the images under the right base change $\underset{B}{\prod} \;\colon\; Vect_B \longrightarrow{\;} Vect$ of $B$-indexed sets of vector spaces.

Finally, the homomorphism-property on a linear map $\mathscr{H} \xrightarrow{\phi} \mathscr{H}'$ between the underlying vector spaces of two such $\bigcirc_B$-modules demands that the following diagram commutes:

$\array{ \underset{b \colon B}{\bigoplus} \mathscr{H} &\xrightarrow{\;\;\; \underset{b \colon B}{\oplus} \;\;\;}& \underset{b \colon B}{\bigoplus} \mathscr{H} \\ \mathllap{ {}^{ \big( P_b \big)_{b \colon B} } } \big\downarrow && \big\downarrow \mathrlap{ {}^{ \big( P'_b \big)_{b \colon B} } } \\ \mathscr{H} & \underset{\phantom{---} \phi \phantom{---} } {\longrightarrow} & \mathscr{H}' \,. }$

The $B$-indexed components of this condition require that $\phi$ commutes with all these projection operators, in that

$b \colon B \;\;\;\; \vdash \;\;\;\; P'_b \circ \phi \;=\; \phi \circ P_b \,.$

But this evidently means that $\phi$ itself is the image under the direct sum-functor

$\phi \;=\; \underset{b \colon}{\oplus} \phi_b$

of a $B$-tuple of linear maps between the $B$-indexed component spaces:

$b \colon B \;\;\; \colon \;\;\; \mathscr{H}_b \longrightarrow \mathscr{H}' \,.$

This is the defining property of morphisms in $Vect_B$ and hence shows that $\bigcirc_B$-algebra homomorphisms are equivalently morphisms of $B$-indexed sets of vector spaces, hence that the two categories are agree.

###### Example

(free quantum $\bigcirc_B$-algebras and quantum measurement bases)
The free $\bigcirc_B$-algebras in Vect are those whose underlying vector space is of the form $\bigcirc_B \mathscr{B} = \underset{b \colon B}{\bigoplus} \mathscr{B}$ for any $\mathscr{B} \,\in \, Vect$, hence, under the equivalence of Prop. , are those $B$-dependent linear types which happen to assign the same vector space $\mathscr{B}$ for all $b \colon B$.

But homomorphisms of such free $\bigcirc_B$-algebras are still allowed to be non-trivially $B$-dependent families of linear maps. This is directly a special case of Prop. but is also immediate under the Kleisli equivalence from observing that $\bigcirc_B$-Kleisli morphisms are of the following form:

$\array{ \mathscr{B} &\xrightarrow{ \big( \phi_b \big)_{b \colon B} }& \underset{b \colon B}{\bigoplus} \mathscr{B}' \,. }$

In quantum information theory the $\bigcirc_B$-algebras in complex vector spaces which are free on the tensor unit $\mathbb{C} \,\in\, \mathbb{C} Vect$ (the 1-dimensional complex vector space) play the role of (finite dimensional complex vector spaces underlying) Hilbert space of quantum states which are spanned by the set $B$ regarded as a “quantum measurement basis”.

For example, the dependent linear type of qbits is the free $\bigcirc_B$-algebra $\bigcirc_{Bool} \mathbb{C}$ spanned by the classical type Bool $= \{0,1\}$ of bits, reflecting the two canonical quantum measurement-outcomes ($\vert 0\rangle$, $\vert 1 \rangle$) of qbits.

Curiously, from this one finds that quantum measurement is exactly indefiniteness handling

where

• “indefiniteness” is understood as the the effect/modality expressed by the reader monad $\bigcirc_B$ (see here),

• “handling” is understood as effect handling in the sense of effect-monads in computer science (see here);

namely: Notice that this process may be understood as the “dynamic lifting” of quantum measurement-results into the context (here: $B =$ Bool) of the ambient dependent linear type theory.

For more on this see at quantum circuits via dependent linear types.

This naturally relates to the discussion of quantum measurement via Frobenius algebra-structures which is popular in the context of quantum information theory via dagger-compact categories – as follows:

###### Remark

Since the direct sum of vector spaces is a biproduct and using our running assumption that $B$ is a finite set, it follows that the underlying functor of the quantum reader monad from Prop. coincides with that of the coreader comonad, and hence that the quantum reader monad is a Frobenius monad (see there).

###### Remark

Consider the $B$-indexed the direct sum $k^{\otimes^B}$ of the ground field with itself as a $k$-algebra and write

${k^{\otimes^B}}\text{-}Writer \;\colon\; Vect \to Vect$

for the writer monad corresponding to this monoid object in Vect: The monad which acts by forming the tensor product $Writer_{k^{\otimes^B}}(V) \;\coloneqq\; V \otimes \big( k^{\otimes^B} \big)$ and whose monad multiplication and unit of a monad are induced from the multiplication and unit in this monoid.

The above proof of Prop. shows at once that this writer monad is isomorphic to the $B$-reader monad:

$\bigcirc_B \;\simeq\; Writer_{k^{\otimes^B}} \,.$

Now the monad modules over a writer monad are just the ordinary modules over the corresponding monoid, so that

$\bigcirc_B Mod(Vect) \;\simeq\; \big( k^{\otimes^B} \big)Mod(Vect) \,.$

This provides a rather transparent re-derivation of and alternative perspective on Example .

Dually, as in Prop. , the quantum coreader comonad is isomorphic to the coreader comonad corresponding to the coalgebra-structure on $k^{\otimes^B}$.

Hence, as a Frobenius monad (Prop. ), the quantum reader corresponds to $k^{\otimes^B}$ regarded as a Frobenius algebra, in fact as a commutative and special Frobenius algebra. In this form the quantum reader monad is prominent in the literature on quantum information theory via dagger-compact categories [Coecke & Pavlović (2008), §1.5.1, Coecke & Paquette (2008), §2.3].

(2) reader monad$W \to (\text{-})$ on cartesian typesunique comonoid structure on $W$
coreader comonad$W \times (\text{-})$ on cartesian typesunique comonoid structure on $W$
writer monad$A \otimes (\text{-})$ on monoidal typeschosen monoid structure on $A$
cowriter comonad$\array{A \to (\text{-}) \\ \\ A \otimes (\text{-})}$ on monoidal typeschosen monoid structure on $A$

chosen comonoid structure on $A$
Frobenius (co)writer$\array{A \to (\text{-}) \\ A \otimes (\text{-})}$ on monoidal typeschosen Frobenius monoid structure

### General

The quantum reader monad – implicitly, in its incarnation as the $k^B$-DualWriter monad – is highlighted in the literature quantum information theory via dagger-compact categories as formalizing “classical structures” (namely linear bases for quantum measurement):