Ramblings by Benjamin Kovach
Theme adapted from minimal by orderedlist.
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.