advanced_lambda.mdwn

   1 [[!toc]]
   2
   3
   4 #Version 4 lists: Efficiently extracting tails#
   5
   6 Version 3 lists and Church numerals are lovely, because they have their recursive capacity built into their very bones. However, one disadvantage
   7 to them is that it's relatively inefficient to extract a list's tail, or get a
   8 number's predecessor. To get the tail of the list `[a;b;c;d;e]`, one will
   9 basically be performing some operation that builds up the tail afresh: at
  10 different stages, one will have built up `[e]`, then `[d;e]`, then `[c;d;e]`, and
  11 finally `[b;c;d;e]`. With short lists, this is no problem, but with longer lists
  12 it takes longer and longer. And it may waste more of your computer's memory
  13 than you'd like. Similarly for obtaining a number's predecessor.
  14
  15 The v1 lists and numbers on the other hand, had the tail and the predecessor
  16 right there as an element, easy for the taking. The problem was just that the
  17 v1 lists and numbers didn't have recursive capacity built into them, in the
  18 way the v3 implementations do.
  19
  20 A clever approach would marry these two strategies.
  21
  22 Version 3 makes the list `[a;b;c;d;e]` look like this:
  23
  24         \f z. f a (f b (f c (f d (f e z))))
  25
  26 or in other words:
  27
  28         \f z. f a <the result of folding f and z over the tail>
  29
  30 Instead we could make it look like this:
  31
  32         \f z. f a <the tail itself> <the result of folding f and z over the tail>
  33
  34 That is, now `f` is a function expecting *three* arguments: the head of the
  35 current list, the tail of the current list, and the result of continuing to
  36 fold `f` over the tail, with a given base value `z`.
  37
  38 Call this a **version 4** list. The empty list can be the same as in v3:
  39
  40 <pre><code>empty &equiv; \f z. z</code></pre>
  41
  42 The list constructor would be:
  43
  44 <pre><code>make_list &equiv; \h t. \f z. f h t (t f z)</code></pre>
  45
  46 It differs from the version 3 `make_list` only in adding the extra argument
  47 `t` to the new, outer application of `f`.
  48
  49 Similarly, `five` as a v3 or Church numeral looks like this:
  50
  51         \s z. s (s (s (s (s z))))
  52
  53 or in other words:
  54
  55         \s z. s <the result of applying s to z (pred 5)-many times>
  56
  57 Instead we could make it look like this:
  58
  59         \s z. s <pred 5> <the result of applying s to z (pred 5)-many times>
  60
  61 That is, now `s` is a function expecting *two* arguments: the predecessor of the
  62 current number, and the result of continuing to apply `s` to the base value `z`
  63 predecessor-many times.
  64
  65 Jim had the pleasure of "inventing" these implementations himself. However,
  66 unsurprisingly, he wasn't the first to do so. See for example [Oleg's report
  67 on P-numerals](http://okmij.org/ftp/Computation/lambda-calc.html#p-numerals).
  68
  69