Everything does not have to be immutable in Haskell. It's only that mutability can only exist in IO or some other context that deals with it. The language enforces purity, not immutability.