The Recursive instance for Mu fmaps more than necessary

[treeowl]

Manually specializing/inlining a few times reveals the opportunity to fuse three of the fmaps into one. I'm not sure of the cleanest way to do this yet, but one option seems to be

  project (Mu g) = g (fmap (let q x = Mu (\f -> f (fmap (cata f . q . project) x)) in q))

I have the feeling there may be several other similar opportunities lying around.

[gelisam]

It is beneficial to merge fmap f . fmap g into fmap (f . g) when each fmap has to traverse a large recursive structure. Since those fmaps are operating on the base functor, which is only a single step of the recursive structure, I don't expect those fmaps to be costly, so I am worried about increasing the complexity of the codebase without a corresponding increase in the performance.

Furthermore, I believe your proposed implementation actually decreases the performance :(

The current implementation is:

project :: Mu f -> f (Mu f)
project = cata (fmap embed)

cata :: (f a -> a) -> Mu f -> a
cata roll (Mu mk) = mk roll

embed :: f (Mu f) -> Mu f
embed fmu = Mu $ \roll -> roll $ fmap (cata roll) fmu

Whereas your version is basically this:

project :: Mu f -> f (Mu f)
project = cata (fmap go) where
  go fmu = Mu $ \roll -> roll $ fmap (cata roll . go . project) fmu

Notice that go looks a lot like embed:

embed fmu = Mu $ \roll -> roll $ fmap (cata roll) fmu
go    fmu = Mu $ \roll -> roll $ fmap (cata roll . go . project) fmu

except go does a lot more work per fmap! It gives the same result because go is embed, and embed is the inverse of project, so the go . project part is an expensive id.

[treeowl]

I really don't remember what I did to find maps that I thought needed fusion. Hrmm.... If I figure it out, I'll let you know.