Menu
I am looking at the Foldable class in Haskell. Two of the methods fold, foldMap requires a Monoid instance. But foldr or foldl don't have any such constraint.
fold :: Monoid m => t m -> m
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (b -> a -> b) -> b -> t a -> b
For the results of foldr/foldl to be equivalent, shouldn't it restrict the given folding function to be associative? Are there any examples where the results of foldr/foldl are different on the same list?
Shouldn't a Foldable instance wrap a Monoidal value? Or Foldable is more general?
681
Difference Between foldl and foldr The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.
Haskell Wiki compares foldr , foldl and foldl' and recommends using either foldr or foldl' . foldl' is the more efficient way to arrive at that result because it doesn't build a huge thunk.
Haskell, in turn, has two fundamental functions representing reducing, or, as we call it, folding – foldl and foldr – that differ in the order of the folding. foldl reduces elements of a container from left to right (as reduce in other languages usually does), while foldr reduces from right to left.
When you wonder whether to choose foldl or foldr you may remember, that both foldl and foldl' can be expressed as foldr . ( foldr may lean so far right it came back left again.) It holds (The converse is not true, since foldr may work on infinite lists, which foldl variants never can do.
It holds (The converse is not true, since foldr may work on infinite lists, which foldl variants never can do. However, for finite lists, foldr can also be written in terms of foldl (although losing laziness in the process), in a similar way like this:
However, for finite lists, foldr can also be written in terms of foldl (although losing laziness in the process), in a similar way like this: How can someone find a convolved expression like this?
For the results of
foldr/foldlto be equivalent, shouldn't it restrict the given folding function to be associative? Are there any examples where the results offoldr/foldlare different on the same list?
Yes. If you pass a non-associative function (like subtraction (-)) you will absolutely get different results. And as you rightly point out there is no Monoid instance that corresponds to something like (-).
But that is by design. There is no such restriction on Foldable instances that foldr and foldl must take associative functions. There are situations where you might want to fold with something like subtraction. An instance of Foldable f is more interested in constraining what the f can do. The laws in particular are:
foldr f z t = appEndo (foldMap (Endo . f) t ) z
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
fold = foldMap id
-- if f is a Functor
foldMap f = fold . fmap f
foldMap f . fmap g = foldMap (f . g)
You can see in the sources that foldr by default does something clever with the newtype Endo a = Endo (a -> a) endomorphism monoid:
-- | Right-associative fold of a structure.
--
-- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z
to build a monoidal fold out of possibly non-monoidal f and z.
So ultimately the answer to the question "Why is Monoid not a requirement?" is the very boring "because it is more practical and, in the end, not necessary."
For more information I refer you to the paper that started it all, Applicative Programming with Effects.
134
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
