Haskell Foldable tree mempty implementation

Question

Hi I need help in understanding this Foldable tree implementation from from here

Consider the following

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 x l r) = F.foldMap f l `mappend`  
                             f x           `mappend`  
                             F.foldMap f r

I have difficulty in understanding how in this example, mempty and mappend get their implementation what their types and how they infered from for example the following invokation.

F.foldl (+) 0 testTree

Thanks

In essence `foldl` will create an "ad hoc" monoid with `(+)` as the `mappend` here and `0` as the `mempty`. — Willem Van Onsem, Apr 26 '23 at 17:46
@WillemVanOnsem Thanks, is there any link with source code explaining how it does it under the hood? — Boris, Apr 26 '23 at 18:16
this might explain it: https://stackoverflow.com/q/47576620/67579 — Willem Van Onsem, Apr 26 '23 at 18:19
@WillemVanOnsem Amazing :) 5 years ago the same question with the same example. — Boris, Apr 26 '23 at 18:21
Also related (and also about that LYAH example): [*Foldr/Foldl for free when Tree is implementing Foldable foldMap?*](https://stackoverflow.com/q/23319683/2751851) — duplode, Apr 26 '23 at 21:28

score 2 · Answer 1 · answered Apr 26 '23 at 16:50

2

Check out the signature of foldMap:

foldMap :: Monoid m => (a -> m) -> t a -> m

See the Monoid m => constraint in there? It means that every time somebody calls foldMap, they have to choose a type m and provide an instance of Monoid for that type.

It's from that instance that mempty and mappend are coming. Since foldMap has been provided an instance of Monoid, it can call methods from that instance.

answered Apr 26 '23 at 16:50

Fyodor Soikin

78,590
9
125
172

Thanks, but I am missing the link on how fold create the concrete instance of monoid – Boris Apr 26 '23 at 18:19
2

@Boris `foldMap` does not choose the monoid, the caller does. In practice, if you write `foldMap f x :: MyMonoidType`, annotating the call with an explicit monoid type of your choice, Haskell will use the corresponding monoid operations. This is not the only option, for instance the type `MyMonoidType` can often be inferred: `True : foldMap f x` will choose `[Bool]` as the monoid even without an explicit type annotation. – chi Apr 26 '23 at 19:51

Haskell Foldable tree mempty implementation

1 Answers1