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)