[Haskell-cafe] state updates and efficiency

[Tim Newsham]

I am writing some code with complex nested state.  I have a question
about performance with respect to the State monad and the Reader monad.

This is somewhat long, so a quick summary of the question up front:
Can the compiler optimize out state updates that dont change the
state?

The question inline with the code:

> module Test where
> import Control.Monad.State
> import Control.Monad.Reader

I have some nested state.  This is a simplified example where
we have one record inside another.  In my real-world example there
is more nesting and there are lists and maps involved as well.

> data T1 = T1 { f1 :: Int, f2 :: T2 } deriving(Show)
> data T2 = T2 { f3 :: Int, f4 :: Int } deriving(Show)

I want to build generic modifiers and reuse them often.
A good example is modifying a numeric value:

> adjNum :: (Num a) => a -> State a ()
> adjNum n = modify (+ n)

I'm going to be writing state code for my T1 structure which is my
master structure.  If I'm going to be able to reuse adjNum I am
going to have to run a nested state action inside an enclosing
state monad.  I can build a lifter that does this as long as
I know how to extract the nested state and set it back in the
enclosing state:

> withInnerM :: (o -> i) -> (i -> o -> o) -> State i a -> State o a
> withInnerM gettor settor act = do
>     outer <- get
>     let inner = gettor outer
>         (ret, inner') = runState act inner
>         outer' = settor inner' outer
>     put outer'
>     return ret

Now we can make lifters for each of the fields:

> withF1M = withInnerM f1 (\f r -> r {f1=f})
> withF2M = withInnerM f2 (\f r -> r {f2=f})
> withF3M = withInnerM f3 (\f r -> r {f3=f})
> withF4M = withInnerM f4 (\f r -> r {f4=f})

which lets us write some state code for T1 using building blocks like
adjNum.  For example, the following code will add a value to
f1, add another value to f2's f3 and finally return the value of f2's
f4:

> tweakT1 :: Int -> Int -> State T1 Int
> tweakT1 v1 v3 = do
>   withF1M $ adjNum v1
>   withF2M $ withF3M $ adjNum v3
>   withF2M $ withF4M $ get

My question here has to do with efficiency.  In order to update
f2's f3 a new T2 had to be constructed and used to construct a
new T1.  There's no way around this (I assume).  But when doing
a mere get of f4, there's no reason why we should have to build a
new T2 and then a new T1 since nothign changed.  But that's how
the code is written.

We could write a different lifter that does not perform a state
put on the return path.  If we did this with the state monad then
someone could accidentally use that non-modify version of the lifter
and lose an update.  So instead I chose to use the Reader monad and
let the type system enforce the difference between lifters that
modify (M) and those that just read (R).  This involved two kinds
of lifters.

The first lifter runs a Reader action inside of a State monad:

> withRead :: Reader s a -> State s a
> withRead act = do
>     s <- get
>     return $ runReader act s

The second lifter runs a nested Reader action inside of an enclosing
Reader monad.  It is similar in spirit to withInnerM:

> withInnerR :: (o -> i) -> Reader i a -> Reader o a
> withInnerR gettor act = do
>     i <- asks gettor
>     return $ runReader act i

again we can generate lifters for each field:

> withF1R = withInnerR f1
> withF2R = withInnerR f2
> withF3R = withInnerR f3
> withF4R = withInnerR f4

And finally we can use a reader monad to eliminate the extra state
updates from our previous tweakT1 implementation:

> tweakT1' :: Int -> Int -> State T1 Int
> tweakT1' v1 v3 = do
>   withF1M $ adjNum v1
>   withF2M $ withF3M $ adjNum v3
>   withRead $ withF2R $ withF4R $ ask
>
> main = do
>   let x = T1 1 (T2 3 4)
>   print $ runState (tweakT1 5 6) x
>   print $ runState (tweakT1' 5 6) x

My question here is: is it worth it?

If I run

> v1 = T2 1 1
> v2 = v1 {f3 = 1}

is the compiler smart enough to notice that the record update doesn't
result in a change, and avoid constructing an entirely new T2?
If so, then I think the original implementation TweakT1 would be
about as efficient as the more complicated TweakT1'.  Otherwise,
I think the latter would be a lot more efficient when the state is
large and complex.

Tim Newsham
http://www.thenewsh.com/~newsham/