I don't know Haskell, but in Erlang, which has semantics similar to those you show, maintaining locally accessible mutable state requries fighting the language. You *can* do it, and fairly simply, but all the sources tell you "Don't do this!", so my suspicion is that if I wrote anything sizeable it would lead to difficult to trace problems.
But mutable state is a part of what many applications need. They just don't need globally visible mutable state.
To be a little bit more precise, I could do things safely in Erlang (i.e., without violating strong recommendations) by storing changes in a database. But that would slow things down tremendously. "volatile" state doesn't usually need to be saved, since it's just going to change again anyway. But it does need to be able to be changed.
Note that anything that can be calculated using mutable state that is safe to express, can be calculated in a pure functional language, if you don't concern yourself with memory and time. But the same it true of a Turing machine. For some classes of problems, pure functional languages work well. That fibonnacci example is a nice example of this. (IIUC that example calculates each small value of the function many times in the course of calculating larger values. Not ideal.) For this reason most functional languages have "escapes" which make them not-pure-fuctional..