Recent changes to this wiki:

s/\.mdwn/.md/g
diff --git index.mdwn index.md
similarity index 100%
rename from index.mdwn
rename to index.md


mechanical attempt at inline
diff --git chap07.mod chap07.mod
index 8e6c50e..199438d 100644
--- chap07.mod
+++ chap07.mod
@@ -14,2141 +14,8 @@ functions instead of on data values.  Some of these take data
arguments and manufacture functions to order; others, like the F<imap>
function of X<imap|chapter>, transform one function into another one.

-=section Currying
-
-We have seen several times so far how to use callbacks to parametrize
-the behavior of a function so that it can serve many purposes.  For
-example, in R<dir_walk_callbacks|section> we saw how a generic
-directory-walking function could be used to print a list of dangling
-symbolic links, to return a list of interesting files, or to copy an
-entire directory.
-
-Callbacks are a way to make functions more general by supplying other
-functions to them as arguments.  We saw how to write functions that
-used closures to generate other functions as return values.  The
-I<currying> technique we'll see combines closures and callbacks,
-turning an ordinary function into a factory that manufactures
-functions on demand.
-
-Recall our F<walk_html> function from R<walk_html|chapter>.  Its
-arguments were an HTML tree and a pair of callbacks, one to handle
-plain text and one to handle tagged text.  We had found a way to use
-this to extract all the text that was enclosed in T<h1> tags:
-
-=inline extract_headers
-
-We then observed that it would make sense to abstract the T<h1> out of
-F<promote_if_h1tag>, to make it more general:
-
-=inline promote_if
-
-The second callback in F<walk_html> is rather peculiar.  It's an
-anonymous function that we manufactured solely to call F<promote_if>
-with the right arguments.  The previous version of the code was
-tidier.  What we need is a way to get F<promote_if> to I<manufacture>
-the F<promote_if_h1tag> function we need.  This seems like it should
-be possible, since after all F<promote_if> already knows how to
-perform the task that we want F<promote_if_h1tag> to perform.  All
-that we need to do is to have F<promote_if> wrap up that behavior into
-a new function:
-
-=startlisting promote_if_curried
-
-        sub promote_if {
-          my $is_interesting = shift; -* return sub { - my$element = shift;
-            if ($is_interesting->($element->{_tag}) {
-              return ['keeper', join '', map {$_->[1]} @_]; - } else { - return @_; - } -* } - } - -=contlisting promote_if_curried - -Instead of accepting both arguments right away, F<promote_if> now gets -the C<$is_interesting> callback only, and manufactures a new function
-that, given an HTML element, promotes it if it's considered
-interesting.  Making this change to F<promote_if>, to turn it from a
-function of two arguments into a function of one argument that returns
-a function of one argument, is called X<currying|d> it, and the
-version of F<promote_if> immediately above is the X<curried|d> version
-of F<promote_if>.N<Currying is so-named because it was popularized by
-Haskell B. Curry in 1930, although it had been discovered by Gottlob
-Frege in 1893 and rediscovered by Moses M<Schoenfinkel> in 1924.
-X<Frege, Gottlob|i> X<Curry, Haskell B.|i> X<M<Schoenfinkel>,
-Moses|i>>
-
-The happy outcome is that the call to F<walk_html> is now much simpler:
-
-          my @tagged_texts = walk_html($tree, - sub { ['maybe',$_[0]] },
-                                       promote_if('h1'),
-                                       });
-
-
-Once you get used to the idea of currying, you start to see
-opportunities to do it all over.  Recall our functions from R<power
-series|chapter> for adding and multiplying two streams together
-element-by-element: F<add2> and F<mul2>.
-
-        sub add2 {
-          my ($s,$t) = @_;
-          return unless $s &&$t;
-          node(head($s) + head($t),
-                       promise { add2(tail($s), tail($t)) });
-        }
-
-        sub mul2 {
-          my ($s,$t) = @_;
-          return unless $s &&$t;
-          node(head($s) * head($t),
-                       promise { mul2(tail($s), tail($t)) });
-        }
-
-These functions are almost identical.  We saw in R<callback|chapter>
-that two functions with similar code can often be combined into a
-single function that accepts a callback parameter.  In this case, the
-callback, C<$op>, specifies the operation to use to combine -C<head($s)> and C<head($t)>: - - sub combine2 { - my ($s, $t,$op) = @_;
-          return unless $s &&$t;
-          node($op->(head($s), head($t)), - promise { combine2(tail($s), tail($t),$op) });
-
-        }
-
-Now we can build F<add2> and F<mul2> from F<combine2>:
-
-        sub add2 { combine2(@_, sub { $_[0] +$_[1] }) }
-        sub mul2 { combine2(@_, sub { $_[0] *$_[1] }) }
-
-Since a major use of F<combine2> is to manufacture such functions, it
-would be more convenient for F<combine2> to do what we wanted in the
-first place.  We can turn F<combine2> into a factory that manufactures
-stream-combining functions by currying it:
-
-=startlisting combine2
-
-        sub combine2 {
-*         my $op = shift; -* return sub { -* my ($s, $t) = @_; - return unless$s && $t; - node($op->(head($s), head($t)),
-*                promise { combine2($op)->(tail($s), tail($t)) }); -* }; - } - -=endlisting combine2 - -Now we simply have - -$add2 = combine2(sub { $_[0] +$_[1] });
-        $mul2 = combine2(sub {$_[0] * $_[1] }); - -This may also be fractionally more efficient, since we won't have to do -an extra function call every time we call F<add2> or F<mul2>. F<add2> -is the function to add the two streams, rather than a function that -re-invokes F<combine2> in a way that adds two streams. - -If we want these functions to stick around, we can give them names, as -above; alternatively, we can use them anonymously: - - my$catstrs = combine2(sub { "$_[0]$_[1]" })->($s,$t);
-
-=test catstrs
-
-    use Stream qw(:all);
-    do 'combine2';
-
-    my $s = upto(1,4); - my$t = upto(5,9);
-    my $catstrs = combine2(sub { "$_[0]$_[1]" })->($s, $t); - - for my$want (qw(15 26 37 48)) {
-        is(head($catstrs),$want);
-        $catstrs = tail($catstrs);
-    }
-    is($catstrs,undef); - -=endtest - -Instead of the F<scale> function we saw earlier, we might prefer this -curried version: - - sub scale { - my$s = shift;
-          return sub {
-            my $c = shift; - return if$c == 0;
-            transform { $_[0] *$c } $s; - } - } - -F<scale> is now a function factory. Instead of taking a stream and a -number and returning a new stream, it takes a stream and manufactures -a function that produces new streams. C<$scale_s = scale($s)> returns -a function for scaling C<$s>; given a numeric argument, say C<$n>, -C<$scale_s> produces a stream that has the elements of C<$s> scaled -by C<$n>.  For example C<$scale_s-\>(2)> returns a stream whose every -element is twice C<$s>'s, and C<$scale_s-\>(3)> returns a stream whose -every element is three times C<$s>'s.  If we're planning to scale the
-same stream by several different factors, it might make sense to have
-a single scale function to generate all the outputs.
-
-Depending on how we're using it, we might have preferred to curry the
-function arguments in the other order:
-
-=listing scale
-

