[NEM]: The ''fold'' function reduces a list (or other structure) to a single value by "folding" a binary
operator between successive elements of the list. To illustrate, if you have a list containing
numbers such as:
 1 2 3 4 5
Then to sum that list you can fold a binary + operator between the elements, resulting in something
like:
 1 + 2 + 3 + 4 + 5
(assuming infix notation). This is essentially what the "fold" function does. It takes a binary
function, together with an initial value (to tack on to the end of the list) and a list:

 proc fold {func init list} {
   if {[llength $list] == 0} {
     return $init
   } else {
     apply $func [lindex $list 0] \
                 [fold $func $init [lrange $list 1 end]]
   }
 }
 proc apply {func args} { uplevel #0 $func $args }

So, we can do our sum over a list by:
 proc + {a b} { expr {$a + $b} }
 fold + 0 {1 2 3 4 5} ;# produces 15 as the answer

You may have noticed that the version of fold above is right-associative. In other words, the result
it produces is equivalent to doing:
 1 + (2 + (3 + (4 + (5 + 0))))

With some operators, it might make more sense to have the reduction be done in a left-associative manner.
We can define a foldl which does this easily enough. I'll leave that (and converting the definition
given above to a more efficient iterative version) as an exercise.

You might wonder if we can perform the reverse operation, i.e., go from a value and a function that
takes a single argument and produces a pair of results and from that generate a sequence/list. Well, you
can indeed, and this is roughly equivalent to [iterators]. There is a demonstration of this ''unfold''
operation on that page.
----
[Category Glossary]