### Transducers are monoid homomorphisms

#### by oleksandrmanzyuk

Well, that’s not quite right: *monoidal* transducers, which are closely related to transducers, are in bijection with monoid homomorphisms between free monoids. This wouldn’t make a catchy title, however, would it?

The following is my humble exploration of the ideas from Franklin Chen’s post, in which he is trying to give a more typeful account of transducers, a new abstraction coming to Clojure.

The type of *transducers*, or *reducing function transformers*, from `a`

to `b`

is defined as

type Transducer a b = forall r. Reducer a r -> Reducer b r

where

type Reducer a r = r -> a -> r

is a type of *reducers*, or reducing functions. Notice the universal quantification over `r`

in the definition of the transducer type. What properties of transducers does it imply?

Let us replace the definition of `Reducer`

with an isomorphic one:

type Reducer a r = a -> Endo r

`Endo r`

is a newtype wrapper around `r -> r`

defined in Data.Monoid, which allows us to give `r -> r`

the structure of a monoid:

instance Monoid (Endo r) where mempty = Endo id Endo f `mappend` Endo g = Endo (f . g)

We could replace `Endo r`

in the definition of the transducer type

type Transducer a b = forall r. (a -> Endo r) -> (b -> Endo r)

with an arbitrary monoid `m`

and consider *monoidal transducers*:

type MonoidalTransducer a b = forall m. Monoid m => (a -> m) -> (b -> m)

Clearly, a monoidal transducer gives rise to a transducer:

psi :: MonoidalTransducer a b -> Transducer a b psi h = h

Remarkably, we can go in the opposite direction as well. The trick is to embed a monoid `m`

into `Endo m`

using the Cayley representation:

rep :: Monoid m => m -> Endo m rep = Endo . mappend

The function `rep`

is a monoid homomorphism. Furthermore, it is split injective with a splitting

abs :: Monoid m => Endo m -> m abs (Endo f) = f mempty

That is, `abs . rep`

is the identity function. This allows us to define

phi :: Transducer a b -> MonoidalTransducer a b phi t f = abs . t (rep . f)

I don’t know if `phi`

and `psi`

are mutually inverse. I thought I had a proof that the composite `phi . psi`

is the identity function, but it relied on the free theorem for the type `MonoidalTransducer a b`

, which requires that `abs`

be a monoid homomorphism, which it is not.

Monoidal transducers are easier to understand than transducers. They can be interpreted categorically as follows.

We have two categories:

- , the category of sets, whose objects are sets and whose morphisms are ordinary functions, and
- , the category of monoids, whose objects are monoids and whose morphisms are monoid homomorphisms.

We have two functors between these categories:

- , the forgetful functor, taking a monoid to its underlying set, and
- , the free monoid functor, taking a set to a free monoid generated by , which is nothing but the set of lists over with the standard structure of a monoid.

The functors and are adjoint, i.e., there is a natural bijection between the set of functions and the set of monoid homomorphisms , for each set and monoid .

Monoidal transducers from a set to a set are interpreted as natural transformations between the functors and from the category to . By adjointness, we can replace the functors and with isomorphic functors and . Therefore, the set of monoidal transducers is isomorphic to the set of natural transformations from to , which by Yoneda Lemma is isomorphic to the set , i.e., the set of monoid homomorphism from the free monoid to the free monoid .

If one were so inclined, one could say that the category of monoidal transducers, whose objects are sets and whose morphisms are monoidal transducers, is equivalent (in fact, isomorphic) to the category of free monoids, a full subcategory of the category of monoids. The latter is isomorphic to the Kleisli category of the list monad: every monoid homomorphism is uniquely determined by its restriction to the set of generators , i.e., by the function , and composition of monoid homomorphisms translates into Kleisli composition.

To sum up, monoidal transducers from `a`

to `b`

are in bijection with monoid homomorphisms from `[b]`

to `[a]`

, which are in turn in bijection with functions `b -> [a]`

. The bijections are given explicitly by

chi :: MonoidalTransducer a b -> b -> [a] chi f = f return rho :: (b -> [a]) -> MonoidalTransducer a b rho f k = mconcat . map k . f

The monoid homomorphism associated with a function `f :: b -> [a]`

is `concatMap f :: [b] -> [a]`

. Note that the functions

mapping :: (a -> b) -> MonoidalTransducer b a mapping f k = k . f filtering :: (a -> Bool) -> MonoidalTransducer a a filtering p k x = if p x then k x else mempty

give rise to the functions `map`

and `filter`

on lists, which are monoid homomorphisms. Conversely, it is impossible to define a function

taking :: Int -> MonoidalTransducer a a

that would give rise to the function `take`

because `take`

is not a monoid homomorphism.

Thanks for taking the analysis to the next level of abstraction!

Interesting read. I understood almost some of it :)