How can I understand the laws for Folding?

Question

The page describing Data.Foldable 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

Endois a "monoid of endomorphisms in composition." appEndois a field of this type.

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

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

You can refer to endomorphism "as a technically correct term for functions, the input and output types are the same ( a -> a).

Endois an instance Monoidwith the composition:

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

---

To facilitate understanding of the law, use the list type as a specific 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

RHS :

   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)

mappend Endo - ,

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

, appEndo (…) z, z:

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

foldr .

---

foldl , Dual - , Dual a `mappend` Dual b == Dual (b `mappend` a) getDual . , foldl.

---

fold . List , fold

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

foldMap:

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

, fold = foldMap id.