
David F. Place wrote:
Hi All,
Is there a program for expanding 'do' notation? I am trying to understand why the following code (from the Fannkuch entry) doesn't hold onto the list 'p' causing a space leak.
You mean "doesn't hold onto the list 'p' preventing a space leak. ^^^^^^^^^^
main = do n <- getArgs >>= return . read . head let p = permutations [1..n] mapM_ (putStrLn . concatMap show) $ take 30 p putStr $ "Pfannkuchen(" ++ show n ++ ") = " putStrLn . show $ foldl' (flip (max . steps 0)) 0 p
If I add a line which refers to 'p' at the end, there is a space leak.
print (head p)
Thanks.
Cheers, David
This is all about lazy evaluation. The "mapM_ (putStrLn . concatMap show) $ take 30 p" command generates the first 30 permutations and prints them, and takes no more space than that. The 31st permutation is never created. The "foldl' (...) 0 p" expression is the left-fold so it requires the elements of "p" one by one. "foldl'" send them with the running maximum , which starts at "0", into "(flip (max . steps 0))" which returns the updated running maximum. Since it is the primed version "foldl'" instead of "foldl", it does this with strict evaluation : the new maxiumum is computed before taking the next value of "p". Since the old values of "p" are never re-used, they are discarded by the garbage collector. So the "foldl'" runs in constant space, which is what it is designed for. When you put "print (head p)" at then end, it keeps a reference to the whole list "p" which is your space leak. If you want to store the head of p, this *should* work:
main = do n <- getArgs >>= return . read . head let p = permutations [1..n] headOfP <- return (head p) mapM_ (putStrLn . concatMap show) $ take 30 p putStr $ "Pfannkuchen(" ++ show n ++ ") = " putStrLn . show $ foldl' (flip (max . steps 0)) 0 p print headOfP
The "headOfP" is computed as an IO action at that point in the program, so "headOfP" does not hold a reference to "p" as a whole. -- Chris