How to make fmap rewrite rules fire?

Question

Simple question: Why doesn't this trigger the rewrite rule?

{-# RULES "fmap/fmap" forall f g xs. fmap f (fmap g xs) = fmap (f.g) xs #-}

main = do
  txt <- fmap head (fmap words (readFile "foo.txt"))
  print txt

Now I wanted to write that extracting fun triggers the rule because it did in a previous test ... not this time.

{-# RULES "fmap/fmap" forall f g xs. fmap f (fmap g xs) = fmap (f.g) xs #-}

fun f g xs = fmap f (fmap g xs)

main = do
  txt <- fun (drop 1) words (readFile "foo.txt")
  print txt

Until I by chance added a module name:

module Main where

{-# RULES "fmap/fmap" forall f g xs. fmap f (fmap g xs) = fmap (f.g) xs #-}

fun f g xs = fmap f (fmap g xs)

main = do
  txt <- fun head words (readFile "foo.txt")
  print txt

Now it still doesn't work if I just write out the function application in the main function.

To sum it up:

• txt <- fmap head (fmap words (readFile "foo")) doesn't work
• txt <- fun head words (readFile "foo") doesn't work
• txt <- fun head words (readFile "foo") plus module works
• fun f g xs = fmap f . fmap g $ xs plus module doesn't work
• fun f g xs = f <$> (g <$> xs) plus module does work (but fires later)

All of this was done by calling ghc --make -O2 -ddump-rule-firings Main.hs. Sample output:

# ghc --make -O2 -ddump-rule-firings Main.hs
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Rule fired: fmap/fmap
Rule fired: unpack
Rule fired: Class op >>=
Rule fired: Class op fmap
Rule fired: Class op fmap
Rule fired: Class op show
Rule fired: Class op showList
Rule fired: unpack-list
Linking Main ...

Answer 1

Given what @Cactus said, what I believe happens here is that the rule Class op fmap replaces your fmap with its method definition for IO:

instance  Functor IO where
    fmap f x = x >>= (pure . f)

If this happens everywhere, before your rule is triggered, then there will be no fmaps left in (GHC's internal representation of) your code for your own rule to trigger on.

GHC tries to specialize class methods when they are used at specific types, so if the monad fmap is used within is completely known, there won't be any generic fmap left once it is done specializing.

So the remaining question is, why does your rule fire when you provide a module header?

module Main where

The answer lies in how this is slightly different from the default module header that is used if you don't provide any:

module Main (main) where

Note that this explicitly exports only main from the module. Your version, with no export list, instead exports everything defined in the module, both main and fun.

When only main is exported, GHC can deduce that fun is used only internally in main, and inline it completely there, not bothering to make a standalone version. Then it notices that the fmaps are used only for IO, and specializes them. Or possibly it does it in the opposite order, but the end result is the same.

When fun is also exported, GHC must assume that the users of your module might want to call it in any monad. Therefore GHC then compiles a standalone version of fun for a generic monad, which does keep fmap generic, and your rule is able to fire on this version.

However, even for the explicit module code, the Class op fmap rule fires twice when compiling, as if it is applied to two separate fmaps. I therefore suspect that even in this case, fun is inlined and specialized in main before your rule has simplified it to use just one fmap, so the inlined version used inside main still will not have had your rule applied to it.