"David House" <[EMAIL PROTECTED]> writes: > On 18/05/07, Albert Y. C. Lai <[EMAIL PROTECTED]> wrote: > > Lazy evaluation says, to evaluate x, call f first, then x is the last > > call. > > x may be the last to be evaluated, but you still have to pass through > f's call context 'on the way out'.
Not exactly, or, only if it has some... > Let's have one more example to explain what I mean by 'call stack'. > The classic tail recursive function is foldl, contrasting with the > non-tail recursive function foldr. Equations from both these functions > are shown below, with their right-hand sides transformed into a tree > (ASCII art: don't use a proportional font): > > foldl f z (x:xs) = foldl f (f z x) xs > > foldl-+--+-----+ > | | | > f f--+ xs > | | > z x > > foldr f z (x:xs) = f x (foldr f z xs) > > f-+--+ > | | > x foldr-+--+--+ > | | | > f z xs > > Tail recursion, then, expresses the idea that a function appears at > the top of its call stack, or at the top of the tree of its right-hand > side. It's got nothing to do with evaluation order. Well, I'd rather have it a different way. The simplest tail recursion is the head function in the expression (the recursion is a/the tail call) -- so in > foldl f z (x:xs) = foldl f (f z x) xs it's easy to see that foldl is a tail call and therefore tail recursion, because it's the leftmost outermost function. Whether or not (f z x) is evaluated strictly, the body of foldl doesn't have to do anything after the call to foldl. In strict evaluation you would evaluate (f z x) before calling foldl, and in lazy evaluation you just make a representation of (f z x), but in either case you pass this as an argument to the tail function and just go. Some of the confusion here is that the left hand side of the definition actually does some work, so the notation handily obscures the fact that foldl isn't such a straightforward tail call. It's actually something like: > foldl f z l = case l of (x:xs) -> foldl f (f z x) xs [] -> z which reveals that foldl in the RHS isn't really the leftmost outermost function, but case is -- the tail call is to case. It happens that case is a kind of function that makes a choice -- it returns one of its arguments but doesn't do anything more to it. In a strict language only some predefined operators like case and if have this property, but lazy languages allow the definition of new ones, which is why we need more care when thinking about tail calls. -- Jón Fairbairn [EMAIL PROTECTED] _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe