Functional programming and looping

This is a pretty decent summary, I think. It uses Ruby, and it's worth noting some of the procedures are also known by other names:

map -- Perform a function on every value in a list individually, as a transformation. As an easy example, map square [1, 2, 3, 4, 5] -> [1, 4, 9, 16, 25]. This is usually just called "map" (it's short), but is different thing than a key->value map. The sequence of execution here is deliberately unspecified, and for potentially expensive/time-consuming operations this can be an easy operation to parallelize.

list.each -- Iterate through a list, doing something for each value. AKA foreach or List.iter. This is different from map in that it discards the result; it is just used for side-effects.

select -- AKA filter, called remove-if-not in Common Lisp. This returns a list of all values in a list meeting some criteria (a predicate, a function that returns a bool, is passed in): filter even [1, 2, 3, 4, 5] -> [2, 4].

reduce -- AKA fold - Starting with a default value (often the identity for a function, e.g. 0 for adding and 1 for multiplication), successively apply a two-argument operation to the current total and the values of the list, reducing it down to one overall result: reduce * 1 [1, 2, 3, 4, 5] -> (((((1 * 1) * 2) * 3) * 4) * 5). NB: Some languages make a distinction between a left fold and a right fold, which refers to whether it starts at the beginning or the end of the (potentially infinite!) list.

Of course, one of the common knocks on Ruby is that naively referring to a function executes it, and to pass functions around avoiding

  list.map { |i| process i }

one must write

  list.map &method(:process)

or, as the Rails guys have done [1], open up Symbol#to_proc so that

  list.map &:process

works. This will be part of core Ruby in 1.9, but last I heard it's slow [2].

[1] http://github.com/rails/rails/tree/master/activesupport/lib/...

[2] http://www.ruby-forum.com/topic/161089