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