Andrew Martin

2018-06-08 13:20:11 UTC

I propose adding another method to the Foldable typeclass: foldMap'

This has the same behavior as foldMap except that it is strict in the

accumulator. This can lead to considerable performance gains when the user

knows that monoidal append is strict both arguments. Consider the following

example (available as a gist at

https://gist.github.com/andrewthad/f79b7022725532baf709514cf08c3955):

{-# LANGUAGE BangPatterns #-}

{-# OPTIONS_GHC -O2 #-}

import Gauge

import Data.Foldable

import qualified Data.Set as S

foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m

foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty

numbers :: [Int]

numbers = [1..4000]

intToSet :: Int -> S.Set Int

intToSet i = S.singleton (mod i 10)

main :: IO ()

main = defaultMain

[ bench "lazy" $ whnf (foldMap intToSet) numbers

, bench "strict" $ whnf (foldMap' intToSet) numbers

]

Here are the results we get from running this:

benchmarked lazy

time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)

0.996 RÂ² (0.993 RÂ² .. 0.998 RÂ²)

mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)

std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)

variance introduced by outliers: 20% (moderately inflated)

benchmarked strict

time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)

0.997 RÂ² (0.996 RÂ² .. 0.999 RÂ²)

mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)

std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)

variance introduced by outliers: 15% (moderately inflated)

These performance gains are considerable. It needs to be a method of

Foldable and not just a function written using foldl' for the same reason

that the lazy foldMap needs to be a method of Foldable. There are types for

which the default implementation can be improved upon. This is a

non-breaking change since there is a sensible default implementation.

This has the same behavior as foldMap except that it is strict in the

accumulator. This can lead to considerable performance gains when the user

knows that monoidal append is strict both arguments. Consider the following

example (available as a gist at

https://gist.github.com/andrewthad/f79b7022725532baf709514cf08c3955):

{-# LANGUAGE BangPatterns #-}

{-# OPTIONS_GHC -O2 #-}

import Gauge

import Data.Foldable

import qualified Data.Set as S

foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m

foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty

numbers :: [Int]

numbers = [1..4000]

intToSet :: Int -> S.Set Int

intToSet i = S.singleton (mod i 10)

main :: IO ()

main = defaultMain

[ bench "lazy" $ whnf (foldMap intToSet) numbers

, bench "strict" $ whnf (foldMap' intToSet) numbers

]

Here are the results we get from running this:

benchmarked lazy

time 178.8 ÎŒs (176.1 ÎŒs .. 183.1 ÎŒs)

0.996 RÂ² (0.993 RÂ² .. 0.998 RÂ²)

mean 180.8 ÎŒs (179.1 ÎŒs .. 183.3 ÎŒs)

std dev 7.242 ÎŒs (5.856 ÎŒs .. 9.304 ÎŒs)

variance introduced by outliers: 20% (moderately inflated)

benchmarked strict

time 108.4 ÎŒs (106.1 ÎŒs .. 111.0 ÎŒs)

0.997 RÂ² (0.996 RÂ² .. 0.999 RÂ²)

mean 107.9 ÎŒs (107.0 ÎŒs .. 109.3 ÎŒs)

std dev 3.672 ÎŒs (2.451 ÎŒs .. 6.220 ÎŒs)

variance introduced by outliers: 15% (moderately inflated)

These performance gains are considerable. It needs to be a method of

Foldable and not just a function written using foldl' for the same reason

that the lazy foldMap needs to be a method of Foldable. There are types for

which the default implementation can be improved upon. This is a

non-breaking change since there is a sensible default implementation.

--

-Andrew Thaddeus Martin

-Andrew Thaddeus Martin