Is state copied on every operation on the state monad in Haskell?

Question

Python

Let's say there is an example of implementing a special case of the State monad in Python - a stack with push and pop operations:

from collections import namedtuple

Stack = namedtuple('Stack', ('value', 'stack'))

Stack.bind = lambda self, fn: fn(self.value, self.stack)

def pop(_, stack):
    return Stack(stack[-1], stack[:-1])

def push(value):
    def inner(_, stack):
        return Stack(value, stack + [value])
    return inner

print(Stack(0, [])
    .bind(push(1))
    .bind(push(2))
    .bind(push(3))
    .bind(pop)
    .stack
)    # [1, 2]

It turns out that at each operation the entire stack is copied. In Haskell, it would be possible to add an element to the beginning, then only the link to the tail will be copied, but the essence does not change - if there was a dictionary, then with each operation, it turns out that the entire dictionary is copied. In theory, performance should be much worse than in imperative languages, where nothing needs to be copied every time. Did I understand correctly? Can something be done about it?

Answer 1

It is copied, only it is necessary to take into account the laziness and purity of Haskell.
If you take an ordinary list and put it in the head - nothing will need to be copied, since adding the head does not require copying the tail, the new list will simply refer to the tail. Removing the head (i.e. taking the tail) also does not require making copies.
If you use any strict data type as a state, yes, with unboxed members, yes, it will be copied.
We must also take into account another thing: the accumulation of thunks. For example, if the state is a number, and you do it a million times modify (+1), in fact there will be a lazy calculation for a million additions of units, which will eat memory. Because there is a strict state monad, and alsomodify', which forces the application of the passed function.

Answer 2

Despite the fact that the State is also a stack inside, you need to separate the State itself and the data structure that is dragged through it:

from collections import namedtuple

State = namedtuple('State', ('fx', 'previous'))
State.unit = staticmethod(lambda value=None: State(lambda: value, None))
State.bind = lambda self, fx: State(fx, self)
State.get = lambda self: self.fx(self.previous.get()) if self.previous else self.fx()

push = lambda value: lambda stack: (value, stack) if stack else value
pop = lambda stack: stack[1] if isinstance(stack, tuple) else stack
toList = lambda stack: toList(stack[1]) + [stack[0]] if isinstance(stack, tuple) else [stack]

print (State.unit()
       .bind(push(1))
       .bind(push(2))
       .bind(push(3))
       .bind(pop)
       .bind(toList)
       .get()) # [1, 2]

toList- rather slow, just an example.