Why does this haskell code not end
import Control.Monad.State.Lazy
type Queue a = [a]
push :: a -> State (Queue a) ()
push x = state (\xs -> ((),xs++[x]))
pop :: State (Queue a) a
pop = state (\(x:xs) -> (x,xs))
queueManip :: State (Queue Int) Int
queueManip =
do
mapM_ push [1..]
a <- pop
return a
main :: IO()
main = do
let (a,_) = runState queueManip []
print a
Should I mapM_
be lazy? Also, it shouldn't be difficult to implement a queue O(1)
?
Since append (++)
itself is lazy ...
source to share
What if I get angry and use
push' :: Int -> State (Queue Int) ()
push' 1052602983 = state $ \_ -> ((), []) -- "Muarhar!"
push' x = state $ \xs -> ((),xs++[x])
Then mapM push' [1..]
should clearly display the state as [1052602983, 1052602984 ..]
. It would be wrong to pop
receive 1
. But mapM
he cannot know this without a preliminary estimate of a billion other numbers. Actually pushing them to the state doesn't matter here, nor does it matter which push
might be completely lazy: mapM
at least should give it the ability to check any given number before passing the monodal program stream.
source to share
Note that is the do mapM_ push [1..3]; something
same as:
do push 1; push 2; push 3; something
to explain why
do mapM_ push [1..]; something
never gets away with doing something
.
If you look at the definition of a state monad:
type State s a = s -> (a, s)
instance Monad (State s) where
return a = \s -> (a,s)
m >>= g = wpAB
where
wpAB = \s1 -> let (v2, s2) = m s1
(v3, s3) = g v2 s2
in (v3, s3)
-- (newtypes and such have been removed to declutter the code)
you see the value m >>= g
always depends on g
. Compare this to the definition of Maybe
monad:
instance Monad Maybe where
return x = Just x
(>>=) m g = case m of
Nothing -> Nothing
Just x -> g x
where m >>= g
cannot be independent of g
, which explains how a monad Maybe
can complete a do-chain.
source to share