某所の「すごいHaskell本」輪読会で「第12章モノイド」を読む予定があり、予習しています。第12章の中で、「Foldableクラスでは、foldMapを用意すれば、foldl/foldrが使えるようになる」との説明があるのですが、foldMapからfoldl/foldrを構成する具体的な方法が記載されておらず、ひじょーに気持ち悪かったので、自分なりの解説を用意しました。（foldlも本質的には同じはず・・・ですが、説明が簡単なfoldrの方で解説しています。）
事前の考察
Foldableクラスのインスタンスは、リストやTreeなど、一般に「値」の集合と考えることができます。若干、荒っぽい書き方で、
xs :: t a xs = {xi | i = 1,...,n}
は、「x1,...,xn」という値の集合からなるFoldableなデータとします。
この時、関数「f :: a -> (b -> b)」に対して、foldrは、次のように理解できます。
foldr f z xs = f x1 ( f x2 ( f x3 ... f xn z )...) = (f x1) . (f x2) . (f x3) ... . (f xn) z
すなわち、初期値「z :: b」をxsの各要素から生成される関数(f xi)で次々に変換していきます。この時、xiを並べる順番の決定ルールが、データの種類（リストなのかTreeなのか）に依存して決まります。
ここで、(f xi)の関数合成の列を抽象化するために、次のMonoidを導入します。
newtype Endo a = Endo { appEndo :: a -> a } instance Monoid (Endo a) where mempty = id mappend = (.)
これは、特定の型の上の関数について、関数合成を「和（mappend）」とするMonoidを構成しています。
すると、関数「f xi :: b -> b」をEndoに包んでMonoid化したもの「Endo (f xi) :: Endo b」を使うと、先の関数合成が「mappend」に抽象化されます。
foldr f z xs = f x1 ( f x2 ( f x3 ... f xn z )...) = (f x1) . (f x2) . (f x3) ... . (f xn) z = appEndo ( (Endo (f x1)) `mappend` (Endo (f x2)) `mappend` ... (Endo (f xn)) ) z = appEndo ( ((Endo . f) x1) `mappend` ((Endo . f) x2) `mappend` ... ((Endo . f) xn) ) z
言い換えると、xs = {xi} の各要素をMonoid化した集合 { (Endo . f) xi } を `mappend` で連結しています。この時、連結する順番がデータの種類（リストなのかTreeなのか）に依存して決まります。
foldMapからfoldrを構成する
ここでおもむろに、Foldableクラスのインスタンスが持つ、foldMapメソッドを思い出します。
class Foldable t where foldMap :: Monoid m => (a -> m) -> t a -> m
Treeの場合は、次のように定義されます。
instance Foldable Tree where foldMap f EmtpyTree = mempty foldMap f (Node x l r) = (foldMap f l) `mappend` (f x) `mappend` (fold Map f r)
これは、xsの各要素をMonoid化する手段「f :: a -> m」をfoldMapに与えると、xsの各要素をMonoid化したものを `mappend` で連結する方法を用意しているとみなせます。
・・・
えーと。。。
・・・・・・そう。
先のセクションの最後の式が、foldMapにぴったり適合しますね。
xsの各要素をMonoid化する手段として、「(Endo . f) xi」をfoldMapに与えると、ちょうど同じことになります。
foldr f z xs = f x1 ( f x2 ( f x3 ... f xn z )...) = (f x1) . (f x2) . (f x3) ... . (f xn) z = appEndo ( (Endo (f x1)) `mappend` (Endo (f x2)) `mappend` ... (Endo (f xn)) ) z = appEndo ( ((Endo . f) x1) `mappend` ((Endo . f) x2) `mappend` ... ((Endo . f) xn) ) z = appEdno (foldMap (Endo . f) xs) z
というわけで、一般にfoldMapが用意されているインスタンスというのは、foldMapによって、各要素を並べる順番決めのルールが用意されてるとみなせて、次の式で、自然にfoldrを定義することができるというわけです。
foldr f z xs = appEnd (foldMap (Endo . f) xs) z
