documentation of difference between lazy and strict State monad
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.
I like the idea, and particularly the fact that the example covers the distinction between strictness in the value, tuple or state. If nothing else, I could bundle this up into a documentation patch for mtl, but the example probably belongs in transformers with the data types, which Ross still maintains. You may have better luck emailing him directly. Sent from my iPad On Sep 21, 2011, at 11:03 AM, Henning Thielemann <lemming@henning-thielemann.de> wrote:
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.
_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
On Wed, 21 Sep 2011, Edward Kmett wrote:
I like the idea, and particularly the fact that the example covers the distinction between strictness in the value, tuple or state. If nothing else, I could bundle this up into a documentation patch for mtl, but the example probably belongs in transformers with the data types, which Ross still maintains. You may have better luck emailing him directly.
I am still not happy with the need to define a custom 'mapM' function, since this cannot be ported to other traversable structures easily. But maybe there is a theoretical problem, that I did not realize so far.
participants (2)
-
Edward Kmett -
Henning Thielemann