blob: 7fa13585c7fdae156dcf8268211e2ba165d27713 (
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
|
---
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 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.
|
