Пример, что вы привели на питоне -- это stack, а не state.
Монада State не предоставляет функциональности стека, она лишь предоставляет возможность хранения некой переменной. С точки зрения человека с головой набитой императивными тараканами это выглядит как полное копирование. Тем ни менее это не так и все зависит от программиста, нужно ли ему таскать за собой весь список или нет решает сам программист.
Например, stack-пример, приведенный выше можно реализовать (используя классическую императивную реализацию) с помощью State монады так:
import Control.Monad.State
pop :: State [a] a
pop = do
h <- head <$> get
modify tail
return h
push :: a -> State [a] ()
push = modify . (:)
print $ runState (mapM_ push [1 :: Int ,2,3,4]>>pop) []
Тем ни менее ленивые вычисления с слабые на голову конструкторы сильно меняют логику выполнения программы, если смотреть с классической императивной позиции.