Actually, because Clojure is not ideological (though it is very opinionated) -- and certainly not pure -- but rather very pragmatic, it includes a very interesting feature called transients[1]. Transients temporarily turn a persistent collection into a mutable (in place) one in O(1), specifically to allow efficient in-place algorithms like quicksort.
Clojure's syntax for transients is deliberately more cumbersome. A Scheme like 'loop! would flag the decision to employ mutation. Instead, Clojure steps outside the conventions of dynamic typing and expressions and requires something that looks like a static type specification and another thing that looks a lot like a 'return statement.
To put it another way, the language complects mutation instead of simplifying it and it's reasons for doing are...well, what's the difference between an ideology and an enforced opinion?
Clojure is rarely introduced with, ok here's how you can do exactly what you were doing before in Clojure, and now here are some ways that you might think about doing it differently. Instead, Quincy autopsying the corpse before the opening credits are even finished.
None of which is to say that I don't like Clojure. It's just that the really important question is part of the theology rather than evangelical outreach. Java in Clojure probably isn't good Clojure, but it might often be better Java. 20% less imperative code is probably an improvement.
I'm pretty sure that it is possible to make a function in Haskell which, while it mutates variables, these variables are all local, so you are still able to offer up a purely functional interface to the world outside of that function.
Whether this is simple and straightforward or even demands some "magic" which isn't usually part of the language semantics - that I don't know. Imperative code seems very doable and maybe even pleasant in Haskell, but I don't know how simple it is to actually write imperative code that is efficient - e.g. destructive updates and all that, rather than making a new value for each "update" and programming in an imperative style though you are really just using immutable values all the time.
> I'm pretty sure that it is possible to make a function in Haskell which, while it mutates variables, these variables are all local, so you are still able to offer up a purely functional interface to the world outside of that function.
Indeed, it's called the ST monad. The internals aren't that magical, behind the scenes GHC does some state passing like IO but nothing too fancy. The real trick is using -XRankNTypes for the runST function[1] to track "state threads" at the type-level.
example1 :: Int
example1 = runST $ do
x <- newSTRef 0
forM_ [1..1000] $ \j -> do
writeSTRef x j
readSTRef x
State can be local, but you need an escape analysis to verify that it doesn't leak the context if your language supports aliases, which I believe Haskell doesn't (or to say, aliases don't make sense in Haskell).
[1]: http://clojure.org/transients