[Haskell-cafe] What really happens

Donald Bruce Stewart dons at cse.unsw.edu.au
Sat May 19 09:57:03 EDT 2007


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


More information about the Haskell-Cafe mailing list