What does the type foldMap :: (Monoid m) => (a -> m) -> f a -> m mean and how to implement it?

Question

Can someone explain what the type mean and how to implement this?

class Foldable f where
  foldMap :: (Monoid m) => (a -> m) -> f a -> m

Based on https://hackage.haskell.org/package/base-4.9.1.0/docs/Data-Foldable.html#v:foldMap, they explained it as "Map each element of the structure to a monoid, and combine the results." but I don't quite understand what it means. How can I map an element to the structure of a Monoid?

I tried foldMap f = mconcat . (<$>) f but I got this error:

 • Couldn't match type ‘f’ with ‘[]’
      ‘f’ is a rigid type variable bound by
        the class declaration for ‘Foldable’
        at traversable.hs:41:16
      Expected type: f a -> m
        Actual type: [a] -> m
    • In the expression: mconcat . (<$>) f
      In an equation for ‘foldMap’: foldMap f = mconcat . (<$>) f
    • Relevant bindings include
        foldMap :: (a -> m) -> f a -> m (bound at traversable.hs:45:3)

I tried @WillemVanOnsem's code and got this error:

error:
    • Could not deduce (Data.Foldable.Foldable f)
        arising from a use of ‘foldr’
      from the context: Foldable f
        bound by the class declaration for ‘Foldable’
        at traversable.hs:41:7-14
      or from: Monoid m
        bound by the type signature for:
                   foldMap :: forall m a. Monoid m => (a -> m) -> f a -> m
        at traversable.hs:42:14-47
      Possible fix:
        add (Data.Foldable.Foldable f) to the context of
          the type signature for:
            foldMap :: forall m a. Monoid m => (a -> m) -> f a -> m
          or the class declaration for ‘Foldable’
    • In the expression: foldr (\ x -> mappend (f x)) mempty
      In an equation for ‘foldMap’:
          foldMap f = foldr (\ x -> mappend (f x)) mempty

Flin

With the function a -> m. This sometimes is just an id. – Twitt

You can implement foldMap f here as foldr (\x -> mappend (f x)) mempty. Note that a Foldable does not imply a Functor. – Twitt

@WillemVanOnsem I tried that but I got the error (edited in my post) instead. – Flin

you forgot to add Foldable type constraint in the signature. – Twitt

Answer 1

they explained it as "Map each element of the structure to a monoid, and combine the results." but I don't quite understand what it means. How can I map an element to the structure of a Monoid?

We do that with the function with signature a -> m. So we define the "mapping" function ourself.

A monoid [wiki] is an algebraic structure. It is in essence a 3-tuple (S, ⊕, s₀) where S is the set of values, ⊕ :: S × S → S is an associative binary operator, and s₀ is an identity element, such that s₀ ⊕ s = s ⊕ s₀ = s.

Types that are members of the Foldable class are data structures that can be "folded". It means that if you for example have a Tree that contains Ints, so a Tree Int, such that you, for a function f :: Int -> Int -> Int, and a neutral element z, you can derive an Int.

By using foldMap we will call a function f :: a -> m on these elements, and use the monoid function ⊕ to "fold" the values. For data structures that implement Functor as well, it is thus, more or less equivalent to foldMap f = foldr mappend mempty . fmap f.

We can however use the f in the foldr function itself, like:

foldMap' :: (Foldable f, Monoid m) => (a -> m) -> f a -> m
foldMap' f x = foldr (\y -> mappend (f y)) mempty x

or shorter:

foldMap' :: (Foldable f, Monoid m) => (a -> m) -> f a -> m
foldMap' f = foldr (mappend . f) mempty

Here we thus first pre-process the values in the datastructure with f to convert these to a monoid object, and we call mappend as folding function on these items.

Twitt

Answer 2

So you have the following signature: foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m. Let's go step by step

The constraints:

a Monoid is data which can be combine by some operation. You can get many examples if you think a while. Just to mention here:

• Integer as data and + as the operation. The elements 1 and 2 can be combine giving 3 = 1 + 2.
• Integer as data and * as the operation. The elements 1 and 2 can be combine giving 2 = 1 * 2.
• List as data and ++ as the operation. The elements [1,2] and [2,3] can be combine giving [1,2,2,3] = [1,2] ++ [2,3].
• Vector of size 2 as data and + as the operation. The elements <1,2> and <4,5> can be combine giving <5,7> = <1,2> + <4,5>.
• etc..

All of the examples above have a Monoid representation in haskell, tipically defined using newtype or data key words. In haskell the monoid operation is represented as <>.

An important property is that monoids have a neutral element and are associative. In the context of Integer under + the neutral element is 0 an associativity is given by the fact that (a + b) + c = a + (b + c). You can easily find this properties in all given examples. Try out!

The Foldable constraint is easier. Essentially, you can summarize a Foldable data structure into one single value.

The function parameters

Code worths thousand words so...

foldMap :: (Monoid m, Foldable f) => (a -> m) -> f a -> m
--          ^^^^^^^^^^^^^^^^^^^^     ^^^^^^^     ^^^
--          |- We've seen this       |           |
--                                   |           |- A 'Set' of a's which can be collapse into a single value
--                                   |- A function to convert a's into a monoid

So by definition you can easily follow this reasoning/algorithim:

Premises

1. I have a Structure of elements which can be collapse into a single value
2. I have a way to convert this elements into a monoid's element
3. Monoids have a neutral element
4. Two monoids element can be combine together

Algorithim

• collapse elements of the structure by combining them using the monoid operator
• if the structure is empty use the neutral element as the result.

very fancy but... I'm still not getting It

The problem is that when you define an instance of Foldable, you haven't define yet how to fold the structure, and that's different for each one!. As in Willem's answer, you can define foldMap in terms of foldr, meaning that foldr is defining the way you can collapse your structure. Viceversa is also true: you can define foldr in terms of foldMap, and probably that's the gotcha!! if you haven't defined foldr, there isn't a universal way to implement foldMap, It'll depends on your data structure. So as a code-sumary:

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m -- A default instance can be provided if you define foldr (a.k.a a way to collapse the structure)
  foldr   :: (a -> b -> b) -> b -> t a -> b  -- A default instance can be provided if you define foldMap (a.k.a a way to collapse the structure into a monoid element)
  -- but if you don't provide at least one, It'll be impossible to implement any
  -- because you aren't telling me how to collapse the structure!!

Codification

very concise explanation and thanks for including the definition of foldr – Flin