Optimizations for Functor, Applicative and Monad by class laws

Learn
#1

I was surprised that the GHC.Base module has no RULES for the laws governing the Functor, Applicative and Monad classes. Does GHC use the laws in other ways to optimize code? For example, is m >>= return optimized to m and if yes, by what mechanism? Judging from the Core output of a small program involving the expression Just "hello, world" >>= return this is in fact optimized away, but that might be special to Maybe.

In another discussion examples of rank-1 types m came up that are monads but only up to some semantics: Suppose for each type a there is a context semantics :: m a -> s a so that for example the right identity law holds only in this context:

semantics m ≡ semantics (m >>= return)
          m ≢            m >>= return

I wonder whether it is safe to use monad combinators for such types or whether there is the danger that GHC might employ semantics-changing optimizations.

1 Like
#2

What you are observing here is probably just the fact that the concrete Maybe Monad is known at compile time, so the implementation for return and >>= is known and can be inlined and optimized.
The kind of general optimizations for code which uses the Functor, Applicative and Monad abstractions would only be relevant for code which is still polymorphic over arbitrary Functors/Applicatives/Monads. But this kind of code is usually small combinators, which are often marked as inlineable and are optimized at their specific call-site.

2 Likes
#3

There is also a section in the GHC documentation about how RULES don’t work well on type class methods:

2 Likes
#4

Okay, so RULES won’t silently change monadic code unless the author of that particular monad designed it so. Are there other optimizations that might simplify general code like

idF :: Functor f => f a -> f a
idF = fmap id

to idF = id?

#5

It seems you can write a rule like this:

{-# RULES "fmap/id" fmap (\x -> x) = \x -> x #-}

And that does optimize your idF. But I guess it just doesn’t work when fmap id is used with a concrete f.

#6

Thanks for showing this, but that was not quite what I was after: I’d like to know what optimizations a user of the base package must take into account when reasoning equationally about code involving fmap, <*> and >>=. In other words, instead of what optimizations are theoretically possible I’d like to know what optimizations are actually performed given an optimization compiler flag. Maybe there is an old discussion somewhere in a GHC dev mailing list? I’m certain I’m not the first one thinking about this, so someone must have had a good reason not to teach GHC to replace fmap id by id everywhere, especially since both constructs and their law are part of the first language report.

#7

Without such an explicit rule GHC doesn’t optimize it away, no.

I think the reason is that it is just a small optimization (it removes a single function call) and in many cases the functions will inline away.