[Haskell-cafe] Expanding do notation

[Chris Kuklewicz]

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