[Haskell-beginners] Recursive Let

[Brent Yorgey]

On Mon, Feb 09, 2009 at 05:43:03PM -0800, Tom Poliquin wrote:
> 
> 
> 1) How does recursion happen?
> 
> Being an ex-Schemer I recalled that let x = 3
> get translated into something like
> 
>    (lambda (x) ... ) 3
> 
> So now there's a function involved. It's clear that b:d is
> 
>    (cons b d) 
> 
> another function. So with appropriate plumbing
> I could see the thing recurses but the Haskell viewpoint
> eludes me.

In Haskell, thinking of let expressions as being translated into
lambda expressions is not very helpful, precisely because of the
special ability to have recursive let bindings.  In Haskell it is
perfectly OK to have something like

  let x = 1:y
      y = 0:x
  in  ...

but it is not clear how this would get translated into function
application (which would come first?).  It's better just to think of
let as a special, primitive construct.

> 
> 2) How do things get started?
> 
> It seems that Haskell could figure out that
> 'd' is a list. If an uninitialized (undefined?) 
> list contains [] then things are reasonably
> straightforward ..

An "uninitialized" list does not contain [].  I think perhaps your use
of the terms "uninitialized/undefined" might betray an imperative
mindset (?); in any case these are not the right words to use, since
they give an incorrect picture of what is going on.

Here's what actually happens: as a first example, let's consider the
let-binding

  let x = 1:x
  in ...

What happens here is that x is bound to a closure or 'thunk'
(suspended computation) which, *when needed*, will evaluate to 1:x.
This is laziness at work.  x is not 'uninitialized'; it is perfectly
well initialized to this thunk.  It is definitely not equal to []; at
this point the runtime doesn't know anything about x other than the
fact that it is a list, and that there is a thunk which may be
evaluated if and when the value of x is actually needed.  If you don't
use x anywhere in the ..., nothing will ever happen and the thunk will
eventually get garbage collected (in fact, it's likely that the
compiler would optimize x away and it would never be in memory at
all).

But suppose the value of x is needed (that is, some code
pattern-matches on x). Then the thunk will be evaluated just far
enough to allow the pattern-match: in particular, x will now be a list
with first element 1, and remainder of the list... another thunk.  At
this point x is not [1]; it is [1:...] where the ... represents
another thunk which will evaluate to x.  This process repeats as more
elements of x are needed, with each thunk evaluating just far enough
to allow the necessary pattern-matches, and suspending the remainder
of computation in another thunk.

Now, let's look at your example:

  let (c,d) = (d,b:d)

Of course, c and d will both be initialized to thunks which will
evaluate to lists as needed.  It's important to realize that from a
semantic point of view, b, c, and d never change.  They always
represent the same, unchanging values, as defined by this let
statement; it's just that operationally, only part of those values may
be actually evaluated, as needed.

If b has the value 7, then d = 7:d, which means d = 7:7:d, which means
d = 7:7:7:d, and so on, and the runtime will expand d out as far as
needed (in this case, 10 elements). You really can think of d as
*being* an infinite list of 7's, only part of which is evaluated.
 
> This is all fine. The only thing that subconsciously
> nags me is that we appear to 'return' each time  which 
> would imply that we would leave the closure causing 'd' 
> to be undefined again.

One way to think about it is that we only 'return' once: when
tracePlus 7 is evaluated, it returns, once and for all, a value 'c',
the evaluation of which happens to be suspended; it will be evaluated
further as needed.  Of course, if you want, you can indeed think of
execution jumping back and forth between main and tracePlus as c is
evaluated bit by bit, but I think this view is unhelpful, as it
suggests procedure calls in an imperative language, where local
variables such as 'd' would indeed go out of scope each time tracePlus
'exited'.  Instead, think of tracePlus as returning a closure, which
packages up the values of b, c, and d; it is this closure which is
then evaluated incrementally as execution continues.
 
> Back to the undefined list ... if it's *not* an
> [] and has something to do with bottom ( _|_ )
> then my eyes glaze over and I have to go watch a
> Woody Allen movie to reset.

A truly _undefined_ list is indeed _|_, and not []. [] is quite
defined; it is the list with no elements.  _|_ just means 'the
completely undefined value'.  However, as I hope I have made clear
above, the c and d in your example are neither [] nor undefined, so
this is immaterial.

There is much more to say on the topic, and doubtless there are places
where I've told some small fibs because the truth is more
complicated.  But hopefully this helps provide a useful way to
understand things.

-Brent