<div dir="ltr">+1<br></div><br><div class="gmail_quote"><div dir="ltr">On Fri, Jun 8, 2018 at 9:20 AM Andrew Martin <<a href="mailto:andrew.thaddeus@gmail.com">andrew.thaddeus@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">I propose adding another method to the Foldable typeclass: foldMap'<div><br></div><div>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 <a href="https://gist.github.com/andrewthad/f79b7022725532baf709514cf08c3955" target="_blank">https://gist.github.com/andrewthad/f79b7022725532baf709514cf08c3955</a>):</div><div><br>  {-# LANGUAGE BangPatterns #-}<br>  {-# OPTIONS_GHC -O2 #-}<br>  import Gauge<br>  import Data.Foldable<br>  import qualified Data.Set as S<br>  </div><div>  foldMap' :: (Monoid m, Foldable f) => (a -> m) -> f a -> m<br>  foldMap' f = foldl' (\ !acc a -> acc <> f a) mempty<br><br></div><div>  numbers :: [Int]</div><div>  numbers = [1..4000]<br>  </div><div>  intToSet :: Int -> S.Set Int<br>  intToSet i = S.singleton (mod i 10)</div><div><br></div>  main :: IO ()<br>  main = defaultMain<br>    [ bench "lazy" $ whnf (foldMap intToSet) numbers<br>    , bench "strict" $ whnf (foldMap' intToSet) numbers<br>    ]<div><div><br></div><div>Here are the results we get from running this:</div><div><br></div><div><div>  benchmarked lazy</div><div>  time                 178.8 μs   (176.1 μs .. 183.1 μs)</div><div>                       0.996 R²   (0.993 R² .. 0.998 R²)</div><div>  mean                 180.8 μs   (179.1 μs .. 183.3 μs)</div><div>  std dev              7.242 μs   (5.856 μs .. 9.304 μs)</div><div>  variance introduced by outliers: 20% (moderately inflated)</div><div><br></div><div>  benchmarked strict</div><div>  time                 108.4 μs   (106.1 μs .. 111.0 μs)</div><div>                       0.997 R²   (0.996 R² .. 0.999 R²)</div><div>  mean                 107.9 μs   (107.0 μs .. 109.3 μs)</div><div>  std dev              3.672 μs   (2.451 μs .. 6.220 μs)</div><div>  variance introduced by outliers: 15% (moderately inflated)</div></div><div><br></div><div>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.</div><div><br></div>-- <br><div class="m_-5534876241638450703gmail_signature">-Andrew Thaddeus Martin</div>
</div></div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote></div>