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 ?

Your translation table is actually wrong. You don't need the [] vs (x:xs) case distinction, only one clause sum xs = foldr (+) 0 xs. — leftaroundabout
(Also, you'd used foldl' instead of foldr, but that's more of a performance detail.) — leftaroundabout
It is not a coincidence. You need some "neutral" initial element to start with something. But nothing prevents you to write something like sumPlus5 = foldr 5 — Denys Prodan
Also, the mempty element for Product (that is, the identity argument for multiplication) is 1, not 0. — Yann Vernier

Silvio Mayolo Silvio Mayolo · Accepted Answer · 2018-07-31T16:17:27

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.

Identity of the "accumulating parameter" of the foldr function

1 Answers