2009/11/13 Rafael Gustavo da Cunha Pereira Pinto :

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

On Fri, Nov 13, 2009 at 4:52 PM, Andrew Coppin wrote:

Stephen Tetley wrote:

...

2009/11/13 Rafael Gustavo da Cunha Pereira Pinto :

...

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_.

This is the thing. If we had a class specifically for containers, that could be useful. If we had a class specifically for algebras, that could be useful. But a class that represents "any possible thing that can technically be considered a monoid" seems so absurdly general as to be almost useless. If you don't know what an operator *does*, being able to abstract over it isn't especially helpful...

...in my humble opinion. (Which, obviously, nobody else will agree with.)

But can't you say exactly the same about Monads? And at times it's useful to be able to switch between getting all results (List) and getting one (or none, Maybe), no? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe

2009/11/13 Magnus Therning :

On Fri, Nov 13, 2009 at 4:52 PM, Andrew Coppin wrote:

...

This is the thing. If we had a class specifically for containers, that could be useful. If we had a class specifically for algebras, that could be useful. But a class that represents "any possible thing that can technically be considered a monoid" seems so absurdly general as to be almost useless. If you don't know what an operator *does*, being able to abstract over it isn't especially helpful...

...in my humble opinion. (Which, obviously, nobody else will agree with.)

But can't you say exactly the same about Monads?

There's a comment about monads for programming that goes along the lines of 'Monads are a just a structure (ADT?), but they happen to be a very good one." Does anyone know the original version (not my paraphrase) and who the originator was? Thanks Stephen

On Fri, 2009-11-13 at 15:16 -0200, Rafael Gustavo da Cunha Pereira Pinto wrote:

"...in my humble opinion. (Which, obviously, nobody else will agree with.)"

I somewhat agree with your opinion!!

What I miss the most is practical examples:

1) A function that uses a Monoid as a container 2) A function that uses Monoid as algebra

and so on, for most of categories.

Here are two practical examples. Most aggregate statistic functions (think of all the aggregate functions in SQL, sum, average, stddev) are monoids. So you can write a generic "compute statistics" function for some dataset and then use it for any monoid statistic function that you come up with. Even better, your "compute statistics" function can take advantage of parallelism since the monoid operation is associative. Another practical example is config files and (equivalently) sets of command line flags. These things are records containing fields. But each field is a monoid (usually list or last) and this lets you make the whole record a monoid, point wise. This lets you do useful stuff like combining configuration from multiple sources (like a config file, defaults and command line) using just mappend. Now you could say, why make it a monoid, why not just provide a function `combineStats` or `combineConfig`. There are two reasons, one is that it provides documentation, it says "this thing is an instance of that well-known pattern". Secondly it sometimes lets you reuse generic functions (eg Data.Traversable). Duncan

Andrew Coppin wrote:

This is the thing. If we had a class specifically for containers, that could be useful. If we had a class specifically for algebras, that could be useful. But a class that represents "any possible thing that can technically be considered a monoid" seems so absurdly general as to be almost useless.

You don't have to look any further than the Writer monad to find an example of how this kind of abstraction is useful. The Writer monad uses a monoid to accumulate results. The monoid provided to Writer could be container-like, like a list; it could be a record whose fields are updated with each operation; it could be a number whose value changes with each operation; etc. The point is that it's general: it can be any value that can be combined with another value of the same type, using some operation to do that combination. Sigfpe's article about monoids goes into more detail: http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html

If you don't know what an operator *does*, being able to abstract over it isn't especially helpful...

The author of the Writer monad didn't know, and doesn't need to care, what the operator does. To him, being able to abstract over this unknown operator was not only helpful, but critical: without that, you'd need a different type of Writer for different types of accumulator. Indeed, we see that kind of thing regularly in lesser languages, where e.g. a logging class might require an instance of a container class to log to, so that if you want to do an accumulation that doesn't involve a container, you're out of luck. Or perhaps you get clever and implement a container class that actually wraps some non-container like value, so that "appending" to the container updates the value. Now you've reinvented monoids, and proved that the author of the logging class *did* need to be able to abstract over an unknown operator, but just didn't realize it. Anton

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

