Version 1 of fold

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 | Category Concept | Functional Programming ]