[Haskell] Excessive sharing and GHC

[paul boston]

Questions prompted by the "Excessive Sharing" section, page 405, of SPJ's 
"The Implementation of Functional Programming".

This section gives 2 variations of a power list function, semantically 
equivalent, but with different space behaviours. Paraphrasing, given a 
caller of "length (powerListXXX [1..20])", the powerListBad version gobbles 
more and more space as execution proceeds, whilst the powerListGood version 
runs in a small amount of constant space. Confirmed under GHC 6.2.2 with 
-O2.

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

powerListGood [] = [[]]
powerListGood (x:xs) = powerListGood xs ++ map ((:) x) (powerLIstGood xs)

Clearly, in this instance GHC is not transforming either of these 
definitions into the other. But are there other compile time transformations 
performed by GHC that might result in more (excessive) sharing, in 
particular the creation of new common sub-expressions such as pxs? If not, 
is that a deliberate design decision?

Since I guess the "excessive" bit of excessive sharing probably can't be 
determined until run-time, would it be practical for the run-time system to 
do something about it? For example, once the run-time system notices that 
the graph size has breached a certain threshold it begins to decouple 
references to "reduced" but bulky sections of the graph, forcing them to be 
recomputed (from the original expression) at a later time.

_________________________________________________________________
Is your PC infected? Get a FREE online computer virus scan from McAfee® 
Security. http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963