From 5282eaa17f976edc5bb2e43127fa40ab413a1441 Mon Sep 17 00:00:00 2001
From: Viktor Dukhovni <ietf-dane@dukhovni.org>
Date: Sun, 3 Oct 2021 18:11:07 -0400
Subject: Explain Endo, Dual, ... in laws

---
 libraries/base/Data/Foldable.hs | 42 +++++++++++++++++++++++++++++++++++++++--
 1 file changed, 40 insertions(+), 2 deletions(-)

(limited to 'libraries')

diff --git a/libraries/base/Data/Foldable.hs b/libraries/base/Data/Foldable.hs
index 57ffcfa98a..21fe7cc72d 100644
--- a/libraries/base/Data/Foldable.hs
+++ b/libraries/base/Data/Foldable.hs
@@ -2355,14 +2355,51 @@ elements in a single pass.
 -- $laws
 -- #laws#
 --
--- @Foldable@ instances are expected to satisfy the following laws:
+-- The type constructor 'Endo' from "Data.Monoid", associates with each type
+-- __@b@__ the __@newtype@__-encapulated type of functions mapping __@b@__ to
+-- itself.  Functions from a type to itself are called /endomorphisms/, hence
+-- the name /Endo/.  The type __@Endo b@__ is a 'Monoid' under function
+-- composition:
+--
+-- > newtype Endo b = Endo { appEndo :: b -> b }
+-- > instance Semigroup Endo b where
+-- >     Endo f <> Endo g = Endo (f . g)
+-- > instance Monoid Endo b where
+-- >     mempty = Endo id
+--
+-- For every 'Monoid' m, we also have a 'Dual' monoid __@Dual m@__ which
+-- combines elements in the opposite order:
+--
+-- > newtype Dual m = Dual { getDual :: m }
+-- > instance Semigroup m => Semigroup Dual m where
+-- >     Dual a <> Dual b = Dual (b <> a)
+-- > instance Monoid m => Monoid Dual m where
+-- >     mempty = Dual mempty
+--
+-- With the above preliminaries out of the way, 'Foldable' instances are
+-- expected to satisfy the following laws:
+--
+-- The 'foldr' method must be equivalent in value and strictness to replacing
+-- each element __@a@__ of a 'Foldable' structure with __@Endo (f a)@__,
+-- composing these via 'foldMap' and applying the result to the base case
+-- __@z@__:
 --
 -- > foldr f z t = appEndo (foldMap (Endo . f) t ) z
 --
+-- Likewise, the 'foldl' method must be equivalent in value and strictness
+-- to composing the functions __@flip f a@__ in reverse order and applying
+-- the result to the base case:
+--
 -- > foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
 --
+-- When the elements of the structure are taken from a 'Monoid', the
+-- defintion of 'fold' must agree with __@foldMap id@__:
+--
 -- > fold = foldMap id
 --
+-- The 'length' method must agree with a 'foldMap' mapping each element to
+-- __@Sum 1@__ (The 'Sum' type abstracts numbers as a monoid under addition).
+--
 -- > length = getSum . foldMap (Sum . const 1)
 --
 -- @sum@, @product@, @maximum@, and @minimum@ should all be essentially
@@ -2376,7 +2413,8 @@ elements in a single pass.
 -- > sum = foldl' (+) 0
 -- > product = foldl' (*) 1
 --
--- If the type is also a 'Functor' instance, it should satisfy
+-- If the 'Foldable' structure has a 'Functor' instance, then for every
+-- function __@f@__ mapping the elements into a 'Monoid', it should satisfy:
 --
 -- > foldMap f = fold . fmap f
 --
-- 
cgit v1.2.1