5

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?

user28522
  • 311
  • 1
  • 7
  • 1
    Related: [*Foldr/Foldl for free when Tree is implementing Foldable foldmap?*](http://stackoverflow.com/q/23319683/2751851) (my answer there covers the same ground as kennytm's answer here, but tells the story in a somewhat different way.) – duplode Apr 27 '17 at 03:18

1 Answers1

9

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.

kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
  • so `Endo a` is the set consisting of endo-maps from a to a? – user28522 Apr 27 '17 at 16:47
  • 2
    @user28522 Yes, up to isomorphism. Note that in types, `Endo a` is the type of such maps, while in terms (programs/expressions) `Endo` is the name of the isomorphism `(a->a) -> Endo a`, while `appEndo` is its inverse iso. – chi Apr 27 '17 at 17:58
  • I still don't understand: "...... is the name of the isomorphism (a->a) -> Endo a, while appEndo is its inverse iso.". Please point me to the places where I can look up for more information to understand what you said. Thx. – user28522 Apr 27 '17 at 18:31