Data.Foldable causes missed foldr/build opportunities

Gabriel Gonzalez gabriel439 at
Thu Jul 25 20:32:36 CEST 2013

On 07/25/2013 11:22 AM, Edward Kmett wrote:
> In your case here mapM_ f would turn into Foldable.foldr ((>>) . f) 
> (return ()) if it were to inline (which it isn't set up to do) rather 
> than into Control.Monad.mapM_. Once it became Foldable.foldr it'd get 
> stuck on the way to becoming GHC.List.foldr and then to fusion by the 
> fact that we don't inline the members of the Foldable [] instance.
> As an aside, it is interesting that in 
> the 
> traverse is INLINE'd but not the mapM, though it is irrelevant to your 
> issue here, it is another thing that would likely be impacted.
> So there appears to be at least two obstacles in the way of this 
> fusing away properly, and yet another in the way of normal mapM fusing.
> Some of this could be mitigated by rephrasing the foldr/build rule 
> directly in terms of Foldable.foldr where it'd only typecheck if 
> applied to a [] anyways, but it does look like a serious look will 
> have to be made at what gets inlined as we proceed to investigate how 
> to get this to work right.

If I understand what you are saying then I tried something similar to 
this, too, where I provided a rewrite rule that would only rewrite if it 

_each :: (Monad m) => [a] -> Producer a m ()
_each = Prelude.mapM_ yield

{-# RULES "_each" each = _each #-}

If I do this GHC spits out a big internal debug message when I compile 
it.  It does compile successfully, but it doesn't work and that rewrite 
rule does not fire.

I think the most reliable way will just be making sure that there is a 
clear chain of INLINEs all the way down.

> -Edward
> On Thu, Jul 25, 2013 at 1:55 PM, Gabriel Gonzalez 
> <gabriel439 at <mailto:gabriel439 at>> wrote:
>     On 07/25/2013 10:41 AM, Edward Kmett wrote:
>>     One of the open concerns about it is definitely ensuring that we
>>     get the fusion opportunities we can.
>>     If you put an INLINE pragma on your Foldable version of each do
>>     the fusion rules fire after it gets inlined into a call site that
>>     uses it as a list?
>     I tried both INLINE and INLINABLE and neither causes the fusion
>     rules to fire.  I also tried:
>     * adding an orphan SPECIALIZE rule for `Data.Foldable.mapM_` in
>     the module where I defined `each`
>     * Specializing the type of `each` to consume lists, but still
>     using the `Foldable` `mapM_`
>     * Defining a new copy of `each` (using the `Foldable` version) in
>     the same module as the code that uses it, specializing the type
>     signature to lists, and trying out INLINE/INLINABLE or no pragma.
>     None of those causes the rule to fire, either.
>>     -Edward
>>     On Thu, Jul 25, 2013 at 1:22 PM, Gabriel Gonzalez
>>     <gabriel439 at <mailto:gabriel439 at>> wrote:
>>         I'm now in favor of the `Data.Foldable` proposal, but I just
>>         wanted to mention that the proposal needs to include some
>>         extra pragma work to ensure that build/foldr optimizations
>>         fire.  I was just experimenting with the following combinator
>>         for `pipes` trying out the following two versions:
>>             each :: (Monad m) => [a] -> Producer a m ()
>>             each = mapM yield
>>             each :: (Monad m, Foldable f) => f a -> Producer a m ()
>>             each = Data.Foldable.mapM yield
>>         When I do a pure `pipes`-based fold over both `Producers`s,
>>         the version specialized to lists triggers a firing of the
>>         build/foldr fusion rule and runs about 20% faster.  The true
>>         improvement for `mapM` by itself is probably even greater
>>         than that because I haven't optimized the folding code yet.
>>          The latter version does not trigger the rule firing.  Either
>>         way I'm going to include the latter `Foldable` version but I
>>         just wanted to mention this because I remember people were
>>         asking if this would impact fusion or not.
>>         _______________________________________________
>>         Libraries mailing list
>>         Libraries at <mailto:Libraries at>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list