Accumulators, Graph searching, Homework tips
All of this material should be directly or indirectly helpful for your current assignment, Missionaries and Cannibals.
In-class, we saw two examples for accumulators:
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.
In the first example, we used an accumulator because we didn't see how to solve the problem without it. That example was rather complicated, since it also involved backtracking and somewhat complicated data structures. In the second example, we used an accumulator to obtain a faster algorithm.
Let's use accumulators in a couple more relatively small examples.
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) ...)
To do: Write the function. You still use the appropriate structural or generative recursive template.
The interesting computation should be in calculating the appropriate accumulator for the recursive call. In this case, there should be no computation left to do after the recursive call completes.
Q: 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?
The initial accumulator value is typically the same value that you would've used as the return value for the non-accumulator version's base case.
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)
...)
To do: Write this function.
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.
Of course, as we already know, it is even better to hide the accumulator version from any prying eyes:
(define (sum alon)
(local [(define (sum-acc alon sum-so-far)
...)]
...))
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.)
Recall our previous definition
(define (reverse aloa)
(foldl cons empty aloa))
foldl is very similar to the accumulator-based reverse.
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.
Labbies: Give a quick overview of the idea of Missionaries and Cannibals. Not all students will have read the assignment yet. (Although they should have!)
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.