Re: [Haskell-cafe] strictness properties of monoidal folds
Hello Alexey, sorry for my slow response. On Thu, Aug 4, 2011 at 7:10 AM, Alexey Khudyakov wrote: > 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? >> >> Left and right folds behave identically for finite structures but they > are different for infinite ones. I agree that for types like normal lists that allow infinite structure it makes sense to have different folds like foldr and foldl that are explicit about the nesting of the combining function. I don't think that there are laws for foldMap that require it to work for infinite lists. One could even argue that the monoid laws imply that the results for folding leftwards and rightwards should be equal, that is undefined.. For types that only allow finite sequences (like Data.Sequence or Data.Vector) this is not an issue. But you convinced me that a strict and lazy foldMap can be distinguished even for list types that have a strict append function by using a lazy mappend function for accumulation. Best regards, Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] strictness properties of monoidal folds
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
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] strictness properties of monoidal folds
Hello Cafe, left- and rightwards folds come in strict and lazy variants foldl/fold' and foldr/foldr' which makes sense because strict versions sometimes use less stack space while lazy versions support infinite data. For example, head (foldr (:) [] [1..]) returns in an instant while head (foldr' (:) [] [1..]) diverges. On the other hand foldl' (flip (:)) 0 [1..10^9] runs in constant space while foldl (flip (:)) 0 [1..10^9] consumes all memory available on my machine (at least without optimizations. With optimizations GHC's strictness analyzer seems to be smart enough to make the accumulator strict.) 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? Sebastian P.S. I thought the `Last` monoid would be an example that requires a lazy accumulator but it is not because the `Just` constructor guards list elements. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
