## 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'