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

[LV] If the above discussion doesn't seem to match the context of fold that you were seeking, another use of the word ''fold'', in the context of text editing, is the idea of [text widget elision], or representing one or more lines of text with a place holder.  Some text editors call this ''text folding''.

[escargo] - This use of ''fold'' reminded me of something, and I couldn't remember what.
Then I recalled:  It reminds me of the [APL] '''reduce''' operator '''/''', where

 +/A

would add up all of the values of the vector A.

[NEM] - Yup, lots of languages have a similar function, and "reduce" is a common name for it, e.g. that is
what it is called in Python (although, not for much longer [http://www.artima.com/weblogs/viewpost.jsp?thread=98196]).
Fold is a very powerful and general function [http://www.cs.nott.ac.uk/~gmh/bib.html#fold] which captures a
particular pattern of recursion (or iteration) over a container. Used with other higher-order functions like
[map], [filter], and [zip] you can start doing some really powerful programming with a few statements (e.g.,
this [http://c2.com/cgi/wiki?TransfoldPattern] discussion of the Transfold Pattern). 
----
[RS] 2005-09-21: for non-empty lists and [expr] operators, the following does a very simple fold (but see [Elegance vs. performance]):
 expr [join $list $op]
The neutral element, if ''list'' is empty, would be 0 for "+", 1 for "*"... and the others?

[escargo] - By "neutral element" do you mean "identity value"?  (That is, the assumed element would be
whatever is the identify value for the particular operation?)

[NEM]: Yes, that's right. What I labelled "init" in the above definition is often more correctly labelled "id".
Here's a handful of operations defined using folds:

 proc foldl {f id list} {
   if {[llength $list] == 0} {
     return $id
   } else {
     foldl $f [apply $f $id [lindex $list 0]] \
              [lrange $list 1 end]
   }
 }
 # Expose some of expr as procs:
 foreach op {+ - * / && ||} { proc $op {a b} "expr \$a $op \$b" }
 proc count {x n} { incr n }
 proc swap {head tail} { linsert $tail end $head }
 proc def {name = args} { interp alias {} $name {} {expand}$args }
 def sum     = foldl + 0
 def product = foldl * 1
 def diff    = fold - 0
 def div     = fold / 1.0
 def and     = fold && 1  ;# 1 == true
 def or      = fold || 0  ;# 0 == false
 def length  = fold count 0
 def reverse = fold swap [list]

And so on. You can also define [map] and [filter] in terms of fold, but it's easier with [lambda].
 

----
[[ [Category Glossary] | [Category Concept] | [Functional Programming] ]]