[Haskell-cafe] strictness properties of monoidal folds

[Alexey Khudyakov]

On 02.08.2011 08:16, Sebastian Fischer wrote:
> Data.Foldable also provides the monoidal fold function foldMap. It is
> left unspecified whether the elements are accumulated leftwards,
> rightwards or in some other way, which is possible because the combining
> function is required to be associative. Does this additional freedom for
> implementors go so far as to allow for strict accumulation? Is it safe
> to implement foldMap (without prime) with a strict accumulator or are
> there examples where lazy accumulation is useful like in the above foldr
> example and distinguishable from strict accumulation without breaking
> the monoid laws?
>
Left and right folds behave identically for finite structures but they 
are different for infinite ones. Here is an example:

> island = map First $ Just "Snark" : repeat Nothing
>
> foldr mappend mempty island = First {getFirst = Just "Snark"}
> foldl mappend mempty island = ⊥

If mappend is lazy arguments then strict and lazy could be distingushed. 
And Last indeed offers an example:

 > island = [ error "Boojum", Last (Just "Snark") ]
 >
 > foldl  mappend mempty island = Last {getLast = Just "Snark"}
 > foldl' mappend mempty island = Last {getLast = *** Exception: Boojum