Higher-order Functions

**4.1 Using flip, negate, and compose ***

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.

**4.2 Linear string search ****

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.

**4.3 Index in list ****

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.

**4.4 Binary search in sorted vectors *****

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.

**4.5 Iterative mapping function ****

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.

**4.6 Table exercise: transposing, row elimination, and column elimination. ****

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.

**4.7 A straightforward filter function ****

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.

**4.8 Quantifier Functions ****

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.

**4.9 Playing with curried functions in Scheme ***

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.

Generated: Tuesday July 2, 2013, 09:15:30