1. Databases
    1. Operator Overloading


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


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

        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

        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)