fold

I have had a lot of questions about the "fold" part of the homework and
what an "accumulator" is.

The idea of a fold is that you want to apply some function to each
element of some collection.  In this assignment, the collection we're
working with is the set of variables in a formula.

The part that's hard to get initially is how fold can be useful when we
aren't using side-effects (mutation, printing, etc.).  Your intution
would be to write code such that, for example, on an "And" formula we
apply the function "f" first the left side and then to the right side--
but how do you put those two together?  If f has no side effects, then
you must use its return value in some way; otherwise there was no reason
to call it in the first place!

This is what we use an accumulator for.  It's the thing that the /user/
(in Dan's terms, "client") of the fold function uses to track whatever
it is they're doing with the variables in the formula.  So they give an
initial accumulator, and then the function they pass takes in an
accumulator and gives back a new, potentially changed, accumulator, and
fold keeps running that over all the variable and finally returns the
last accumulator.  To emphasize:  we don't ever "change" the
accumulator; we just hand it to f, which gives us back a new one, which
we repeat the process with.  The name "accumulator" is a bit misleading
in that respect.

I've found some students have been helped by seeing a picture.  Please
excuse my art ability:
http://www.cs.washington.edu/education/courses/cse341/CurrentQtr/section/fold.png

I drew the function as a box that takes its inputs on the left and has
its output come out the right.

You'll notice that the fold function itself makes no use of the
accumulator; it merely passes it through each call to the function.
I've marked all the arrows that carry the accumulator around with two
little lines across them so you can see that for yourself.

For that reason, the accumulator can be of *any type*, as long as it is
the same type as the function inputs and outputs.  In SML we write that
with a 'a, pronounced "alpha" or "tick a", and it was chosen just
because it is the first letter of the (Greek) alphabet.  The fact that
it starts with the same letter as "accumulator" is just a coincidence.