We have seen that it is possible to write our own higher-order procedures. Scheme also includes a number of built-in higher-order procedures. You can read about many of them in section 6.4 of the Scheme report (r5rs), which is available through the DrScheme Help Desk. Here are some of the more popular ones. You already know about the basic use of the map procedure. After our discussion above, you also know how one might implement it. It turns out that map has some additional capabilities. For example, you can apply a procedure to multiple lists (in which case it takes the corresponding value from each list). One of the most important built-in higher-order procedures is apply, which takes a procedure and a list as arguments and invokes the procedure, giving it the elements of the list as its arguments: > (apply string=? (list "foo" "foo")) #t > (apply * (list 3 4 5 6)) 360 > (apply append (list (list 'a 'b 'c) (list 'd) (list 'e 'f) null (list 'g 'h 'i))) (a b c d e f g h i)

At this point, you've seen many other design patterns that typically involve recursion. You may find it valuable to design corresponding procedures to encapsulate those patterns. Here are some of the patterns you may wish to think about: fold, which inserts a binary (two parameter) operation between all of values in a list. For example, sum inserts a plus between neighboring values in a list (i.e., (sum (list 1 2 3 4)) is 1+2+3+4). Similarly, product inserts a times between neighboring values. If we had defined fold (see the lab), we might define sum as (define sum (lambda (lst) (fold + lst))) tally, which counts the number of values in a list that meet a particular predicate. For example, to count the number of odd values in a list, we would use > (tally odd? lst) Similarly, to count the number of sevens or elevens in a list, we might use > (tally (lambda (v) (or (= 7 v) (= 11 v))) lst) select, which selects all elements of a list that match a particular predicate. For example, > (select odd? (list 1 2 3 4 5 6 7)) (1 3 5 7) remove, which removes all elements of a list that match a particular predicate. For example, > (remove odd? (list 1 2 3 4 5 6 7)) (2 4 6)

We can use a more advanced technique to build a procedure that builds list predicates. We'll write a procedure, make-list-pred that takes one parameter, a predicate, and returns a procedure of one parameter, a list, and determines whether the predicate holds for every element of the list. Since we need to build a recursive procedure, we'll use letrec to build that procedure. It's now even simpler to define our favorite list predicates. > (define all-int? (make-list-predicate integer?)) > (define all-rgb? (make-list-predicate rgb?)) > (define all-odd? (make-list-predicate odd?)) > (all-int? null) #t > (all-int? (list 1 2 3)) #t > (all-int? (list 1 2.5 3)) #f > (all-int? 1) #f > (all-odd? (list 1 3 5)) #t > (all-odd? (list 1 2 3 4 5)) #f > (all-odd? (list 1 2.5 2)) Error: Requires integer. That last error message is a direct result of the author ignoring the preconditions of make-list-predicate. Since odd? can't be applied to all values, (make-list-predicate odd?) is not guaranteed to work. There's also an important benefit to using higher-order procedures, suggested by the final all-int? example. As that example suggests, we've succeeded in not only defining the procedure more concisely, we've also defined it more generally. (The old all-int? would crash if given a non-list as a parameter.) That means that all of the procedures we define with make-list-predicate benefit from this change. If we make other improvements, they are automatically propagated to other procedures.

Here are some common procedures that you might use to build other procedures. Not all are predefined in Scheme. We've included some definitions. You should be able to write the others. (left-section binary-proc arg1) creates a new procedure by filling in the first argument of a binary procedure. For example, we might define a procedure that multiplies a value by 2 with > (define mul2 (left-section * 2)) The left-section procedure is surprisingly powerful. Note that with a little more work, we could even use it to define a variant of make-list-predicate. (define make-list-predicate (lambda (pred?) (left-section all pred?))) The code for left-section is relatively straightforward. (right-section binary-proc arg2) creates a new procedure by filling in the second argument of a binary procedure. For example, we might define a procedure that subtracts 3 from a value with > (define sub3 (right-section - 3)) (make-filter pred?) creates a new filter that uses pred? to determine whether or not to keep elements. Note that make-filter is very similar to remove except that remove takes two parameters (the predicate and the list) and returns a list, while make-filter takes one parameter (the predicate) and returns a function whose purpose is to read a list and remove elements that match the predicate. (conjunction pred1? pred2? ... predn?) create a news predicate that holds only if all of pred1?, pred2?, through predn? hold (the predicates should be tested in order). We can use conjunction to build a better version of even. (define better-even? (conjunction number? even?)) (disjunction pred1? pred2? ... predn?) creates a new predicate that holds if pred1? holds or pred2? holds or ... or predn? hods. The predicates should be tested in order. (complement pred?) creates a new predicate whose result is the opposite of the result of pred?. This procedure can be defined as (define complement (lambda (pred?) ; Result procedure (lambda (val) (not (pred? val)))))