blob: 8252d2014433ad642efbd64e107a3266b45620aa (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
---
format: rst
toc: no
...
===================================
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.
|
