An In-Depth Problem using HOF/lambda/Recursion

(Was going to be on the exam … I’ve modified it slightly.)

This exercise is about writing a function called 'uber-hof' that will single-handedly replace accumulate, keep, and every (and will be able to do all of the possible combinations of all of these). Your uber-hof takes 5 arguments: 'combinerf', 'postmapf', 'keeperf', 'premapf' (all of which are functions) and 'sent' (which is a sentence) and should do the following:

1. Apply premapf to all of the elements of sent to form another sentence (sent2).

2. Apply keeperf to the second sentence (sent2) and keeps only the values that resolve to #t in a third sentence (sent3, which is a subset of sent2)

3. Apply postmap to all of the elements of the third sentence (sent3) to form a new sentence (sent4)

4. Accumulates all of the elements of sent4 using combinerf and returns this final value.

For example:

(uber-hof + (lambda (x) (+ 1 x)) even? (lambda (x) (* 3 x)) ‘(1 2 3 4)) è 20

Part I: Look at the data-flow diagrams for every, keep and accumulate given on pages 110-111 of simply scheme. Draw a similar diagram for uber-hof. Your diagram should follow the same conventions as those in the book. [Purpose: To understand the data-flow of HOF composition.]

Part II: Define uber-hof using only other higher-order functions. You will receive no credit for solutions that use recursion or lambda. [Purpose: To demonstrate that you know how to use and compose HOFs]

Part III: Define a procedure named 'uber-hof-maker' that takes as arguments the first four arguments to uber-hof (combinerf, postmapf, keeperf, and premapf) and returns a procedure that takes one argument, viz. sent, and computes the uber-hof (using those four arguments) of sent. [Purpose: Using lambda to make procedure-makers … this is different than simply using lambda in a procedure.]

Part IV: Using uber-hof-maker, redefine keep, every, and accumulate. Your new keep, every, and accumulate only need to works for sentences -- you do not need to handle words. [Purpose: To demonstrate understanding of procedure-makers as well as ability to short-circuit functions.] You may find it useful to use the following defined function:

(define I (lambda (x) x))

Part V: Re-define uber-hof using no HOFs, no lambdas, and no helper functions -- this means that you will have to resort to some kind of embedded recursion. For simplicity's sake, you may assume that the function that is passed in as 'combinerf' will be able to handle 0, 1, and 2 arguments without crashing (like + does). If your solution uses a helper function, you will receive, at most, half-credit. If your solution uses other HOFs, you will receive no credit. [Purpose: To do conceptually simple yet practically daunting recursions using only the basic tools.]

Part VI: Do you think that it is possible to write uber-hof-maker recursively without using helper functions or other HOFs (like we did for uber-hof in PartV)? If so, do it. If not, say why not and what you would need in order to be able to do it. [Purpose: To demonstrate deep understanding of the limitations of lambda (as presented in this class). If you want an interesting explanation of how to get around this problem, ask Prof. Dan (for the good explanation) or me (for the not-so-good one) in office hours.]

CAVEAT: This not intended as a comprehensive review of material for the exam.