documentation of difference between lazy and strict State monad
Henning Thielemann
lemming at henning-thielemann.de
Wed Sep 21 17:03:04 CEST 2011
The confusion about the kind of strictness in lazy and strict State monad
pops up again and again. How about illustrating the difference using these
examples:
Control.Monad.Trans.State.Lazy> evalState (mapM (\n -> modify (n+) >> get) [1::Integer ..]) 0
[1,3,6,10,15,21,28,36,45,55,66,78,91,105,120 ...
Control.Monad.Trans.State.Strict> evalState (mapM (\n -> modify (n+) >> get) [1::Integer ..]) 0
<<wait infinitely>>
?
Now, often I like to have a kind of strictness where lists can be
processed lazily but the state is updated strictly between the list cells.
E.g. the following expression cannot be computed both in lazy and in
strict State monad:
evalState (mapM (\n -> modify (n+) >> get) [1::Integer ..]) 0 !! 10000000
Since the list shall still be processed lazily, we must stay in the lazy
State monad. But the state shall be updated strictly for every list cell.
I can achieve this for instance by replacing 'mapM' by the following
'mapS':
mapS :: (a -> State s b) -> [a] -> State s [b]
mapS _ [] = gets (\s -> seq s [])
mapS f (x:xs) = do y <- f x; s <- get; ys <- mapS f xs; return (seq s (y:ys))
Now
evalState (mapS (\n -> modify (n+) >> get) [1::Integer ..]) 0 !! 10000000
can be computed with constant memory consumption.
More information about the Libraries
mailing list