[Haskell-cafe] Could someone teach me why we use Data.Monoid?

Edward Kmett ekmett at gmail.com
Fri Nov 13 12:33:11 EST 2009


A monoid is just an associative binary operation with a unit. They appear
all over the place.

Why do we bother to talk about them in programming?

Well, it turns out that there are a lot of ways you can take advantage of
that fairly minimal amount of structure.

For one, you could take any container worth of values that can be mapped
into the monoid and apply the monoid to the elements the container in a left
to right or right to left or arbitrary ordering, and by the magic of
associativity you will get the same answer. Since you are free to
reparenthesize you can even compute the result in parallel.

Normally you have to distinguish between foldr and foldl. When the operation
you are applying is monoidal, you just have fold (from Data.Foldable). And
the container can choose the traversal that makes the most sense for it.

One particularly interesting, if somewhat complex monoid is the 'fingertree'
monoid, which lets you glue together fingertrees of values that have some
other monoidal measure on them.

This is actually a pretty tricky data structure to get right, but it can be
written once and for all (and has been tucked in Data.FingerTree) and is
parameterized on an arbitrary monoidal measure. I find uses for this
structure all over the place. For instance, FingerTrees of ByteStrings make
a great text buffer with fast splicing operations, while still allowing them
to be sliced at arbitrary positions if you use a monoidal measure for the
size.

In my monoids package I have several other monoids of interest. For
instance, if I am interested in reducing a container of values with a
monoid, I can turn to data compression techniques to build a variation on
the container that can be decompressed inside of the monoid. Lempel Ziv 78
describes a compression technique, that can be applied to improve
the sharing of monoidal intermediate results. Viewing the world this way
helps turn data compression techniques into efficiently reducible data
structures.

The fact that you can use associativity to reparenthesize for parallelism,
the unit to avoid having to perfectly subdivide into an exact number of
cores, and that you can feed the result into a fingertree lets you build
structures that you can build initially in parallel, and update
incrementally for a reduced cost.

All for the low low price of using a little bit of mathematical formalism.

I have a few posts on monoids and my monoids package on my blog at
comonad.com, which may help you get your head around their use outside of
the realm of pure mathematics.

-Edward Kmett

On Fri, Nov 13, 2009 at 12:11 PM, Magicloud Magiclouds <
magicloud.magiclouds at gmail.com> wrote:

> That is OK. Since understand the basic concept of monoid (I mean the
> thing in actual math), the idea here is totally not hard for me. But
> the sample here does not show why (or how) we use it in programming,
> right?
>
> On Sat, Nov 14, 2009 at 12:48 AM, Stephen Tetley
> <stephen.tetley at gmail.com> wrote:
> > 2009/11/13 Rafael Gustavo da Cunha Pereira Pinto <
> RafaelGCPP.Linux at gmail.com>:
> >>
> >> Monoid is the category of all types that have a empty value and an
> append
> >> operation.
> >>
> >
> > Or more generally a neutral element and an associative operation:
> >
> > The multiplication monoid (1,*)
> >
> > 9*1*1*1 = 9
> >
> > 1 is neutral but you might be hard pressed to consider it _empty_.
> >
> >
> > Best wishes
> >
> > Stephen
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
>
>
>
> --
> 竹密岂妨流水过
> 山高哪阻野云飞
>  _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091113/e049dbdd/attachment.html


More information about the Haskell-Cafe mailing list