[Haskell-cafe] Space usage and CSE in Haskell

[Melissa O'Neill]

I wrote:
>> This "CSE-makes-it-worse" property strikes me as "interesting".    
>> Has anyone worked on characterizing CSE space leaks (and avoiding  
>> CSE in those cases)?

and Simon replied:
> You might find chapter 23 "The pragmatics of graph reduction" in my  
> 1987 book worth a look. It gives other examples where CSE can be  
> harmful.

There are some great examples there.  Specifically, 23.4.2 "Excessive  
Sharing" (viewable at http://research.microsoft.com/~simonpj/papers/ 
slpj-book-1987/PAGES/405.HTM) gives a neat example, the powerList  
function.

In short, it contrasts two definitions.  The first uses sharing:

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

and a space-efficient one (that does more reductions):

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

... when running length(powerList [1..20]).

But my original question was whether this problem is considered  
"interesting", etc.  As Simon points out above, its an issue that has  
existed for at least 20 years, but Simon also wrote for GHC bug #947  
(which looked like a related issue):

> I don't know any way to solve this problem automatically.  But I do  
> think it should be under your control.

To me, problems that Simon doesn't know how to solve are by  
definition at least a little interesting, but probably likely to be  
rather hard... :-)

     Melissa.

P.S. GHC bug #947 can be viewed at http://hackage.haskell.org/trac/ 
ghc/ticket/947 (Simon's bandaid for GHC bug #947 was -fno-cse.)