Writing foldMap in Haskell
I am trying to write my own foldMap function as excersice to learn Haskell
It currently looks like
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 compiled, 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 is wrong with my fold?
source to share
Maybe we should answer the actual solution:
Hopefully it is 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 have already given you a high level explanation, but perhaps I can give you another look at it:
Let's just follow types to omit this answer:
We need a function f a -> m
, where m
is a monoid and f
is a functor. In addition, we have a function g :: a -> m
that we can use to get from some a
to a monoid - nice.
Now we get some additional functionality:
-
fold :: f m -> m
from our own class -
fmap :: (a -> b) -> f a -> f b
from Functorf
So, we need f a -> m
, if only a
to be m
, then we could use fold
... dang.
But wait: we can do a
in m
with g
, but a
packaged in f
... dang.
Oh wait: we can do f a
in f m
with fmap
.... ding-ding-ding
So let's do this:
- do
f a
inf m
:fmap g a
- use a fold on it:
fold (fmap g a)
or using $
:
foldMap g a = fold $ fmap g a
Example
Let's get something for us to 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 Sum
and [1..4]
:
λ> foldMap Sum [1..4]
Sum {getSum = 10}
which seems beautiful to me.
source to share
Monoid has two functions: mappend
and mempty
, and instead mappend
you can use (<>)
.
Typeclasses work because the compiler inserts the appropriate function definition depending on the data types, so (fortunately) there is no need to pass that function.
The mistake you made is to unnecessarily pass the Monoid functions you are using.
For example, if I defined a function to check if something was in the list, for example:
isin :: Eq a => a -> [a] -> Bool
isin equalityFunction a list = any (equalityFunction a) list
I would accidentally try passing equalityFunction
as an argument and the type signature doesn't match it.
Instead, I must define
isin :: Eq a => a -> [a] -> Bool
isin a list = any (== a) list
using the standard name for the equality function as defined in the class Eq
.
Likewise, you do not need or need to pass arguments (<>)
or empty
.
source to share