CODEWITHSUNDEEP
haskellfoldmonoidsfoldable
zeronone
zeronone

Reputation: 3041

Why Monoid is not a requirement for foldr/foldl?

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?

Upvotes: 6

Views: 670

Answers (1)

hao
hao

Reputation: 10228

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.

Upvotes: 5

Related Questions