Comp 210 Lab 5: Re-cap

Exam debriefing

We'll go over a couple of the exam solutions (perhaps #5 (natural numbers), and definitely #4 (list-of-classweights).)
[Note: what questions do we ask ourselves, to have the template guide us to a solution?]

Accumulators: hand-evaluation

Consider a function to reverse a list.

• Following the template directly, write reverse-v1 (w/o an accumulator).
  Hint: Follow the template, and if/when you reach a point where you think "gee, wouldn't it be great if there were a function which did such-and-such", can you write a helper function to do so? (That helper function may itself also be based straight off the template.)

  #|   Template:
  
  ;; list-fun: list --> ??
  ;;
  (define (list-fun data)
    (cond [(empty? data) ...]
          [(cons?  data) ..(first data)..(list-fun (rest data)).. ]))
  
  |#
  

  
  [Note: what questions do we ask ourselves, to have the template guide us to a solution?]
  (solution)
• Let's write reverse-v2, using an accumulator: add an argument named "reverse-so-far" (or "rev-so-far", or "rsf"...).
  (solution)
• Let's look at the interesting part of a hand-evaluation of this accumulator version. ("interesting" meaning "show the expression just before calling any function you wrote"). To reverse a list of length l, how many steps (approx) are in your hand-evaluation?
  (solution)

• To discuss: why two versions, of the same program? Is one preferable?

  The standard template approach (non-accumulator) says, "how can we get an answer to our full problem, just using the answers from our sub-parts?".

  Sometimes, that info isn't enough: Consider, taking a list of numbers (bank deposit/withdrawls), and asking if the balance ever goes negative. Our input might be (list +100 -21.50 -41.50 +200). Unfortunately, looking at just hte rest of this list doesn't help you build the answer to the full problem; it really depends on the running balance-so-far. Thus an accumulator is necessary. (Another example is the fudge-data from last week's lab: the rest of the datalist may begin with 'fog; the answer depends on data previously seen.

  Sometimes, as in reverse and sum we can write a problem both ways. The primary point is getting solid, clear, correct code; which of the two versions you use isn't so important.

  However, as the hand-evaluations show, sometimes accumulator-style functions yield tail-recursive functions -- the answer to the recursive call is the answer to the entire question. This means that you don't build up a whole waiting list of pending function calls. Tail-recursion is sometimes called a loop -- it is a special case of recursion in general.

  To think about: In the non-accumulator version of reverse, how many steps (approx) are in your hand-evaluation to reverse a list of length l? This shows that there can be fundamentally faster ways of doing a task. We'll talk more about this later. Always keep in mind that it's more important to write a function so that it is clear, correct, and maintainable, than one that is faster but more confusing. Studies show that even experienced professional programmers aren't good at predicting where bottlenecks occur in code. First write your code correctly; if you find it runs too slowly, you can use drscheme's profiler and find out which functions you want to focus on, to optimize later.