Imagine an imperative rendering engine that blits sprites to a bitmap that later gets displayed. This heavily relies on the ability to efficiently mutate individual pixels in said bitmap. How would I do such a thing an a language without side effects? I guess a completely different data structure is called for?
You can convert any algorithm that uses mutable state into an algorithm that "strings" the state along with it. Haskell provides a way of doing this such that it still feels like imperative programming with the state Monad.
Although, it seems to me that the basic blit operation could be done in a more functional style. You are basically combining two bitmaps to produce a new bitmap via pixel by pixel operation. That sounds very functional to me.
High quality imperative code is often faster than good functional code, but if you are willing to give up a little speed you can normally create very nice architectures in a pure functional style