[plt-scheme] List loop timing

From: Carl Eastlund (cce at ccs.neu.edu)
Date: Fri Feb 15 14:17:11 EST 2008

On Fri, Feb 15, 2008 at 2:15 PM, Carl Eastlund <cce at ccs.neu.edu> wrote:
> On Fri, Feb 15, 2008 at 2:05 PM, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:
>  > Carl Eastlund wrote:
>  >  > My point is that removing append is what did something for
>  >  > its time, and tail recursion was serendipitous.  The saved time is all
>  >  > due to traversal of the list structure, and not due to the stack.
>  >
>  >  Most (not all) of the saved time is due to avoiding excessive list
>  >  traversal. But without working through the idea of using tail recursion,
>  >  one wouldn't have saved that time. If you insist on measuring the
>  >  savings due to tail recursion as the difference between the
>  >  tail-recursive function and the tail-recursive function spiked by
>  >  putting a trivial operation after each tail call, then, yes, the
>  >  difference is likely negligible. --PR
>  I don't insist on measuring a contrived function.  But if you want to
>  measure the savings of X, you can't trust comparisons that vary in
>  both X and Y.  For reverse, it happens that the only way to vary in
>  tail recursion but not list traversal is to use a contrived function;
>  that's incidental.
>  Personally, I learned how to write linear-time reverse in a lesson on
>  accumulators, in which tail recursion wasn't once mentioned (mostly
>  because I was programming in C).  You're used to seeing it tied up
>  with tail recursion, but the tie is not inherent.

That last should be "perhaps you're used to" or "in functional
programming, one is used to", or something of the sort.  Obviously I
don't know for sure what anyone other than myself it used to, and
should not assert that I do.

Carl Eastlund

Posted on the users mailing list.