[Haskell-cafe] Expanding do notation

Chris Kuklewicz haskell at list.mightyreason.com
Sat Jan 7 12:25:45 EST 2006

David F. Place wrote:
> On Jan 7, 2006, at 11:56 AM, Chris Kuklewicz wrote:
>> This is all about lazy evaluation.

Ah.  Sorry then.

> Actually, I understand about lazy evaluation.   What I don't  understand
> is the extent of variable bindings.

The binding has a lexical extent.  The "p" in the source file means
"permutation [1..n] for the whole block, as you show correctly below:

> If I desugar the code this far:
> main = do n <- getArgs >>= return . read . head
>               main' n
> main' n = let p = permutations [1..n]
>                   in do mapM_ (putStrLn . concatMap show) $ take 30 p
>                           putStr $ "Pfannkuchen(" ++ show n ++ ") = "
>                           putStrLn . show $ foldl' (flip (max . steps
> 0)) 0 p
> 'p' is a variable bound by a normal 'let.'   Why isn't 'p' kept  around
> until the whole 'in' expression is evaluated?

"p" is lexically available to refer to by you source code for the whole

After it is compiled and run, the dynamic garbage collection whittles
away the *elements* of p that can no longer (a dynamic concept) be
accessed.   At the same time, the *elements* of p that are demanded are
computed lazily.

>  If it were,  then I
> assume the GC would be obliged to copy everything it pointed to.
> In the original version, the author called 'permutations' twice and 
> didn't create a variable binding.
> Cheers, David

the mind-bending-thing I had to learn with Haskell is that the "let p ="
 creates source code *shorthand*.  In C++,Scheme,Lisp,Java,Python it
allocates a particular part of memory that is called "p" and refers to a
list.  This could then be altered with "p=q" or "(set! p q)" depending
on the language.  In Haskell, a binding "let p =" is not a variable in
memory anywhere like "int p" or "int **p" that can be mutated.  The
Haskell binding is just syntactic shorthand to make your code easier for
you to read.

> Spoon boy: Do not try and bend the spoon. That's impossible. Instead... only try to realize the truth.
> Neo: What truth?
> Spoon boy: There is no spoon.
> Neo: There is no spoon?
> Spoon boy: Then you'll see, that it is not the spoon that bends, it is only yourself. 

There is no allocated "p" that points to the head of the permutations at
run time and lives the duration of the lexical block.

Also, note that if write

makeP n = let p = permutations [1..10]
          in return p

Then the permutations clearly exist after the lexical scope of the "let
binding".  Allocation is done when lazy things get evaluated and
de-allocation is done when the garbage collector can discard unreachable


More information about the Haskell-Cafe mailing list