Class 8: Reverse & Practicum ... practice


Reading
None.

Homework
Turn in the Practicum 2, which turned into a practice practicum.

Reverse and the Unexpected Benefits Extra Arguments
Recall that in the last class we talked about the obvious implementation of a list reversing function, which I'll call my-reverse, since there's a builtin function reverse already.
(define (my-reverse L)
  (if (null? L) 
      '()
      (append (my-reverse (cdr L)) (list (car L)))))
	
If you go ahead and run this on some short lists, it works just fine. What about larger lists? With the help of the bl function
(define (bl n) (if (= n 0) '() (cons n (bl (- n 1)))))
for creating some large lists, we can see that it's not too fast.
> (define L (bl 10000))
> (time (car (my-reverse L)))
cpu time: 25730 real time: 53807 gc time: 12540
1
>
The reasons are two-fold: the function is not tail-recursive, and the append call needs to do some copying. In fact, tailrecursive-ness only affects the hidden constant, wheras the copying append needs to do leads, in this example, to an n^2 running time. Still, let's try and formulate the thing tailrecursively anyway.
(define (my-reverse-tr L c)
  (if (null? L) 
      c
      (my-reverse-tr (cdr L) (cons (car L) c))))
Notice that adding this extra argument c to pass along partial results from one function to the next resulted in a natural formulation using cons instead of append. So we solved both problems at once!
> (time (car (my-reverse-tr L '())))
cpu time: 30 real time: 34 gc time: 0
1

The moral of the story is ... that this idea of adding extra parameters to pass along partial results can be used to to increase efficiency in ways that have nothing to do with tail-recursion! In fact, in many cases the function you want at the user level is just a wrapper that calls a recursive function with many more paramters; parameters that pass along extra information that makes the function easier to write.

Practice Practicum
We did Practicum 2, which turned into a practice practicum.


Christopher W Brown
Last modified: Mon Jan 24 17:24:09 EST 2005