Products
So far nearly all of our transformations of stream values have been essentially one-dimensional, like map() and grep(), which take as input sequences of values and which emit sequences of new values in the same order. Similarly, functions like add2() take in two sequences and return a single sequence.
One important type of operation we haven't covered so far produces a fundamentally two-dimensional result. The simplest example is called the Cartesian product. Given two streams, (a_1, a_2, a_3, ...) and (b_1, b_2, b_3, ...) the Cartesian product contains all possible pairs of elements from the two streams:
(a1, b1) (a1, b2) (a1, b3) ...
(a2, b1) (a2, b2) (a2, b3) ...
(a3, b1) (a3, b2) (a3, b3) ...
...
To see why this might be useful, consider the Unix shell's wildcard expansion. An expression of the form {a,b,c} in the shell will expand to each of the strings a, b, and c. So, for example, the command
rm tricks.{ps,pdf}
is equivalent to
rm tricks.ps tricks.pdf
One can combine wildcards; this:
rm tricks.{ps,pdf}{,.gz}
expands to this:
rm tricks.ps tricks.ps.gz tricks.pdf tricks.pdf.gz
(The {,.gz} expands to either the empty string or to ".gz".)
The general rule for expanding such expressions is that an expression of the form
A{B,C,..,Y}Z
expands to
ABZ ACZ ... AYZ
If any of B, C, ... Y, or Z contains further braces, then the result above is expanded further. So, returning the the example above,
rm tricks.{ps,pdf}{,.gz}
is expanded first to
rm tricks.ps{,.gz} tricks.pdf{,.gz}
(here A is "tricks." and Z is "{,.gz}"); then tricks.ps{,.gz} is expanded:
rm tricks.ps tricks.ps.gz tricks.pdf{,.gz}
and finally
rm tricks.ps tricks.ps.gz tricks.pdf tricks.pdf.gz
Text-based database? (Tibia?) demonstrate composition operators
20010824 Program (with iterators) to generate all the strings that
match a certain regex. Use Japhy's parser? Have a bounded-length
and an unbounded-length version. Interesting composition operators
here.
append, ordered merge, ordered and, cartesian product
20020121 Maybe move the currying section here from Chap. VI?
20020123 More examples of functions produced by 'reduce'? Where
did you read about the use of 'fold', anyway? One of those papers
in ~mjd/misc/papers/FP? One possibility: Graham Hutton's paper "A
tutorial on the universality and expressiveness of fold" in
.../fold.ps. Also I think it was in the Bird and Wadler book on
functional programming.
Examples: Given list of digits, construct base-10 number.
Given list of path components, resolve to inodes. (e.g., ("/",
"usr", "local", "bin", "ezmlm", "ezmlm-make") => (2, 277985,
2130089, 3229158, ...) or resolve to true paths: -> ("/", "/usr",
"/data/local", "/data/local/bin", ...). Given a hash and a list of
keys, produce a list of values.
20020121 Don't forget to use game trees as an example somewhere.
Reread the Hughes paprt on why FP matters; it has an extensive
example of how to build a game tree search using functional
techniques.
20020123 Function to turn streams into chapter-4 iterators.
20030919 Function that takes a binary operator and turns it into an
any-ary operator. e.g., turns a+b into sum(@p); gcd(a,b) into
gcd(@p); concat2() into concatmany(); merge2 into merge
You should be able to define generic and and or operators that work
reasonably on any kind of iterator.
Analogues of 'fold' for other data structures. Generic function for
HTML trees: supply callback for empty tree, for text node, for tag
node. Generic function for directory hierarchies: Supply callback
for directory, for nondirectory file.
I think they won't disappear entirely, but they will turn into a single chapter. Here's a revised outline:
VII. Higher-order functions
* Refer back to currying examples from Ch. VI; 'function factories'
* Curried file tree walker (variation on Ch. I example)
* curried version of ordered merge from Ch. VI
* 'reduce' and 'combine'
* For lists
* For streams
* Abstract versions of 'reduce' and 'combine'
* 'fold'
* 'fold' is universal!
* Extended example: Database queries
* simple queries ('name = "Smith"')
* 'and'; 'or'; 'not'
* operator overloading (sets up technique for Ch. IX)
TOP