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

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@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 wrote:

...

2009/11/13 Rafael Gustavo da Cunha Pereira Pinto < RafaelGCPP.Linux@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 竹密岂妨流水过 山高哪阻野云飞 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe