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
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
