Identity of the "accumulating parameter" of the foldr function

Question

the foldr function:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr func acc []      = acc
foldr func acc (x:xs)  = func x (foldr func acc xs)

catches patterns like those (left side) and makes them simpler (right side)

sum :: [Integer] -> Integer       |  sum :: [Integer] -> Integer
sum [] = 0                        |  sum [] = 0
sum (x:xs) = x + sum xs           |  sum (x:xs) = foldr (+) 0 xs
                                  |
product :: [Integer] -> Integer   |  product :: [Integer] -> Integer
product [] = 0                    |  product [] = 0
product (x:xs) = x * product xs   |  product (x:xs) = foldr (*) 1 xs
                                  |
concat :: [[a]] -> [a]            |  concat :: [[a]] -> [a]
concat [] = []                    |  concat [] = []
concat (x:xs) = x ++ concat xs    |  concat (x:xs) = foldr (++) [] xs
----------------------------------------------------------------------
       not using folds            |           using folds 

one thing I noticed was that the acc argument, provided as input for the fold, seems to be exactly the neutral element / identity element of that function.

In Mathematics the neutral element of the addition operation + is 0
because n + 0 = n, n ∈ ℝ

it doesn't change anything, in other words: With this neutral element provided as an input for the addition function, the summand equals the sum.

(+) summand 0 = summand or summand + 0 = summand

The same goes for multiplication, the product of the factor and the identiy equals the factor itelf:

(*) factor 1 = factor

So is this just a coincidence or is there someting bigger behind ?

Answer 1

You're exactly right. We very often want to pass an "identity"-like element to foldr, so that the "starting point" doesn't affect the result at all. In fact, this is codified in Haskell with the Monoid typeclass. A monoid is an associative binary operation with an identity. The examples you provide are all examples of a monoid, and they all exist in Haskell.

• + on any Num is codified as a monoid over the Sum newtype.
• * on any Num is codified as a monoid over the Product newtype.
• ++ on any list is codified as a monoid on [a].

And in fact we can go one step further. Folding over a monoid is such a common practice that we can do it automatically with fold (or foldMap, if you need to disambiguate). For instance,

import Data.Foldable
import Data.Monoid

sum :: Num a => [a] -> a
sum = getSum . foldMap Sum

product :: Num a => [a] -> a
product = getProduct . foldMap Product

concat :: [[a]] -> [a]
concat = fold

If you look in the source for Foldable, you can see that fold and foldMap are actually defined in terms of foldr on a monoid, so this is doing the exact same thing you just described.

You can find the full list of (built-in) Monoid instances on Hackage, but a few others that you might find of interest:

• || on Booleans is a monoid with the Any newtype.
• && on Booleans is a monoid with the All newtype.
• Function composition is a monoid with the Endo newtype (short for "endomorphism")

As an exercise, you might consider trying to pinpoint the identity of each of these operations.