haskellfoundation / haskellfoundation/hs-opt-handbook.github.io

OneShot Monad Trick

Open
#53 1 comment 0 reactions 0 assignees View on GitHub
optimization
Dominant language
HTML
Stars
190
Forks
11
PR merge metrics
No merged PRs in 30d

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
~~~~~~~~~
...
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.