I don't think IO is unidiomatic at all, although 7 years ago I might have agreed. First if we really need to we can write haskell that looks a lot like C. Secondly if I find myself in a situation where I need to write a little block of code that just doesn't lend itself to being written in Haskell I have no problem writing it in C. If I was implementing some numerical algorithm this is what I would do. Indeed haskell bindings to things like BLAS to just this. The benefit of marking all side effects with IO is an easy to read codebase, easy refactoring and of course Software Transactional Memory!

Doing this kind of effect sequencing in Haskell is annoying indeed. A radical library can mitigate that but that would be really unidiomatic.

Could be nice to have sugar like expr[!x] that expand to: x >>= \genName -> .. expr[genName] ..

So you could write: writeArr arr !(readArr ..) !(readArr ..)

Then if you add an operator to do the reading it becomes quite reasonable.

Well, you can add operators, though you almost certainly should think about more idiomatic solutions first, it's entirely possible to write operators to allow a statement like:

  arr .~ (i,j) .= arr ! (a,b) + arr ! (x,y)

You make orphan instances for Indexed and Num, and then .~ is just a slight tweak on the adjust function that Indexed provides and .= is literally a direct synonym for $ that just looks better in this context. This is actually more flexible than most languages, because now (arr .~ (i,j)) or (.~ (i,j)) can be named and applied to multiple things should that be desirable for some reason. Also note that this code is very weird, as arr is not an array, but an IO action describing how to produce one. Operations on it actually produce diffing instructions to be applied elsewhere. I have also not tested the performance.

These exact things are not in base because they are discouraged and not supposed to be easy. Note that the lens library provides operators more or less just like this for a wide variety of data types, in a safe and composable way.

Taking IO actions just to do the bind for the caller goes against the benefits you usually get from purity.

OK, I know this isn't nice but it's already part of the way there

    writeArray arr (i,j) =<< ((+) <$> readArray arr (i,j-1) <*> readArray arr (i-1,j))

This is not only not nice, it's just a bad idea. (and I understand it!)

I think you may have misinterpreted my comment.

It's not unidiomatic at all, and if you need to do it, you'll do it.