# evan_tech

03:31 pm, 22 Apr 04

### fold

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.```

•  Ah, you mean "inject" in Smalltalk-80 parlance... reply to this
•  Smalltalk-80Get with the century, old man ;^P (yes, i know smalltalk was years and years ahead of its time, and i've never heard anything but good about it. I haven't learned it yet because i'm lazy. I just feel like giving you a little crap now and again, all because of your "amish" comment ;^) reply to this
•  Haw!Actually I learned Smalltalk-72 first. (Well, I read the manual, though I never actually used it. My first taste of OOP, and dynamic languages, and GUIs.)I don't think there's anything that special about ST80 by today's standards. The graphics/windowing system was laughably primitive, and the language doesn't have much that today's hep scripting languages don't have, especially Ruby.There's this newer thing called Squeak that's like a slightly-modernized ST80; but as far as I can tell, it's interesting mostly for nostalgia value, like a Flock Of Seagulls reunion tour. reply to this
•  I have to write an assignment using Squeak. It's on the menu after Scheme, which starts next week. I like smalltalk ok, but Squeak is really confusing to use. :( reply to this
•  Kids these days... they should know what the CX register is for!I really can't think of a good way to explain this without falling back on the accumulator-register/retval-variable model of an accumulator.I think i would introduce alpha as the "variable type" concept, but maybe your students just aren't that "with it?" reply to this
•  I think folds are better thought of as catamorphisms. there is an intuition one can take away from such a discussion: folds replace all the constructors in a term with user-provided functions of the same shape, then evaluate the new term.for example, your fold_vars function is a very specific fold, replacing all the Var terms with a user-provided function and presumably replacing all other terms in the tree with a composition operator (right branch of And uses result of left, I'm guessing).you make your user-provided function take an extra value so that the user can thread an accumulator through the composition; but you will need to write such a fold for every possible family of traversal (eg. what if you want to visit Var nodes and And nodes?). a more general fold would take a function argument corresponding to each constructor in your formula type, and combine results however the user likes. that would let users replace for example all the leaves of the formula with sets, and all the other nodes with set union.I think the use of "list folds" in haskell / ML standard libraries damages people's perception of folds in general, because they come to think of them as only representing a single value propagation during a left-to-right or right-to-left traversal (foldl and foldr). this is because lists are simple linear structures with only one leaf and only two sensible traversal directions, so replacing CONS with some ('a * 'b -> 'b) function and NIL with some 'b value sort of makes the "accumulator" intuition work. but that intuition hides intuitions about more general folds. reply to this
•  awesome comment, thanks. reply to this