Magicloud Magiclouds wrote:

Hum... simple like that. So you meant the Monoid just abstracts/represents the ability to build a stack, right?

The key idea behind monoids is that they define sequence. To get a handle on what that means, it helps to think first about the "free monoid". If we have some set S, then we can generate a monoid which describes sequences of elements drawn from S (the neutral element is the empty sequence, the operator is juxtaposition). The tricky thing is that we *really* mean sequences. That is, what we're abstracting over is the tree structure behind a sequence. So if we have a sequence like "abcd" we're abstracting over all the trees (a(b(cd))), (a((bc)d)), ((ab)(cd)),... including all the trees with neutral elements inserted anywhere: ((a)(b(cd))), the other ((a)(b(cd))), (a((b)(cd))),... The places where monoids are useful are exactly those places where we want to abstract over all those trees and consider them equal. By considering them equal, we know it's safe to pick any one of them arbitrarily so as to maximize performance, code legibility, or other factors. One use is when we realize the significance of distinguishing sequences from lists. Sequences have no tree structure because they abstract over all of them, whereas lists convert everything into a canonical right-branching structure. Difference-lists optimize lists by replacing them with a different structure that better represents the true equivalence between different ways of appending. Finger trees are another way of optimizing lists which is deeply connected to monoids. Another place that's helpful is if we want to fold over the sequence. We can parallelize any such fold because we know that the grouping and sequence of reductions are all equivalent. This is helpful for speeding up some computations, but it also lets us think about things like parallel parsing--- that is, actually building up the AST in parallel, working on the whole file at once rather than starting from the beginning and moving towards the end. Another place it's useful is when we have some sort of accumulator where we want to be able to accumulate groups of things as well as individual things. The prime example here is Duncan Coutts' example of supporting multiple config files (where commandline flags can be thought of as an additional config file). CSS is another example of this sort of accretion. Just to build on the config file example a bit more. What sorts of behavior do we expect from programs when some flag is specified more than once? The three most common strategies are: first one wins, last one wins, and take all of them as a list. All three of these are trivially monoids. Some of the stranger behaviors we find are also monoids. For example, some programs interpret more than one -v flag as incrementing the level of verbosity. This is just the free monoid generated by a singleton set, aka unary numbers, aka Peano integers. We could generalize this so that we accept multiple -v=N flags which increment the verbosity by N, in which case we get the (Int,0,+) monoid. Given all these different monoids, we can define the type signature of a config file as a mapping from flags to the monoids used to resolve them. And doing so is far and away the most elegant approach to config handling I've seen anywhere. So monoid == sequence. Similarly, commutative monoid == set. Stacks don't have a heck of a lot of equivalences, so I can't think of a nice algebraic structure that equates to them off-hand. (And the sequentiality of monads comes from being monoids on the category of endofunctors.) -- Live well, ~wren

I see. Then what is about Dual and Endo? Especially Endo, I completely confused.... 2009/11/14 Eugene Kirpichov :

There is an astonishing number of things in programming that are monoids:  - Numbers, addition, 0  - Numbers, multiplication, 1  - Lists, concatenation, [] (including strings)  - Sorted lists, merge with respect to a linear order, []  - Sets, union, {}  - Maps, left-biased or right-biased union, {}  - Maps K->V, union where Vs for same K get merged in some other monoid, {}  - For any M: Subsets of M, intersection, M  - Any lattice with an upper bound, minimum, upper bound; symmetrically for a lower-bounded set  - If (S, *, u)  is a monoid, then (A -> S, \f g x -> f x * g x, \x -> u) is a monoid  - Product (a,b) and co-product (Either) of monoids  - Parsers, alternation, a parser that always fails  - etc.

The benefits of calling something a monoid arise from using general-purpose structures operating on monoids:  - Finger trees http://apfelmus.nfshost.com/monoid-fingertree.html  - Aforementioned maps which merge values for a key in a given monoid  - Aforementioned monoids lifted to functions  - Monoidal folds (Data.Foldable)  - ...

2009/11/13 Magicloud Magiclouds :

...

