[Haskell-cafe] A clarification about what happens under the hood with foldMap
Hi Cafe, I was playing with the classic example of a Foldable structure: Trees. So the code you can find both on Haskell Wiki and LYAH is the following: data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Eq) instance Foldable Tree where foldMap f Empty = mempty foldMap f (Node l p r) = foldMap f l `mappend` f p `mappend` foldMap f r treeSum :: Tree Int -> Int treeSum = Data.Foldable.foldr (+) 0 What this code does is straighforward. I was struck from the following sentences in LYAH: Notice that we didn't have to provide the function that takes a value and > returns a monoid value. > We receive that function as a parameter to foldMap and all we have to > decide is where to apply > that function and how to join up the resulting monoids from it. This is obvious, so in case of (+) f = Sum, so f 3 = Sum 3 which is a Monoid. What I was wondering about is how Haskell knows that it has to pass, for example, Sum in case of (+) and Product in case of (*)? In other term, I'm missing the logical piece of the puzzle which maps the associative binary function passed to fold up to our foldMap declaration. Thanks for any explanation :) Cheers, A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A clarification about what happens under the hood with foldMap
-- Forwarded message -- From: Alfredo Di Napoli Date: 23 October 2012 10:35 Subject: Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap To: Chaddaï Fouché 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"? I hope to have been clearer, don't know if I'm missing something crucial, though :) Thanks, A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] A clarification about what happens under the hood with foldMap
> I was playing with the classic example of a Foldable structure: Trees. > So the code you can find both on Haskell Wiki and LYAH is the following: > > data Tree a = Empty | Node (Tree a) a (Tree a) deriving (Show, Eq) > > instance Foldable Tree where > foldMap f Empty = mempty > foldMap f (Node l p r) = foldMap f l `mappend` f p `mappend` foldMap f r > > treeSum :: Tree Int -> Int > treeSum = Data.Foldable.foldr (+) 0 > > > What this code does is straighforward. I was struck from the following > sentences in LYAH: > > Notice that we didn't have to provide the function that takes a value and > > returns a monoid value. > > We receive that function as a parameter to foldMap and all we have to > > decide is where to apply > > that function and how to join up the resulting monoids from it. > > This is obvious, so in case of (+) f = Sum, so f 3 = Sum 3 which is a > Monoid. > What I was wondering about is how Haskell knows that it has to pass, for > example, Sum in case of (+) and Product in case of (*)? Hopefully the following paradox helps: > treeDiff :: Tree Int -> Int > treeDiff = Data.Foldable.foldr (-) 0 > > t1 = treeDiff (Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty)) This works just as well. You might be surprised: after all, there is no Diff monoid that corresponds to (-). In fact, there cannot be since (-) is not associative. And yet treeDiff type checks and even produces some integer when applied to a tree. What gives? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap
Le 23 oct. 2012 09:54, "Alfredo Di Napoli" a écrit : > > What this code does is straighforward. I was struck from the following sentences in LYAH: > >> Notice that we didn't have to provide the function that takes a value and returns a monoid value. >> We receive that function as a parameter to foldMap and all we have to decide is where to apply >> that function and how to join up the resulting monoids from it. > > > This is obvious, so in case of (+) f = Sum, so f 3 = Sum 3 which is a Monoid. > What I was wondering about is how Haskell knows that it has to pass, for example, Sum in case of (+) and Product in case of (*)? > In other term, I'm missing the logical piece of the puzzle which maps the associative binary function passed to fold up to our foldMap declaration. Haskell doesn't know it has to pass anything ! As the doc said, this is a parameter to foldmap : so you would use "treeSum = foldmap Sum" for example. And the binary function associed would be determined by the monoid instance. Here that would be (+) because that's what mappend is for Sum (or rather for Sum Int). -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap
On Tue, Oct 23, 2012 at 10:36 AM, Alfredo Di Napoli wrote: > 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"? > > I hope to have been clearer, don't know if I'm missing something crucial, > though :) Sorry I misunderstood your first post. The answer is that Haskell doesn't have oracular powers so it doesn't know to choose Sum if you pass (+) and Product if you pass (*), it especially doesn't have one kind of monoid for each possible operation you can pass to foldr... So it proceeds otherwise. It's pretty obvious that foldr can be implemented with foldMap, if only by using the list monoid then using the list foldr but the actual default implementation does it more efficiently and more directly instead, you should probably look at the source ( http://www.haskell.org/ghc/docs/latest/html/libraries/base-4.6.0.0/src/Data-Foldable.html ) then investigate the endomorphism monoid. -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap
Thanks guys, I'll work my way through Oleg's paradox as well as what you just said Chaddai. I'm very busy right now, but I'll probably come back to you tomorrow morning, when I'll have an hour to think freely :) Cheers, A. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap
> From: Alfredo Di Napoli > Subject: [Haskell-cafe] A clarification about what happens under the > hoodwith 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
Re: [Haskell-cafe] A clarification about what happens under the hood with foldMap
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 wrote: > > From: Alfredo Di Napoli > > Subject: [Haskell-cafe] A clarification about what happens under the > > hoodwith 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
