03:31 pm, 22 Apr 04
I just wrote this to the class list about fold. I'm never sure which parts are clear and which aren't, but the few students I've talked to seemed to understand things better once they saw the picture.
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.