Hi,  I have looked the concept of monoid and something related, but still, I do not know why we use it?

-- 竹密岂妨流水过 山高哪阻野云飞

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

-- 竹密岂妨流水过 山高哪阻野云飞

Thank you guys. I think I learned a lot. Pretty confusing and interesting. 2009/11/14 Eugene Kirpichov :

For every monoid (M, *, u), the dual to it is the monoid (Dual M, \x y -> y * x, u) For every type A, there exists the A-endomorphism monoid (A->A, (.), id). Endo A is just a newtype for A -> A.

More simply, dualization is flipping the binary operation, and the endo monoid is the monoid of functions a->a with composition.

2009/11/13 Magicloud Magiclouds :

...

I see. Then what is about Dual and Endo? Especially Endo, I completely confused....

2009/11/14 Eugene Kirpichov :

...

There is an astonishing number of things in programming that are monoids:  - Numbers, addition, 0  - Numbers, multiplication, 1  - Lists, concatenation, [] (including strings)  - Sorted lists, merge with respect to a linear order, []  - Sets, union, {}  - Maps, left-biased or right-biased union, {}  - Maps K->V, union where Vs for same K get merged in some other monoid, {}  - For any M: Subsets of M, intersection, M  - Any lattice with an upper bound, minimum, upper bound; symmetrically for a lower-bounded set  - If (S, *, u)  is a monoid, then (A -> S, \f g x -> f x * g x, \x -> u) is a monoid  - Product (a,b) and co-product (Either) of monoids  - Parsers, alternation, a parser that always fails  - etc.

The benefits of calling something a monoid arise from using general-purpose structures operating on monoids:  - Finger trees http://apfelmus.nfshost.com/monoid-fingertree.html  - Aforementioned maps which merge values for a key in a given monoid  - Aforementioned monoids lifted to functions  - Monoidal folds (Data.Foldable)  - ...

2009/11/13 Magicloud Magiclouds :

...

Hi,  I have looked the concept of monoid and something related, but still, I do not know why we use it?

-- 竹密岂妨流水过 山高哪阻野云飞

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

-- 竹密岂妨流水过 山高哪阻野云飞

-- Eugene Kirpichov Web IR developer, market.yandex.ru

-- 竹密岂妨流水过 山高哪阻野云飞

Magicloud Magiclouds writes:

I see. Then what is about Dual and Endo? Especially Endo, I completely confused....

It should help to look at the instances:

-- | The dual of a monoid, obtained by swapping the arguments of 'mappend'. newtype Dual a = Dual { getDual :: a } deriving (Eq, Ord, Read, Show, Bounded)

instance Monoid a => Monoid (Dual a) where mempty = Dual mempty Dual x `mappend` Dual y = Dual (y `mappend` x)

You can tag a monoidal value as being "Dual" and then invoking "mappend" will swap the argument order. Re: Endo:

-- | The monoid of endomorphisms under composition. newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where mempty = Endo id Endo f `mappend` Endo g = Endo (f . g)

It's a way of labelling functions of type a -> a ("endomorphism") as being a monoid under composition (the "." operator). A short example:

GHCi, version 6.10.4: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. Prelude> import Data.Monoid Prelude Data.Monoid> let f = ((+2) :: Double -> Double) Prelude Data.Monoid> let g = ((/4) :: Double -> Double) Prelude Data.Monoid> appEndo (Endo f `mappend` Endo g) 4 3.0

same as "(f . g) 4" == 4/4 + 2

Prelude Data.Monoid> appEndo (getDual (Dual (Endo f) `mappend` Dual (Endo g))) 4 1.5

same as "(g . f) 4" == (4+2)/4. G. -- Gregory Collins

Excerpts from Daniel Schüssler's message of Sun Nov 15 07:51:35 +0100 2009:

Hi, Hi,

-- Invariant 1: There are never two adjacent Lefts or two adjacent Rights [...] normalize (Left a0 : Left a1 : as) = Left (mappend a0 a1) : normalize as normalize (Right a0 : Right a1 : as) = Right (mappend a0 a1) : normalize as

