[Haskell-beginners] Recursive Let

[Tom Poliquin]

On Tuesday 10 February 2009 07:57, Brent Yorgey wrote:
> On Mon, Feb 09, 2009 at 05:43:03PM -0800, Tom Poliquin wrote:

> tracePlus b = let (c,d) = (d,b:d) 
>               in c
> main = do
>      w <- return $ take 10 $ tracePlus 7
>      print w
>
> > 1) How does recursion happen?

> 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.

Ah, this is what I needed, a mental model that actually fits
what's happening.

> > 2) How do things get started?

> An "uninitialized" list does not contain [].  I think perhaps your use
> of the terms "uninitialized/undefined" might betray an imperative
> mindset (?)

I've been doing FP for about 3 years (and imperative for 30)
I guess old habits are hard to break :-)  I went from Scheme
to ML and now Haskell and it seems like every day there's 
something new for me to try to wrap my head around.
(Is category theory next ??!! ... into the rabbit hole .. no
pejorative intent)

> 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. 

Great point. It seems like laziness is the major part of my misunderstanding.
Thinking about thunks will help a lot.

> 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.

Ok, this clears things up a lot !   I just need to internalize it.

> A truly _undefined_ list is indeed _|_, and not []. 
> However, as I hope I have made clear 
> above, the c and d in your example are neither [] nor undefined, so
> this is immaterial.

Good. I'm not ready for _|_ yet .. :-)

> 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

Yes it does, and you're right I'm probably not ready for the 'truth' yet :-)

Thanks for the very detailed reply. It was extremely helpful!

Tom