[TurboHaskal]

What I do: Write pure functions, but don't shy away from mutating lexically scoped state in order to improve performance. For global stuff, wrap it with classes since objects are a commonly understood way to reason about state.

[Ambrevar]

For immutable data structures, there is this helper library which can help: http://quickdocs.org/immutable-struct/