If you want to preserve your invariant, I think you should do : normalize (Left a0 : Left a1 : as) = normalize (Left (mappend a0 a1) : as) normalize (Right a0 : Right a1 : as) = normalize (Right (mappend a0 a1) : as) However, maybe it is correct if you only call normalize on (xs ++ ys) where xs and ys are already normalized so that you have only one point where you can break this invariant. Regards, -- Nicolas Pouillard http://nicolaspouillard.fr

Hey, I've found terrific slides about monoids! http://comonad.com/reader/wp-content/uploads/2009/08/IntroductionToMonoids.p... Edward Kmett, you rock! There's more http://comonad.com/reader/2009/iteratees-parsec-and-monoid/ - but the second part was too hard for me to read it fully without special motivation. 2009/11/15 Daniel Schüssler :

On Sunday 15 November 2009 13:05:08 Nicolas Pouillard wrote:

...

Excerpts from Daniel Schüssler's message of Sun Nov 15 07:51:35 +0100 2009:

...

Hi,

Hi,

Hi,

...

...

-- Invariant 1: There are never two adjacent Lefts or two adjacent Rights

[...]

...

normalize (Left a0 : Left a1 : as) = Left (mappend a0 a1) : normalize as normalize (Right a0 : Right a1 : as) = Right (mappend a0 a1) : normalize as

If you want to preserve your invariant, I think you should do :

normalize (Left  a0 : Left  a1 : as) = normalize (Left  (mappend a0 a1) :  as) normalize (Right a0 : Right a1 : as) = normalize (Right (mappend a0  a1) : as)

However, maybe it is correct if you only call normalize on (xs ++ ys) where xs and ys are already normalized so that you have only one point where you  can break this invariant.

Regards,

You are right :) If `normalize' is meant to normalize arbitrary lists, we'd have to use your version. If OTOH we just want to normalize xs ++ ys, we shouldn't iterate over the whole list; it'd be better to use Data.Sequence and just consider the middle, as you said (I was thinking of free groups, where there can be more collapse, but in that case we'd need the analogue your version too).

Greetings, Daniel _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

2009/11/14 Daniel Schüssler :

...

 - Product (a,b) and co-product (Either) of monoids the coproduct of monoids is actually a bit tricky.

Funny, I was just thinking about that. I was pondering the article at LTU on Lawvere theories: http://lambda-the-ultimate.org/node/3235 Essentially the idea is this: monads correspond to algebraic theories and monad transformers are ways to combine algebraic theories. But Lawvere theories provide another way to describe algebraic theories, and hence the things that monads can help with: like side effects, state and non-determinism. The advantage of Lawvere theories is there is some nice mathematics for how to combine them, something that's lacking from monads. So I just worked through a simple example: combining the Writer monad with itself. As Lawvere theories there are two ways to combine them: the product and the sum. The product corresponds, I think, to the usual monad transformer. This gives the Writer monad corresponding to the product of monoids. But the sum gives the Writer monad for the coproduct of monoids. (I think this is correct, but I'm not 100% sure I totally get Lawvere theories yet.) If you think about it, it's a very natural thing to do. If you think of the Writer monad as being useful to make logs then the coproduct allows you to interleave two different kinds of logs keeping the relative order of the entries. The usual monad transformer keeps two separate logs and so loses the relative ordering information. So it's actually something you might frequently want in real world code. But I can't imagine a monad transformer for Writer that would give the coproduct when combined with another Writer, so I don't think it could be implemented as such. -- Dan

It is a great example, shows both howto and benefits. Thanks. 2009/11/14 Maurí­cio CA :

...

 I have looked the concept of monoid and something related, but still, I do not know why we use it?

I don't know if it's a good example, but it's simple. This package I wrote uses reverse polish notation to write gtk2hs layout windows.

http://hackage.haskell.org/package/gtk2hs-rpn

Since the type for operators used in the stack is a Monoid instance, you can combine many of them to create new operators.

I believe you can think of monoids as things you can sequence to make new ones of the same type, but someone with better knowledge please say if this is actually a misleading idea.

Best, Maurício

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 竹密岂妨流水过 山高哪阻野云飞