summaryrefslogtreecommitdiffstats
path: root/software/functional programming
diff options
context:
space:
mode:
authorbryan newbold <bnewbold@snark.mit.edu>2009-01-22 23:04:17 -0500
committerbryan newbold <bnewbold@snark.mit.edu>2009-01-22 23:04:17 -0500
commit7218768aba3a43f1a62867f35f05cb85a30d7ed2 (patch)
treeacfc09cc29bcb6c543a760ede6a399375a8c92ab /software/functional programming
parent0f238f885ff64a94c2bfb2906b5f1e8edb93dc0c (diff)
parentf18ba63a8b3d39bc9f2ca8dbe6d766d0dd5f77ec (diff)
downloadknowledge-7218768aba3a43f1a62867f35f05cb85a30d7ed2.tar.gz
knowledge-7218768aba3a43f1a62867f35f05cb85a30d7ed2.zip
Merge branch 'master' of ssh://animus.robocracy.org/srv/git/knowledge
Diffstat (limited to 'software/functional programming')
-rw-r--r--software/functional programming52
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.
+