Designing programs with every, keep, and accumulate

Here are some tactics for designing with the higher-order procedures every, keep, and accumulate.

First, decide how the output compares to the input.

One may observe that every and keep may be viewed as producing a combination of all the words in their input sentence or of all the characters in their input word. Indeed, every and keep may be implemented as calls to accumulate.

Suppose you decide to use every or keep. How do you decide on the procedure to use as its argument?

Let's start with every. We'll assume for simplicity that the second argument to every will be a sentence—of course, it can also be a word—and we'll call this argument sent. We'll call the procedure argument proc.

Here's an example, the prepend-every procedure in Simply Scheme exercise 9.5. What's needed is a procedure that, given a word named prefix and a sentence, returns the result of prefixing prefix onto each word in the sentence.

    > (prepend-every 's '(he aid he aid))
    (she said she said)

We start with a procedure header:

    (define (prepend-every prefix sent)
We continue by observing that every is probably an appropriate higher-order procedure, and that it will apply some procedure to every word in sent:
    (define (prepend-every prefix sent)
      (every
        _____
        sent ) )
What's needed is a procedure that attaches prefix to the beginning of each word in sent. At first glance, that would require a procedure with two inputs, the prefix and the word. However, a lambda expression inside prepend-every can use all the placeholders that prepend-every makes available. In particular, it can use prefix without having it as a placeholder of its own. Here's the complete definition.
    (define (prepend-every prefix sent)
      (every
        (lambda (wd) (word prefix wd))  ; prefix is prepend-every's placeholder
        sent) )

The keep higher-order procedure is used in pretty much the same way. Its procedure argument, like that of every, takes one argument. We'll call the procedure argument pred, since it's a predicate. If keep's second argument is a sentence, then pred will be applied to each word in the sentence. If keep's second argument is a word, then pred will be applied to each character in the word. The success or failure of this application determines whether the word or character appears in keep's result.

Suppose you decide to use accumulate. How do you decide on the procedure to use as its argument?

Again, let's give the arguments names. The procedure argument can be combiner. We'll assume for now that the second argument is a word, which we'll call wd.

The combiner procedure will take two arguments, which represent the things being combined. The first is one of the characters in wd. The second is a "so far" argument, similar to what we saw in accumulating recursions. Combiner is applied to the character and the "so far" to get the next "so far" value.

Here's an example, reversal of the characters in a word. We choose to implement this with accumulate. (An aside: why would every not work? What helper procedure would allow the use of every, at least on words whose characters are all different letters?) Here's a framework:

    (define (wd-reverse wd)
      (accumulate
        (lambda (char reversed-so-far) _____ )
        wd) )
How do we "accumulate" the character into the reversed word we have so far? We merely attach it to the end:
    (define (wd-reverse wd)
      (accumulate
        (lambda (char reversed-so-far) (word reversed-so-far char))
        wd) )
We urge you to test this using the Replacement Modeler, which may help solidify your understanding of how accumulate works.