## 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 operators20010824 Program (with iterators) to generate all the strings thatmatch 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 product20020121 Maybe move the currying section here from Chap. VI?20020123 More examples of functions produced by 'reduce'? Wheredid 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 anany-ary operator. e.g., turns a+b into sum(@p); gcd(a,b) into gcd(@p); concat2() into concatmany(); merge2 into mergeYou should be able to define generic and and or operators that workreasonably on any kind of iterator.Analogues of 'fold' for other data structures. Generic function forHTML 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