Merge branch 'master' of ssh://animus.robocracy.org/srv/git/knowledge

1 files changed, 52 insertions, 0 deletions

diff --git a/software/functional programming b/software/functional programming
new file mode 100644
index 0000000..4720280
--- /dev/null
+++ b/software/functional programming
@@ -0,0 +1,52 @@
+===================================
+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.
+