Why is Monoid not a requirement for foldr / foldl?

Question

I am considering the Foldable class in Haskell. The two methods fold , foldMap require an instance of Monoid. But foldr or foldl do not have this limitation.

 fold :: Monoid m => tm -> m foldMap :: Monoid m => (a -> m) -> ta -> m foldr :: (a -> b -> b) -> b -> ta -> b foldl :: (b -> a -> b) -> b -> ta -> b 

In order for the results of foldr / foldl be equivalent, should we not restrict this folding function to an associative one? Are there any examples where foldr / foldl results differ on the same list?

Should a folded instance wrap the value of a monoidal value? Or is folding more common?

Answer 1

In order for the results of foldr / foldl be equivalent, should we not restrict this folding function to an associative one? Are there any examples where foldr / foldl differ on the same list?

Yes. If you pass a non-associative function (for example, subtracting (-) ), you will get completely different results. And, as you rightly pointed out, there is no Monoid instance that matches something like (-) .

But it is by design. There are Foldable such restrictions on Foldable instances that foldr and foldl must accept associative functions. There are situations when you can reset something like subtraction. The Foldable f instance is more interested in limiting what f can do. Laws, in particular, are as follows:

 foldr fzt = appEndo (foldMap (Endo . f) t ) z foldl fzt = 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 does something clever by default with the endomorphism monoid newtype Endo a = Endo (a -> a) :

 -- | Right-associative fold of a structure. -- -- @'foldr' fz = 'Prelude.foldr' fz . 'toList'@ foldr :: (a -> b -> b) -> b -> ta -> b foldr fzt = appEndo (foldMap (Endo #. f) t) z 

to build monoidal addition from possibly non-monoidal f and z .

So, in the end, the answer to the question "Why is the Monoid not a requirement?" is very boring, "because it is more practical and, in the end, not needed."

For more information, I refer you to the paper that started everything, Application programming with effects .