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:

  • \mathbf{Set}, the category of sets, whose objects are sets and whose morphisms are ordinary functions, and
  • \mathbf{Mon}, the category of monoids, whose objects are monoids and whose morphisms are monoid homomorphisms.

We have two functors between these categories:

  • U : \mathbf{Mon}\to\mathbf{Set}, the forgetful functor, taking a monoid to its underlying set, and
  • F : \mathbf{Set}\to\mathbf{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.

The functors U and F are adjoint, i.e., there is a natural bijection between the set of functions \mathbf{Set}(X, UY) and the set of monoid homomorphisms \mathbf{Mon}(FX, Y), for each set X and monoid Y.

Monoidal transducers from a set X to a set Y are interpreted as natural transformations between the functors \mathbf{Set}(X, U(-)) and \mathbf{Set}(Y, U(-)) from the category \mathbf{Mon} to \mathbf{Set}. By adjointness, we can replace the functors \mathbf{Set}(X, U(-)) and \mathbf{Set}(Y, U(-)) with isomorphic functors \mathbf{Mon}(FX, -) and \mathbf{Mon}(FY, -). Therefore, the set of monoidal transducers is isomorphic to the set of natural transformations from \mathbf{Mon}(FX, -) to \mathbf{Mon}(FY, -), which by Yoneda Lemma is isomorphic to the set \mathbf{Mon}(FY, FX), i.e., the set of monoid homomorphism from the free monoid FY to the free monoid FX.

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 FY\to FX is uniquely determined by its restriction to the set of generators Y, i.e., by the function Y\to FX, 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.

Advertisements