summaryrefslogtreecommitdiffstats
path: root/software/functional programming
diff options
context:
space:
mode:
authorbnewbold <bnewbold@eta.mit.edu>2009-01-14 16:24:34 -0500
committerbnewbold <bnewbold@eta.mit.edu>2009-01-14 16:24:34 -0500
commit823441e43dd007d4e8931fb236ffbeada12eabd2 (patch)
tree13a9aa9f4f980f283cf56bccda2370a83aa088c8 /software/functional programming
parenta2574206f1150354083df6c43506b40429efc9a4 (diff)
downloadknowledge-823441e43dd007d4e8931fb236ffbeada12eabd2.tar.gz
knowledge-823441e43dd007d4e8931fb236ffbeada12eabd2.zip
bunch of new
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.
+