Dnia czw 28. sierpnia 2003 23:04, [EMAIL PROTECTED] napisał: > > copyList (x:xs) = x : copyList xs > > > > is surely not tail-recursive in the traditional sense, but I think > > that most Haskell programmers take it for granted that it runs in > > constant stack space.
The problem lies in the fact that the execution of a Haskell "function" can be interleaved with the execution of the code which calls it. Counting total stack space ever consumed by parts consisting of a function is meaningless because between these parts the stack is usually unwound. If you implemented this in a strict language, you would probably attribute only building of the cons cell to the invocation of the function. The cell points to a thunk in its tail, so when the tail is evaluated, an anonymous function is called - the original function is long finished. > I brought up the same issue some time back about >>. That is > in func = f x >> func, we have the problem that >> is a function > so func is not a last call. It's an easy problem: although func is not a tail call, >> is a tail call and >> itself in most monads enters its second argument in a tail position. I would name it an indirect tail call. > In procedural programming, the idea of the last call is that > there is an operator ; that is often thought of as separating > statements. In Scheme not only sequencing generates tail calls; e.g. branches of 'if' are in a tail position wrt. the 'if' itself, the body of 'let' wrt. the whole 'let' etc. If these constructs were implemented as plain functions taking closures as parameters, you would derive whether they tail call some of their parameters from their implementation. A Scheme definition, which describes the semantics and not a concrete implementation, would probably specify which functions on which conditions are required to tail call which of their parameters. But Scheme prefers macros, so I think the language definition doesn't talk about tail call properties of standard functions - because there aren't any interesting functions to talk about. OTOH Haskell uses more functions instead of built-in syntactic constructs, because passing a parameterless closure is very easy - you just write the expression consisting of the body. This makes meaningful to ask which functions on which conditions enter some of their parameters in a tail position. For example && does this with its second parameter if it's entered at all. -- __("< Marcin Kowalczyk \__/ [EMAIL PROTECTED] ^^ http://qrnik.knm.org.pl/~qrczak/ _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell