Accumulators, Graph searching, Homework tips
All of this material should be directly or indirectly helpful for your current assignment, Missionaries and Cannibals.
Our in-class example for accumulators was for finding a route in a graph. The idea was that we use an extra argument in our function(s), called the accumulator, which "accumulates" the complicated result, here the path.
When do we use accumulators? It's hard to give any firm rules, and it's best to learn from examples. In general, you should always try to solve a problem without accumulators (using plain structural or generative recursion), and only add accumulators when necessary.
Since the route finding example was rather complicated, let's look at a couple simpler examples in lab.
By now, we certainly know how to sum all the elements of a list. Thus, by our previous guideline, we probably don't want to use an accumulator for this. But, we'll use an accumulator anyway, as a nice small example that is easy to understand.
Typically, the accumulator represents whatever you will give as the final answer, or at least as much of it that you have calculated so far.
The header and contract should account for the accumulator. Your purpose should also describe the accumulator.
; sum-acc : list-of-num num -> num
; Purpose: Returns the sum of the numbers in the list, plus
; sum-so-far, which should represent the sum of any previously seen
; numbers.
(define (sum-acc alon sum-so-far) ...)
Write the function. You still use the appropriate structural or generative recursive template.
(define (sum-acc alon sum-so-far)
(cond
[(empty? alon) sum-so-far]
[(cons? alon) (sum-acc (rest alon) (+ (first alon) sum-so-far))]))
As suggested, the final answer, i.e., the answer in the base case, is just the accumulator in this case. Here, sum-so-far represents the sum of all the previously seen list elements -- when the list is empty, all of our "original" list's elements were seen previously.
Note how much of the interesting computation is now in calculating the appropriate accumulator for the recursive call. In this case, there's no computation left to do after the recursive call completes.
What should the initial call be to this function? I.e., what should the initial value of the accumulator be? When we haven't looked at any of the list's elements yet, what's the sum of those that we've looked at?
(sum-acc (list 5 1 9 -2) 0)
As in this case, the initial accumulator value is typically the same value that you would've used as the return value for the base case if you weren't using accumulators.
Since we usually don't want other people using our function to have to know about the accumulator, let's create a version that calls this function with the appropriate initial accumulator.
; sum : list-of-num -> list-of-num
; Purpose: Returns the sum of the elements in the list of numbers.
(define (sum alon)
(sum-acc alon 0))
Note how it has the same contract and purpose as our standard
non-accumulator version of the function from earlier in the class.
Anyone using this function doesn't care how it's implemented, just
as long as it lives up to its contract and purpose.
Let's do even better and hide the accumulator version.
(define (sum alon)
(local [(define (sum-acc alon sum-so-far)
(cond
[(empty? alon) sum-so-far]
[(cons? alon) (sum-acc (rest alon)
(+ (first alon) sum-so-far))]))]
(sum-acc alon 0)))
For brevity, we skipped the step of making examples. Now that we see how the accumulator is supposed to be used, go back and test the accumulator version. (Test the version before it was hidden inside a local.)
As a programmer, you should still favor the original non-accumulator version of sum. It is easier to understand. (For the curious... There are efficiency reasons why you might want a system to translate your non-accumulator version into an accumulator version, but there's no reason for the programmer to do this.)
To do: Develop the function reverse using an accumulator for the eventual result. The solution.
One effect of using a list as an accumulator: if used in the most straightforward manner, it gets elements in reverse order.
For the curious... You can write a structurally recursive non-accumulator version of reverse, so why should you ever use this version? To do: Write the non-accumulator version, and count the number of recursive calls that are made, including for the helper function (or append) you'll need. Compare that to the number of recursive calls for the accumulator version. You should see that the non-accumulator version needs more than just a constant factor more calls.
Recall our previous definition
(define (reverse aloa)
(foldl cons empty aloa))
foldl is very similar to the accumulator-based reverse.
For the curious...To do: Recall the equational definition of foldl:
(foldl f base (list x1 x2 ... xN)) = (f xN ... (f x2 (f x1 base))...)
Write foldl using structural recursion and an accumulator.
Our route-finding example in class used a strategy called "depth first search". The idea was to search for a solution along one full path, and then backtrack to find another path if you don't find a solution on the current path.
If you follow the homework directions, you will use an alternate strategy called "breadth first search". The idea is to look at longer and longer paths in the graph until you find a solution. However, instead of looking at one path at a time and backtracking to the next path, you are look at all paths at once and just keep looking deeper and deeper along those paths.
For details of both of these, please refer to the class discussion and the book. Labbies: Illustrate the difference between these strategies on a small graph.
There are several tradeoffs in using these two strategies. In answering all the homework parts, you will look at some of these tradeoffs, but you'll look at these strategies in more detail in later COMP courses.
When you are done, you will have a relatively large program -- much larger than for any previous homework in this course. If you just try to write the whole thing, then test it, you will have little if any luck in trying to find mistakes.
You should follow the design methodology -- create and use test cases for all helper functions. In previous programs, that might have sounded like busywork, but here it will save your sanity. Each of the functions should be reasonably straightforward, but as a whole system, they will solve a complicated problem and interact in complicated ways.
In the end, you'll want to hide your helper functions inside a big local. But first, make all your functions global (i.e., not inside a local), and do your testing. When everything works, then edit to hide your helper functions.
In lab, we will discuss some ideas about what states are for the Missionaries & Cannibals problem. The following are some generalities to consider:
E.g., a bunch of cities, each with its own temperature? If so, it is generally helpful to use nested data structures, such as a list of pairs, e.g., a list of city/temperature pairs.
E.g., if we are representing only right triangles, the data might be the lengths of the three sides, but having two side lengths is sufficient. We may want to keep track of only the minimal amount of information (here, two sides' lengths), or all of the data (here, all three sides' lengths). The latter choice makes it easier to get at all of the data, but we may have to worry about having inconsistent data (here, three lengths that don't make a right triangle).
We've already said that you'll be using breadth first search, not depth first. That means no backtracking.
Your program needs to accumulate a list of moves to the result. That sounds sort of similar to our in-class example that accumulated a list of cities for a path in a graph.