I understand this frustration, but my understanding is that patterns exist to _ensure_ transformations go through exist in Haskell land. Im thinking about stream fusion for example. Lots of "pipe-y" libraries exist to make sure your program consumes input in a streamed manner.

So while your O(n) code might sometimes unreliably be turned into O(1), if performance is your game you can use these kind of libraries to endure O(1).