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

Eugene Kirpichov ekirpichov at gmail.com
Sun Nov 15 13:04:28 EST 2009

Hey, I've found terrific slides about monoids!
Edward Kmett, you rock!

- but the second part was too hard for me to read it fully without
special motivation.

2009/11/15 Daniel Schüssler <anotheraddress at gmx.de>:
> 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
> _______________________________________________