Зачем этот код haskell не заканчивается

Question

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 

Не должен ли mapM_ быть ленивым? Кроме того, для реализации очереди не должно быть сложности O(1)?

Поскольку Append (++) сам ленив ...

Answer 1

Обратите внимание, что do mapM_ push [1..3]; something такое же, как:

do push 1; push 2; push 3; something 

так, что должен объяснить, почему

do mapM_ push [1..]; something 

никогда не получает вокруг выполнения something.

Если посмотреть на определение государственной монады:

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) 

вы видите, что значение m >>= g всегда зависит от g. Контраст, что с определением Maybe монады:

instance Monad Maybe where 
    return x = Just x 
    (>>=) m g = case m of 
        Nothing -> Nothing 
        Just x -> g x 

, где m >>= g может быть независимым от g, который объясняет, как Maybe монады может вызвать короткое замыкание сделай цепи.

Answer 2

Что делать, если я зла и использовать

push' :: Int -> State (Queue Int)() 
push' 1052602983 = state $ \_ -> ((), []) -- "Muarhar!" 
push' x = state $ \xs -> ((),xs++[x]) 

Тогда mapM push' [1..] должны четко визуализировать состояние как [1052602983, 1052602984 ..]. Было бы неправильно для pop, чтобы получить 1. Но mapM, возможно, не знает этого, без предварительной оценки миллиарда других чисел. Фактически толчок их к состоянию здесь не имеет значения, и также не имеет значения, что push может быть полностью ленивым: mapM по крайней мере должен дать ему шанс проверить любое заданное число, прежде чем передавать монографический поток программы.