Transducers are monoid homomorphisms
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
b is defined as
type Transducer a b = forall r. Reducer a r -> Reducer b r
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
Endo m using the Cayley representation:
rep :: Monoid m => m -> Endo m rep = Endo . mappend
rep is a monoid homomorphism. Furthermore, it is split injective with a splitting
abs :: Monoid m => Endo m -> m abs (Endo f) = f mempty
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
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
b are in bijection with monoid homomorphisms from
[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
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 is not a monoid homomorphism.