Table of Contents for Programming Languages: a survey

"what is a recursion scheme? Basically, they are formalized and dissected looping patterns in functional programming. In imperative programming, loops are basically unstructured—a for or while loop can do many different things:

    transform the contents data structure
    combine the contents of a data structure into another value
    build up a data structure step by step
    combine two (or more!) data structures in non-trivial ways
    iteratively compute some result
    something else, arbitrarily complex
    any combination of the above

One of the immediate wins from everyday functional programming is that it gives us the terms to talk about these patterns—both abstractly and, more importantly, in code. In particular, higher-order functions abstract over the most common patterns:

    transforms each element of a data structure
    combines all the elements of a data structure into something else
    builds up a data structure step by step
    combines two structures
    , well, iteratively computes some result

These are specific examples of what a loop can do—there are, of course, more besides. In many cases, these functions operate on lists specifically rather than arbitrary structures, but they can usually be generalized (sometimes in different ways) to other structures as well.

The advantage to having a bunch of different named patterns like this is twofold: it makes the intentions behind your code clearer and it makes it harder to make mistakes. When you see a


, you immediately know that it will transform the contents of a data structure without affecting its shape. You can't know this from a for or while loop! Similarly, using


prevents all sorts of mistakes; since you can only consider one element at a time, you can't accidentally reorder or skip any of them. Off-by-one errors become a thing of the past! " --

backwards GOTO


in some languages (for example, Lua version 5.1 and up, according to [1], section "Loop Instructions", page 42), a different loop variable is created for each iteration of the loop.

"Consider the following, where loop index i is used as an upvalue in the instantiation of 10 functions:

local a = {}
for i = 1, 10 do
  a[i] = function() return i end

Lua 5.0.2 will print out 10, while Lua 5.1 will print out 5. In Lua 5.0.2, the scope of the loop index encloses the for loop, resulting in the creation of a single upvalue. In Lua 5.1, the loop index is truly local to the loop, resulting in the creation of 10 separate upvalues." -- [2]

In some languages, for loops can have an optional clause that executes when the loop completes normally (without a 'break'). In Python this is called 'else' Python; 'nobreak' has been suggested as a more intuitive name [3] [4]. The founder of Python has stated that if he could do it over, he would not have included this feature [5].

with step