Why Monoid is not a requirement for foldr/foldl?

Question

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?

Laskowski

Look at the types of the first functions of foldr and foldl. A monoid does not fit there. – Miraflores

@Miraflores Nah, a Monoid is the only thing that really makes sense for the standard folds, because everything is treated as "sort of a list". Wherever types are treated as having a more complicated structure, the "left" and "right" in the name stop making sense. If you want to fold over anything that isn't a list, you'll really have to provide a more complicated algebra. – Arriola

functional composition is associative: foldr :: (a -> b -> b) -> b -> t a -> b, foldr (c :: (a -> b -> b)) :: b -> t a -> b, c (x :: a) :: b -> b, so we get to compose c x1, c x2, ..., c xn in whatever order we like, because / IOW endofunctions do form a monoid, Endo b, all by themselves. With e.g. lists, (x :) == ([x] ++) , i.e. we can represent c as c x = (f x <>) with some suitable f, and c x . c y ~= f x <> f y. (or something like that). – Thermic

Answer 1

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?

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.

Slusher