# software/functional programming

# 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 x+1;
def how_long_col(x, col):
"""call this as how_long_col(<collection>, lambda b: b)"""
if not 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.