> 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
