Is this a type of Haskell in action or something else?

Question

I work through the LYAH online book (the link will take you directly to the section that concerns my question).

The author defines the data type of the binary tree and shows how it can be made an instance of the Foldable type (defined in Data.Foldable) by implementing the foldMap function:

import Data.Monoid import qualified Data.Foldable as F data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) instance F.Foldable Tree where foldMap f Empty = mempty foldMap f (Node xlr) = F.foldMap fl `mappend` fx `mappend` F.foldMap fr 

A foldMap declaration is as follows:

 F.foldMap :: (Monoid m, F.Foldable t) => (a -> m) -> ta -> m 

therefore, a function is required that takes an instance of type "a" and returns a monoid.

Now, as an example, the author creates an instance of the tree

  testTree = Node 5 (Node 3 (Node 1 Empty Empty) (Node 6 Empty Empty) ) (Node 9 (Node 8 Empty Empty) (Node 10 Empty Empty) ) 

and performs the following fold (defined for Folding types):

 F.foldl (+) 0 testTree -- the answer is 42 (sum of the Node Integers) 

My question is, how does Haskell figure out that adding by type Integer - a Haskell request for type testTree gives Tree [Integer] - can be considered a monoid operation (if my terminology is correct)?

(My own attempt to answer: the author in the few paragraphs before this section describes how the Num type can be interpreted as the Monoid type in two different ways; by transferring them to the Sum and Product types with (+) and (*) as functions mappend and 0 and 1 as a mempty element, respectively. "a" in ( Tree a) somehow deduced as belonging to the type Sum (the way that Haskell interprets numerical values ​​differently according to context) or is it something else completely?]

Answer 1

My question is, how does Haskell figure out that adding by type Integer — a Haskell query for type testTree gives Tree [Integer] —can be considered a monoid operation (if my terminology is correct)?

Can not! In fact, there is no Monoid instance for Integer .

Now, don't get me wrong - integers are monoids when added. However, they are also monoids under multiplication, and Haskell has no way of knowing what to use, therefore, newtype wrappers.

But ... none of this happens here. Moving on ...

(My own attempt to answer: the author a few paragraphs before this section describes how the Num type can be interpreted as a monoid type in two different ways: by transferring them to the Sum and Product type using (+) and (*) as functions mappend and 0 and 1 as a mempty element, respectively. Is the type “a” in (Tree a) somehow deduced as belonging to the type Sum (since Haskell interprets numerical values ​​differently according to context) or is it completely different?]

Not a bad guess, but such a conclusion (finding an instance using Sum based on the arguments you gave) is beyond what Haskell can do for you.

There are two key points here - first of all, the Monoid restriction Monoid used only for certain functions, and not for folding in general. In particular, foldl does not actually need a Monoid instance Monoid all, because you provide a binary operation and an initial value to use it.

The second point is what I suspect you really need - how does it create a generic foldl that doesn't need Monoid , when all you define is foldMap , what does it do? To answer this, we can just look at the default implementation of foldl :

 foldl :: (a -> b -> a) -> a -> tb -> a foldl fzt = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

Here Endo is another newtype wrapper , especially for functions a -> a giving Monoid compositions with id as an identity, and Dual is a wrapper that changes the direction of Monoid . So he actually uses Monoid here, so he can glue using (+) along with the composition of the function, and then apply the result to the initial value.

Answer 2

The monoid is not actually used here. The last line uses F.foldl , which has the signature F.Foldable t => (a -> b -> a) -> a -> tb -> a . Mostly you use the monoid manually, supplying (+) and 0.

If you want to use the monoid "implicitly", you can use F.fold (which has a signature (F.Foldable t, Monoid m) -> tm -> m ). In this case, if you try, you will get:

 *Main> F.fold testTree <interactive>:1:1: No instance for (Monoid Integer) arising from a use of `F.fold' Possible fix: add an instance declaration for (Monoid Integer) In the expression: F.fold testTree In an equation for `it': it = F.fold testTree *Main> :t F.foldl 

GHCI now complains that there is no Monoid instance for Integer, as it should be. You must select Sum or Product by wrapping Integer up. To do this, we can use F.foldMap (signature (F.Foldable t, Monoid m) => (a -> m) -> ta -> m ):

 *Main> F.foldMap Sum testTree Sum {getSum = 42}