Writing a foldMap in Haskell

Question

I am trying to write my own foldMap function as an excersice to learn Haskell

Currently it looks like this

class Functor f => Foldable f where
    fold    :: Monoid m =>             f m -> m
    foldMap :: Monoid m => (a -> m) -> f a -> m
    foldMap g a = fold (<>) mempty (fmap g a)

However when compiling it it gives the following error

Could not deduce (Monoid ((f m -> m) -> fm -> m)) arising from use of 'fold'
from the context (Foldable f) bound by the class declaration for 'Foldable' at (file location)
or from (Monoid m) bound by the type signature for foldMap :: Monoid m => (a -> m) -> f a -> m at (file location
In the expression fold (<>) mempty (fmap g a)
In an equation for 'foldMap':
     foldMap g a = fold (<>) mempty (fmap g a)

I can't figure out what the compiler is trying to tell me with this error, can anyone tell me what goes wrong with my foldMap?

Answer 1

Maybe we should do an answer with the actual solution:

I hope it's now clear, that this is a possible definition:

class Functor f => Foldable f where
    fold    :: Monoid m =>             f m -> m
    foldMap :: Monoid m => (a -> m) -> f a -> m
    foldMap g a = fold $ fmap g a

follow the types

Andrew and Lee already gave you a high level explanation but maybe I can give you another view on it:

Let's just follow the types to oget to this answer:

We want a function f a -> m where m is a monoid and f is a functor. In addition we have a function g :: a -> m we can use to get from some a into the monoid - nice.

Now we get some additional functions:

• fold :: f m -> m from our own class
• fmap :: (a -> b) -> f a -> f b from the Functor f

Ok we need f a -> m now if only the a would be an m then we could use fold ... dang.

But wait: we can make a a into a m using g- but the a is packed into f ... dang.

Oh wait: we can make a f a into a f m using fmap .... ding-ding-ding

So let's do it:

• make f a into f m: fmap g a
• use fold on it: fold (fmap g a)

or using $:

foldMap g a = fold $ fmap g a

example

Let's get something so we can try:

module Foldable where

import Data.Monoid

class Functor f => Foldable f where
    fold    :: Monoid m => f m -> m
    foldMap :: Monoid m => (a -> m) -> f a -> m
    foldMap g a = fold $ fmap g a

instance Foldable [] where
  fold []     = mempty
  fold (x:xs) = mappend x (fold xs)

here is a simple example using this with Sum and [1..4]:

λ> foldMap Sum [1..4]
Sum {getSum = 10}

which seems fine to me.