Я ☞ Articles ☞ Context-free effects with Monoidal functors

Previously: Bind and traverse with Kleisli morphisms

Familiar taste of monoids

Do those monoidal functors somehow related to monoids, right? Highly likely you already familiar with this concept - it’s pretty convenient to use. But I don’t want to hop between these relative definitions, it’s better to build our intuition on something more solid.

Monoidal functor is a special kind of functor between categories with some tensor. You can think on tensor as a placeholder for either a product or a sum of objects (depicted below as *).

I recommend that you don’t think about monoidal functors or monoidal categories, but rather think about natural transformations of semimonoidal functors instead. Here you go:

Test it on products and sums

In order to tie this abstract pattern to our intuition, let’s take an example from the previous chapter - combining optional values:

Maybe i `P` Maybe ii `AR__` Maybe (i `P` ii)

I bet you already feel this taste of naturality - there is only one implementation for such a transformation that actually makes sense:

Some i `lu` Some ii `q____` Some (i `lu` ii)

You can think of this dotted circle with a dot inside operator as a tuple constructor.

But actual operator that does this magic (combining effects) looks like this (yp):

`yp`: t i `P` t ii ---> t (i `P` ii)

So in case if you want to use it as an infix operator placed between two effectful values you need to combine a tuple builder and an effect merger:

(x): Maybe i
(y): Maybe ii
(x `lu'yp` y): t (i `P` ii)

So, this operator can move you from a product of optional values to an optional product of values. But we also can send a product of optional values to an optional sum of values. Spot the difference:

`yp`: t i `P` t ii ---> t (i `P` ii)
`ys`: t i `P` t ii ---> t (i `S` ii)

Implementing such a transformation is not so natural I would say… In this case we have to choose which one we inspect first - first or second item of a tuple. Since everything in Я left-associative, let’s make it left-biased as well:

Some x `lu'ys` ______ `q___` Some (This x)
______ `lu'ys` Some y `q___` Some (That y)

Semi this, semi that…

Why is it semimonoidal, by the way? To make it fully monoidal we need to define identity. Actually there are many semi definitions with turned off identity property - semifunctors, semi natural transformations, semigroups*, semigroupoids*… For now you can express only semifunctors in Я.

Identity morphisms

Sorry, I got distracted by the details. We need to define identity as well - this is where things gets trickier. Identity here is a special morphism with a neutral element:

identity: (Neutral tensor `AR` i) `AR` t i

Think of neutral element in terms of algebraic sense - for sum it’s 0 (Void), for product it’s 1 (Unit). Substituting these objects on neutral placeholder we get:

identity [`P`] [`P`]: (Unit `AR` i) `AR` t i
identity [`P`] [`S`]: (Void `AR` i) `AR` t i

A bit of adjustment left to make these morphisms to be useful in code:

identity [`P`] [`P`] ~ enter: t Unit
identity [`P`] [`P`] ~ intro: i `AR` t Unit
identity [`P`] [`S`] ~ empty: t o

Let’s see how they are working with Optional’s (enter, intro, empty):

enter @Maybe `q__` Some Unit
intro @Maybe `q__` Some
empty @Maybe `q__` None Unit

Playing with list combinatorics

I think examples with optionals are quite easy. It’s time to tackle lists:

`yp`: List i `P` List ii ---> List (i `P` ii)

Despite the fact that implementation of this transformation is obvious, it would surprise us - we lose elements if their length are not matched:

[1, 2, 3] `lu'yp` [4, 5] `q___` [1 `lu` 4, 2 `lu` 5]
[1, 2] `lu'yp` [3, 4, 5] `q___` [1 `lu` 3, 2 `lu` 4]

Since we already have an internal convention to keep everything left-biased, implementation with a sum target could surprise us even more - this transformation get an element of the right part list only if it’s absent on the left side:

[1, 2, 3] `lu'ys` [4, 5] `q___` [This 1, This 2, This 3]
[1, 2] `lu'ys` [3, 4, 5] `q___` [This 1, This 2, That 3]

However, I have an idea.

Getting more from both sides

What if we combine Sum and Product and use it as a new tensor? It’s going be either a sum of two types or a product of the same types.

(i `SP` ii) ~ (i `S` ii `S_` i `P` ii)

I called this monster SP since it’s a combination of Sum and Product (any suggestions related to a glyph and a name for this chupacabre are welcome). We will use it as a target tensor for a new monoidal transformation operator (ysp):

`ysp`: t i `P` t ii `AR_` t (i `SP` ii)

So this way we do not let any element to drop out:

[1, 2, 3] `lu'ysp` [4, 5] `q___` [That (1 `lu` 4), That (2 `lu` 5), This (This 3)]
[1, 2] `lu'ysp` [3, 4, 5] `q___` [That (1 `lu` 3), That (2 `lu` 4), This (That 5)]

References in Haskell

• For some reason, people call Alternative typeclass as a monoidal one, but it doesn’t seem correct to me - things just do not align at all. The instance for a List just concatenates one to another - I don’t think that Sum resembles it.

• I didn’t invent this SP type, there is similar one called These.

That tuple operator…

In this chapter I introduced a new infix lu operator that builds a tuple from two parameters - it’s a special case of a group of operators related to limits and colimits.

We will talk about it next time.

Continue: Pushing to the limit!