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

[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