Open
Description
- cite this trick and provide code examples in GHC, the note is in
GHC.Utils.Monad.hs - describe exactly why this works (I think this was in Joachim's thesis?)
- tie it to a GHC specific system, i.e., the occurence analyzer
Here is some of the Note to wet your appetite:
{- Note [The one-shot state monad trick]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Summary: many places in GHC use a state monad, and we really want those
functions to be eta-expanded (#18202).
The problem
~~~~~~~~~~~
Consider
newtype M a = MkM (State -> (State, a))
instance Monad M where
mf >>= k = MkM (\s -> case mf of MkM f ->
case f s of (s',r) ->
case k r of MkM g ->
g s')
fooM :: Int -> M Int
fooM x = g y >>= \r -> h r
where
y = expensive x
Now suppose you say (repeat 20 (fooM 4)), where
repeat :: Int -> M Int -> M Int
performs its argument n times. You would expect (expensive 4) to be
evaluated only once, not 20 times. So foo should have arity 1 (not 2);
it should look like this (modulo casts)
fooM x = let y = expensive x in
\s -> case g y of ...
But creating and then repeating, a monadic computation is rare. If you
/aren't/ re-using (M a) value, it's /much/ more efficient to make
foo have arity 2, thus:
fooM x s = case g (expensive x) of ...
Why more efficient? Because now foo takes its argument both at once,
rather than one at a time, creating a heap-allocated function closure. See
https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT
for a very good explanation of the issue which led to these optimisations
into GHC.
The trick
~~~~~~~~~
...