Notes on Transducers are monoid homomorphisms

Monoidal transducers are in bijection with monoid homomorphisms between free monoids.

transducers (reducing function transformers):

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

Alternatively:

import Data.Monoid
-- newtype Endo r = Endo (r -> r)
type Reducer r = a -> Endo r
-- type Transducer a b = forall r. (a -> Endo r) -> (a -> Endo r)

Which gives rise to the following Monoid instance:

instance Monoid (Endo r) where
  mempty = Endo id
  Endo f <> Endo g = Endo (f . g)

Define monoidal transducers:

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

Arbitrary monoidal transducers give rise to normal transducers (they’re the same; with m Endo):

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

We can go in the opposite direction (Cayley representation)!

See also this comment on reddit

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

rep is a monoid homomorphism; i.e.

a function \(f : M \rightarrow N\) such that \[f(x \cdot_M y) = f(x) \cdot_N f(y) \\ f(1_M = 1_N)\]

Concretely:

rep (x <> y) == rep x <> rep y
rep mempty == mempty

It is also split injective with splitting:

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

i.e. abs . rep == id

Hence we have a way to get from Transducer to MonoidalTransducer:

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

NB. phi and psi are not necessarily mutually inverse.

In CT (almost w4w from original article, I understood in bits):

We have two categories, \(Set\) (objects: sets, morphisms: ordinary functions) and \(Mon\) (objects: monoids, morphisms: monoid homomorphisms).

We have two functors between these categories:

\(U : Mon \rightarrow Set\), the forgetful functor, taking a monoid to its underlying set

\(F : Set \rightarrow Mon\), the free monoid functor, taking a set X to a free monoid generated by X, which is nothing but the set of lists over X with the standard structure of a monoid.

U and F are adjoint => there is a natural bijection between the set of functions \(Set(X, UY)\) and the set of monoid homomorphisms \(Mon(FX, Y)\), for each set X and monoid Y.

Monoidal Transducers from X -> Y (both sets) are interpreted as natural transformations between the functors \(Set(X, U(-))\) and \(Set(Y, U(-))\) from the category \(Mon\) to \(Set\).

By adjointness(above), we can replace the functors \(Set(X, U(-))\) and \(Set(Y,U(-))\) with isomorphic functors \(Mon(FX, -)\) and \(Mon(FY, -)\). So, the set of monoidal transducers is isomorphic to the set of natrual transformations from \(Mon(FX, -)\) to \(Mon(FY, -)\), which by the Yoneda Lemma is isomorphic to the set \(Mon(FY, FX)\) (the set of monoid homomorphisms from the free monoid \(FY\) to the free monoid \(FX\)).

The category of monoidal transducers whose objects are sets and whose morphisms are monoidal transducers is isomorphic to the category of free monoids (a subcategory of the category of monoids). The category of monoids is isomorphic to the Kleisli category of the list monad: every monoid homomorphism FY -> FX is uniquely determined by its restriction to the set of generators Y, i.e. by the function Y -> FX, and composition of monoid homomorphisms translates into Kleisli composition.

Monoidal transducers from a -> b are isomorphic to monoid homomorphisms from [b] -> [a], which are isomorphic to Kleisli arrows b -> [a].

The concrete bijections are:

chi :: MonoidalTransducer a b -> (b -> [a])
chi f = f return

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

i.e. the monoid homomorphism associated with a function f :: b -> [a] is concatMap f :: [b] -> [a]

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 map and filter on lists, because they’re monoid homomorphisms! It’s impossible, however, to define a function:

taking :: Int -> MonoidalTransducer a a

because take is not a monoid homomorphism.

Discussion on reddit