Exercises
Higher-order Functions

Define and play with the functions flip, negate, and compose, as they are defined on this page .

Define, for instance, a flipped cons function and a flipped minus function.

Define the function odd? in terms of even? and negate.

Finally, compose two HTML mirror functions, such as b and em, to a new function.

Be sure you understand your results.

Lists in Scheme are linear linked structures, which makes it necessary to apply linear search techniques.

Strings are also linear structures, but based on arrays instead of lists. Thus, strings can be linearly searched, but it is also possible to access strings randomly, and more efficiently.

First, design a function which searches a string linearly, in the same way as find-in-list. Will you just replicate the parameters from find-in-list, or will you prefer something different?

Next program your function in Scheme.

It is sometimes useful to know where in a list a certain element occurs, if it occurs at all. Program the function index-in-list-by-predicate which searches for a given element. The comparion between the given element and the elements in the list is controlled by a comparison parameter to index-in-list-by-predicate. The function should return the list position of the match (first element is number 0), or #f if no match is found.

Some examples will help us understand the function:

   (index-in-list-by-predicate '(a b c c b a) 'c eq?) => 2

   (index-in-list-by-predicate '(a b c c b a) 'x eq?) => #f

   (index-in-list-by-predicate '(two 2 "two") 2 
     (lambda (x y) (and (number? x) (number? y) (= x y)))) => 1
     

Be aware if your function is tail recursive.

Linear search, as illustrated by other exercises, is not efficient. It is often attractive to organize data in a sorted vector, and to do binary search in the vector.

This exercise is meant to illustrate a real-life higher-order function, generalized with several parameters that are functions themselves.

Program a function binary-search-in-vector, with the following signature:

  (binary-search-in-vector v el sel el-eq? el-leq?)

v is the sorted vector. el is the element to search for. If v-el is an element in the vector, the actual comparison is done between el and (sel v-el). Thus, the function sel is used as a selector on vector elements. Equality between elements is done by the el-eq? function. Thus, (el-eq? (sel x) (sel y)) makes sense on elements x and y in the vector. The ordering of elements in the vector is defined by the el-leq? function. (el-leq? (sel x) (sel y)) makes sense on elements x and y in the vector.

The call (binary-search-in-vector v el sel el-eq? el-leq?) searches the vector via binary search and it returns an element el-v from the vector which satisfies (el-eq? (sel el-v) el). If no such element can be located, it returns #f.

Here are some examples, with elements being cons pairs:

  (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 7 car = <=)    =>
  (7 . i)

  (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 2 car = <=)    =>
  (2 . x)

  (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 10 car = <=)   =>
  #f

Be sure to program a tail recursive solution.

In contrast to the function mymap on this page , write an iterative mapping function which is tail recursive.

Test your function against mymap on this page, and against the native map function of your Scheme system.

In an earlier section we have shown the application of some very useful table manipulation functions. Now it is time to program these functions, and to study them in further details.

Program the functions transpose, eliminate-row, and eliminate-column, as they have been illustrated earlier. As one of the success criteria of this exercise, you should attempt to use higher-order functions as much and well as possible in your solutions.

Hint: Program a higher-order function, (eliminate-element n). The function should return a function which eliminates element number n from a list.

The filter function illustrated in the material is memory efficient, using tail recursion.

Take a moment here to implement the straightforward recursive filtering function, which isn't tail recursive.

The mathematical quantifiers for all and there exists are well-known. In this exercise we will write similar Scheme quantifier functions.

The function (for-all lst p) is supposed to check if all elements in the list lst satisfy the predicate p.

The function (there-exists lst p) is supposed to check if one or more elements in the list lst satisfy the predicate p.

Finally, the function (there-exists-1 lst p) is supposed to check if exactly on element in the list lst satisfies p.

Program and test these functions.

You should in addition consider how to program these function by use of map, filter, and reduction (accumulation).

Please decide if your functions are tail recursive.

Try out the functions curry2 and curry3 on a number of different functions.

You can, for instance, use then curry functions on plus (+) and map.

Demonstrate, by a practical example, that the uncurry functions and the curry functions are inverse to each other.