Thanks guys for the clarification, this blowed my mind a bit :P As far as I understood, is that my initial thought about Sum and Product was wrong; in fact, they don't even participate to the party! This is confirmed by the Oleg's paradox about (-). What really happens is that Endo (which I guess is the endofunctor, so a functor from X to X itself) act as a "semantic bridge" between the operation to perform (+,* or whatever) and our foldable structure. Have I got the gist?
Thanks a lot! A. On 24 October 2012 02:22, John Lato <jwl...@gmail.com> wrote: > > From: Alfredo Di Napoli <alfredo.dinap...@gmail.com> > > Subject: [Haskell-cafe] A clarification about what happens under the > > hood with foldMap > > > > I'm sure I'm missing a point, but the "minimum" definition for a Foldable > > instance is given in terms of foldMap, so I get the cake for free, foldr > > included, right? > > In the example I have defined my treeSum as: > > > > treeSum = Data.Foldable.foldr (+) 0 > > > > So the only thing Haskell knows it that I want to fold over a Foldable > for > > which foldMap (and therefore foldr) is defined, and specifically I want > to > > fold using (+) as function. > > But foldMap is defined in terms of f, which in this case is Sum, because > I > > want to sum things. It it were (*) f would have been Product, right? > > > > So what I'm missing is the relation between foldMap and foldr, aka "How > > Haskell infer from (+) that I want f = Sum and not something different"? > > What you're missing is that this isn't how foldr is defined. As you > probably suspect, it isn't possible for Haskell to deduce "f = Sum" > from just the function. And in general the function parameter to > foldr isn't even equivalent to mappend for any monoid, because it > operates on two values with different types. Rather, foldr is defined > using the Endo monoid, which is > > > newtype Endo a = Endo (a -> a) > > instance Monoid (Endo a) where > mempty = id > mappend = (.) > > Here's the default instance of Data.Foldable.foldr > > > foldr :: (a -> b -> b) -> b -> t a -> b > > foldr f z t = appEndo (foldMap (Endo . f) t) z > > What happens is that, as the tree is traversed, Leaf constructors are > replaced with 'id' (mempty :: Endo b), and branch values are replaced > with 'Endo . f', where f = (+) in this example. Look at Endo . f: > > -- Endo :: (b -> b) -> Endo b > -- f :: a -> (b -> b) > -- Endo . f :: a -> Endo b > > so at each branch (Endo . f) is applied to the value, resulting in the > type 'Endo b' > > foldMap just composes everything together with mappend, which, after > the Endo constructor is removed, is a giant function pipeline :: b -> > b, which is then applied to the provided base value (0 here). > > John L. >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe