Difference between revision 2 and current revision
No diff available.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:
map
transforms each element of a data structure
fold
combines all the elements of a data structure into something else
unfold
builds up a data structure step by step
zipWith
combines two structures
iterate
, 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
map
, 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
map
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! " -- http://www.quora.com/What-are-Zygohistomorphic-prepromorphisms-and-how-are-they-used
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 end print(a[5]())
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].