[Haskell-cafe] does the compiler optimize repeated calls?

John Hughes rjmh at cs.chalmers.se
Wed Sep 6 10:42:10 EDT 2006

On 9/6/06, Tamas K Papp <tpapp at princeton.edu> wrote:

>> or does the compiler perform this optimization?  More generally, if a
>> function is invoked with the same parameters again (and it doesn't
>> involve anything like monads), does does it makes sense
>> (performancewise) to "store" the result somewhere?

I was wondering something like this too, and then I found this email:

So I guess it is as Stephane said: theoretically possible but not actually done?

--eric the perpetual newbie


The trouble is that this isn't always an optimisation. Try these two 

powerset [] = [[]]
powerset (x:xs) = powerset xs++map (x:) (powerset xs)


powerset [] = [[]]
powerset (x:xs) = pxs++map (x:) pxs
  where pxs = powerset xs

Try computing length (powerset [1..n]) with each definition. For small 
n, the second is faster. As n gets larger, the second gets slower and 
slower, but the first keeps chugging along. The problem is that the 
second has exponentially higher peak memory requirements than the first. 
Round about n=25, on my machine, all other programs stop responding 
while the second one runs. You don't really want a compiler to make that 
kind of "pessimisation" to your program, which is why it's a deliberate 
decision to leave most CSE to the programmer. You can still write the 
second version, and suffer the consequences, but at least you know it's 
your own fault!


More information about the Haskell-Cafe mailing list