Yes, in the conclusion I remark that a Sufficiently Smart Compiler can do all of this. I don't know that either Haskell or C++ compilers will inline your maps,

Yes, in the conclusion I remark that a Sufficiently Smart Compiler can do all of this. I don't know that either Haskell or C++ compilers will inline your maps, but if so, that's very cool. And yes, specializing for the Array -> Array case and eliminating bounds checks will be necessary to get real performance.