How can I understand the laws for Foldable instances?

Question

On the page describing Data.Foldable, it says: Foldable instances are expected to satisfy the following laws:

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

Please help me understand how the above laws work. What is Endo . f?

Answer 1

Endo is "the monoid of endomorphisms under composition". appEndo is the field of this type.

newtype Endo a = Endo { appEndo :: a -> a }

-- i.e.
Endo :: (a -> a) -> Endo a
appEndo :: Endo a -> (a -> a)

You may treat "endomorphism" as a technically-correct term of functions which input and output types are the same (a -> a).

Endo is an instance of Monoid with composition:

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

---

To make the law easier to grasp, let's use the List type as a concrete example:

instance Foldable [a] where
    foldMap f []     = mempty
    foldMap f (x:xs) = f x `mappend` foldMap f xs

-- i.e.
-- foldMap f [a, b, …, w] == f a `mappend` f b `mappend` … `mappend` f w

When we evaluate the RHS of the law:

   foldMap (Endo . f)         t
== foldMap (\x -> Endo (f x)) [a, b, …, w]
== (\x -> Endo (f x)) a `mappend`   …   `mappend` (\x -> Endo (f x)) w
== Endo (f a) `mappend` Endo (f b) `mappend`   …   `mappend` Endo (f w)

recall mappend for Endo is composition, so the above is

== Endo (f a . f b .   …   . f w)

Finally we use appEndo (…) z to take out the composed function and apply it to the initial value z:

   appEndo (Endo (f a . f b .   …   . f w)) z 
== (f a . f b .   …   . f w)                z
== f a (f b (  …  (f w z)  …  ))

and this is exactly the definition of foldr for a list.

---

The foldl one is similar, Dual is another monoid instance where Dual a `mappend` Dual b == Dual (b `mappend` a), and getDual takes out the inner monoid. It should be easy to see how this produces foldl.

---

The fold function collapses the foldable of monoids into a single monoid. Again using List as an example, fold can be implemented as

fold [a, b, …, w] == a `mappend` b `mappend` … `mappend` w

which can be retrieved from foldMap:

foldMap id [a, b, …, w] == id a `mappend` id b `mappend` … `mappend` id w
                        == a `mappend` b `mappend` … `mappend` w

this shows how the identity fold = foldMap id is suggested.