(Diff truncated)

pseudo-colophon
diff --git index.mdwn index.mdwn
index 2820c95..6d3eaa2 100644
--- index.mdwn
+++ index.mdwn
@@ -1 +1,5 @@
[[!map pages="chap*"]]
+
+-----
+
+_Generated with [[ikiwiki]] and [a very simple MOD plugin](https://github.com/schmonz/ikiwiki/compare/higherorderperl)._


Added a comment: I can't edit, only comment
diff --git chap02/comment_1_4bcee6d3d974bbff7578ad4184eef6c7._comment chap02/comment_1_4bcee6d3d974bbff7578ad4184eef6c7._comment
new file mode 100644
index 0000000..b4ade9d
--- /dev/null
+++ chap02/comment_1_4bcee6d3d974bbff7578ad4184eef6c7._comment
@@ -0,0 +1,8 @@
+[[!comment format=mdwn
+ username="schmonz"
+ ip="166.147.104.168"
+ subject="I can't edit, only comment"
+ date="2013-07-07T18:25:10Z"
+ content="""
+I'm not mjd so I'll have to make do.
+"""]]


blah blah
diff --git chap03.mod chap03.mod
index 5a5a23d..3786028 100644
--- chap03.mod
+++ chap03.mod
@@ -1,5 +1,4 @@

-
=note You forgot to use the word 'stub'.
This will make many paragraphs clearer.

@@ -210,6 +209,9 @@ we try to compute C<fib(17)> three times or C<fib(16)> five times
because the work will only be done once, and the cached results will
be retrieved quickly when they are needed again.

+M<x^2 + x + 1 = 0>
+
+
=section Inline Caching

The most straightforward way to add caching to a function is to give


an example web edit
diff --git chap01.mod chap01.mod
index f0346cb..d229815 100644
--- chap01.mod
+++ chap01.mod
@@ -1,5 +1,4 @@

-
=chapter Recursion and Callbacks

R<callback|HERE>
@@ -8,7 +7,7 @@ X<Recursion|d> is a method of solving a problem by reducing it to a
simpler problem of the same type.

Unlike most of the techniques in this book, recursion is already
-well-known and widely-understood.  But it will underlie several of the
+well known and widely understood.  But it will underlie several of the
later techniques, and so we need to have a good understanding of its
fine points.


initial commit
diff --git .gitignore .gitignore
new file mode 100644
index 0000000..eecda60
--- /dev/null
+++ .gitignore
@@ -0,0 +1 @@
+/.ikiwiki
diff --git chap01.mod chap01.mod
new file mode 100644
index 0000000..f0346cb
--- /dev/null
+++ chap01.mod
@@ -0,0 +1,2368 @@
+
+
+=chapter Recursion and Callbacks
+
+R<callback|HERE>
+The first advanced' technique we'll see is X<recursion>.
+X<Recursion|d> is a method of solving a problem by reducing it to a
+simpler problem of the same type.
+
+Unlike most of the techniques in this book, recursion is already
+well-known and widely-understood.  But it will underlie several of the
+later techniques, and so we need to have a good understanding of its
+fine points.
+
+=section Decimal to Binary Conversion
+
+Until the release of Perl 5.6.0, there was no good way to generate a
+binary numeral in Perl.  Starting in 5.6.0, you can use
+C<sprintf("%b", $dec)>, but before that the question of how to do this +was Frequently Asked. + +Any whole number has the form M<2k+b>, where V<k> is some smaller +whole number and V<b> is either 0 or 1. V<b> is the final bit of the +binary expansion. It's easy to see whether this final bit is 0 or 1; +just look to see whether the input number is even or odd. The rest of +the number is M<2k>, whose binary expansion is the same as for V<k>, +but shifted left one place. For example, the number M<37 = 2 * 18 + +1>; here V<k> is 18 and V<b> is 1, so the binary expansion of 37 +(100101) is the same as that for 18 (10010), but with an extra 1 on +the end. + +How did I compute the expansion for 37? It is odd, so the final bit +must be 1; the rest of the expansion will be the same as the expansion +for 18. How can I compute the expansion for 18? 18 is even, so its +final bit is 0, and the rest of the expansion is the same as the +expansion for 9. What is the binary expansion for 9? 9 is odd, so +its final bit is 1, and the rest of its binary expansion is the same +as the binary expansion of 4. We can continue in this way, until +finally we ask about the binary expansion of 1, which of course is 1. + +This procedure will work for any number at all. To compute the binary +expansion of a number V<n> we proceed as follows: + +=numberedlist + +=item If V<n> is 1, its binary expansion is 1, and we may ignore the + rest of the procedure. Similarly, if V<n> is 0, the expansion + is simply 0. + Otherwise: + +=item Compute V<k> and V<b> so that M<n = 2k + b> and M<b = 0 {\rm or} 1>. + To do this, simply divide V<n> by 2; V<k> is the quotient, and M<b> + is the remainder, 0 if V<n> was even, and 1 if V<n> was odd. + +=item Compute the binary expansion for V<k>, using this same method. + Call the result V<E>. + +=item The binary expansion for V<n> is M<Eb>. + +=endnumberedlist + +Let's build a function called F<binary> that does this. Here +is the preamble, and step 1: + +=listing binary + + sub binary { + my ($n) = @_;
+          return $n if$n == 0 || $n == 1; + +Here is step 2: + + my$k = int($n/2); + my$b = $n % 2; + +For the third step, we need to compute the binary expansion of V<k>. +How can we do that? It's easy, because we have a handy function for +computing binary expansions, called F<binary>---or we will once we're +finished writing it. We'll call F<binary> with V<k> as its argument: + + my$E = binary($k); + +Now the final step is a string concatenation: + + + return$E . $b; + } + +=endlisting binary + +=test binary 51 + + eval { require 'binary' }; + for (0..50) { + my$bin = sprintf "%b", $_; + my$b2 = binary($_); + is($b2, $bin, "$_ => binary");
+        }
+
+=endtest
+
+
+This works.  For example, if you invoke C<binary(37)> you get the
+string C<100101>.
+
+The essential technique here was to I<reduce the problem to a
+simpler case.> We were supposed to find the binary expansion of a
+number V<n>; we discovered that this binary expansion was the
+concatenation of the binary expansion of a smaller number V<k> and a
+single bit V<b>.  Then to solve the simpler case of the same problem,
+we used the function F<binary> in its own definition.  When we
+invoke F<binary> with some number as an argument, it needs to
+compute F<binary> for a different, smaller argument, which in turn
+computes F<binary> for an even smaller argument. Eventually, the
+argument becomes 1, and F<binary> computes the trivial binary
+representation of 1 directly.
+
+This final step, called the X<base case|d> of the recursion, is
+important.  If we don't consider it, our function might never
+terminate.  If, in the definition of F<binary> above, we had omitted
+the line
+
+          return $n if$n == 0 || \$n == 1;
+
+then F<binary> would have computed forever, and would never have
+produced an answer for any argument.
+
+=section Factorial
+
+Suppose you have a list of V<n> different items.  For concreteness,
+we'll suppose that these items are letters.  How
+many different orders are there for such a list?  Obviously, the
+answer depends on V<n>, so it is a function of V<n>.  This function is
+called the X<factorial function|d>.  The factorial of V<n>
+is the number of different orders for a list of V<n> different items.
+Mathematicians usually write it as a postfix M<!> mark, so that the
+factorial of V<n> is M<n!>.  They also call the different orders
+X<permutations|d> .
+
+Let's compute some factorials.  Evidently, there's only one way to
+order a list of 1 item, so M<1! = 1>.  There are two permutations of a
+list of two items: C<A-B> and C<B-A>, so M<2!=2>.  A little
+pencil work will reveal that there are six permutations of three
+items:
+
+        C  AB        C  BA
+        A C B        B C A
+        AB  C        BA  C
+
+How can we be sure we didn't omit anything from the list?  It's not
+hard to come up with a method that constructs every possible ordering,
+and in R<permutations|chapter> we will see a program to list them all.
+Here is one way to do it.  We can make any list of three items by
+adding a new item to a list of two items.  We have two choices for the
+two-item list we start with: C<AB> and C<BA>.  In each case, we have
+three choices about where to put the C<C>: at the beginning, in the
+middle, or at the end. There are M<2\cdot3=6> ways to make the choices
+together, and since each choice leads to a different list of three
+items, there must be six such lists.  The left column above shows all
+the lists we got by inserting the C<C> into C<AB>, and the right
+column shows the lists we got by inserting the C<C> into C<BA>, so the
+display above is complete.
+
+Similarly, if we want to know how many permutations there are of four
+items, we can figure it out the same way.  There are six different
+lists of three items, and there are four positions that we could
+insert the fourth item into each of the lists, for a total of
+M<6\cdot4=24> total orders:
+
+        D  ABC    D  ACB    D  BAC    D  BCA    D  CAB    D  CBA
+        A D BC    A D CB    B D AC    B D CA    C D AB    C D BA
+        AB D C    AC D B    BA D C    BC D A    CA D B    CB D A
+        ABC  D    ACB  D    BAC  D    BCA  D    CAB  D    CBA  D
+
+
+Now we'll write a function to compute, for any V<n>, how many
+permutations there are of a list of V<n> elements.
+
+=note
+%%  Why would we care?
+%% Because lists are fundamental to computer programming and we need to
+%% know many basic facts about them.
+%% Analogy with sin() and cos()
+
+We've just seen that if we know the number of possible permutations of
+M<n-1> things, we can compute the number of permutations of V<n>
+things.  To make a list of V<n> things, we take one of the M<(n-1)!>

(Diff truncated)
`