On Saturday 28 May 2011 22:37:45, Patrick LeBoutillier wrote:
Hi,
I'm reading the LYAH book and on page 263 it says that if you define Data.Foldable.foldMap you get Data.Foldable.foldl and Data.Foldable.foldl for "free". The default implementation code of Data.Foldable.foldr is:
foldr :: (a -> b -> b) -> b -> t a -> b foldr f z t = appEndo (foldMap (Endo . f) t) z
I don't understand this code, but more specifically I don't get how there can a Monoid constraint on foldMap's return type and not on foldr/foldl.
Can any one explain what Endo is and how it works?
newtype Endo a = Endo { appEndo :: a -> a } So an (Endo a) is a wrapped function (a -> a), an endomorphism of a (in the category Hask; ignore this if you don't know what that means). The type of f in foldr is f :: a -> b -> b = a -> (b -> b), hence (f x) :: (b -> b) and Endo . f :: a -> Endo b and there is a Monoid instance for (Endo b) (mempty is (Endo id), (Endo g) `mappend` (Endo h) = Endo (g . h)), so (Endo . f) is a suitable argument for foldMap. foldMap (Endo . f) t builds an endomorphism of b [wrapped in the newtype], which is then unwrapped by appEndo to yield a function (b -> b) which finally is applied to the supplied element z of b. Without the wrapper and for lists: foldr f z [1,2,3] ~> f 1 (foldr f z [2,3]) === (f 1) (foldr f z [2,3]) ~> (f 1) ((f 2) (foldr f z [3])) = ((f 1) . (f 2)) (foldr f z [3]) ~> ((f 1) . (f 2)) ((f 3) (foldr f z [])) ~> ((f 1) . (f 2) . (f 3)) (foldr f z []) ~> ((f 1) . (f 2) . (f 3)) z The composition (f 1) . (f 2) . (f 3) is what foldMap builds [modulo the wrapper Endo, with the wrapper it is Endo (f 1) `mappend` Endo (f 2) `mappend` Endo (f 3) = Endo ((f 1) . (f 2) . (f 3)) which is then unwrapped by appEndo].
Thanks a lot,
Patrick