> 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

[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe