[Haskell] Excessive sharing and GHC

paul boston paul_bostonjp at hotmail.co.uk
Mon Oct 17 13:42:59 EDT 2005

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 

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

More information about the Haskell mailing list