=================================== Functional Programming =================================== Recursion -------------- **Partial** functions can recurse endlessly over a finite input. **Total** functions will terminate/halt over a finite input. (TODO: check this definition) Collectors -------------- The collector concept/pattern/paradigm is the one I am least familiar with in functional programming. My current understanding is that they essentially allow allow recursive functions to maintain something like state by wrapping immutable functions or variables in layer after layer of functions and just holding on to the outermost layer. For instance, the typical way to write a ``length`` function in python would be:: >>> def how-long(x): >>> l = 0 >>> while x.has_next() >>> l = l+1; >>> x.pop() >>> return l Using recursion, we could do:: >>> def how-long-recurse(x): >>> if x.has_next() >>> x.pop() >>> return how-long-recurse(x) + 1 >>> else >>> return 0 Using the collector paradigm, we could do:: >>> def add1(x): return a+1; >>> def how-long-col(x, col): >>> if x.has_next() >>> return col(0) >>> else >>> x.pop() >>> return how-long-col(x, lambda a: col(add1(a))) The first two ways, the plus one operation is actually executed at any given time, while with the collector implementation we're really creating a function step by step which will give the answer at the end when it is all executed.