Wadler space leak

28 Oct 2010

      Hi,

I have a question regarding the famous Wadler space leak. The  
following program is a variation of Wadler's example.

   let (first,rest) = break (const False) input
   in
   print (length (first ++ rest))

When I compile this program using -O2 and use a large text file as  
input the code runs in constant space. If I understand correctly, the  
program runs in constant space because ghc uses an optimization  
similar to the one proposed by Wadler/Sparud.

If I define the following function which is based on break

   splitBy :: (a -> Bool) -> [a] -> [[a]]
   splitBy _ []  = []
   splitBy p xs  =
     l : case ys of
              []   -> []
              _:zs -> splitBy' p zs
     where
       (l,ys) = break p xs

and compile the following program the behaviour is different.

   print (length (concat (splitBy (const False) input)))

In this case the memory usage is not constant. However if I use a  
strict pattern matching instead of the lazy tuple matching the program  
runs in constant space.

   splitBy' :: (a -> Bool) -> [a] -> [[a]]
   splitBy' _ []  = []
   splitBy' p xs  =
     case break p xs of
          (l,ys) -> l : case ys of
                             []   -> []
                             _:zs -> splitBy p zs

To me this looks like another instance of the Wadler space leak. Is  
this correct? I do not understand why the Wadler example runs in  
constant space and this example does not. Can anyone explain me why  
these functions behave differently?

I still get the same behaviour if I use the following simplified  
function.

   test :: (a -> Bool) -> [a] -> [[a]]
   test _ []  = []
   test p xs  =
     l : case ys of
                 [] -> []
     where
       (l,ys) = break p xs

That is, the following program does not run in constant space.

   print (length (concat (test (const False) input)))

On a related note if I do not use -O2 the following program runs in  
constant space

   let (first,rest) = break (const False) input
   in
   print (length (first ++ rest))

while it does not run in constant space if I add an application of id  
as follows.

   let (first,rest) = break (const False) input
   in
   print (length (first ++ id rest))

Thanks, Jan

Wadler space leak

Jan Christiansen