andrewcoppin:
Hi everybody.
Is there any circumstances under which an expression like map (2*) would perform an in-place update rather than generating a new list? (Obviously
Yes, should be fine, if the result is consumed. We have fusion frameworks that do this.
this depends on which compiler we're talking about. I'm implicitly assuming GHC.) Assuming the old list isn't needed again, an in-place update is obviously significantly cheaper. (Less RAM used, less time allocating RAM, less GC time, etc.) For something like an integer which can be "unboxed", you could write a very tight loop of machine code to perform a multiplication by 2 over a single-linked list.
Similarly, according to the rules, something like length . filter odd
length . filter won't fuse in ghc's current list fusion system, as length is a left fold. However, we do know how to fuse it, and a couple of libraries do provide a fusible length . filter api (bytestring, using functional array fusion, and stream fusion, and the Data.List.Streams library). They use library specified rewrite rules to augment ghc's optimiser with domain specific strategies for optimising their api.
I spend lots of time telling people that Haskell compilers can actually make big optimizations like this, and coding my own stuff as if this will happen, but is it actually so? Am I assuming the optimizer is all-powerful when in fact it's not?
It does do some pretty clever optimisations, because purity helps compilers out a lot. So yes, I think its safe to say that the various optimising Haskell compilers are pretty smart, and do many things not feasible in an impure setting. -- Don