Exercises and solutions
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.

1. ((flip -) 5 6)   =>   1
2. ((flip cons) 'a 'b)   =>   (b . a)
3. (let ((non-string? (negate string?))) (non-string? 5))   =>   #t
4. ((compose b em) "bold emphasize text")   =>   "<b><em>bold emphasize text</em></b>"

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 not obvious to replicate the parameter profile from find-in-list. The reason is that the element type of strings is always char. Thus, a predicate will typically (but not necessarily) check for equality relative to a given, fixed character. In that case find-in-string from lib/general.scm is a reasonable solution. Here it is:

;; Search linearly for the character ch in the string str. 
;; An optional start postion start-post tells at which position to start the search (default is position 0).
;; Return the index of the first occurence of ch, or #f if it does not exist in str.
;; The index of the first character in a string is 0.
(define (find-in-string str ch . start-pos)
 (let ((start-pos-1 (if (null? start-pos) 0 (car start-pos))))
  (find-in-string-1 str ch start-pos-1 (string-length str))))

(define (find-in-string-1 str ch i lgt)
  (cond ((>= i lgt) #f)
        ((eqv? ch (string-ref str i)) i)
        (else (find-in-string-1 str ch (+ i 1) lgt))))  

Please be aware if you make a tail recursive function or not.

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.

;; Return the index of the first occurrence of el in lst. 
;; Return #f is el is not found in lst.
;; Comparison is done by comparator.
;; The index of the first element is 0.
(define (index-in-list-by-predicate lst el comparator)
  (index-in-list-by-predicate-1 lst el comparator 0))

(define (index-in-list-by-predicate-1 lst el comparator i)
  (cond ((null? lst) #f)
        ((comparator el (car lst)) i)
        (else (index-in-list-by-predicate-1 (cdr lst) el comparator (+ i 1)))))

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.

(define (mymap-iter f lst)
  (mymap-help-iter f lst '()))

(define (mymap-help-iter f lst result)
  (cond ((null? lst) (reverse result)) 
        (else (mymap-help-iter f (cdr lst) (cons (f (car lst)) result)))))

Please notice the reversing of the result in the case where lst becomes empty. It is not efficient to operate on the rear end of a list. Therefore we insert (f (car lst)) in the front of the list, and 'turn the list around' (reverses it) once and for all as the last thing before finally returning the result.

An iteratively programmed function is characterized by having all its 'state' in the parameter list. The relevant 'state' for the iterative mapping task is the original list (which gradually becomes shorter) and the new list of f applications (which gradually gets longer).

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.

(define (filter pred lst)
  (cond ((null? lst) '())
        ((pred (car lst)) 
           (cons (car lst) (filter pred (cdr lst))))
        (else (filter pred (cdr lst)))))

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.

; Directly programmed functions. These function terminate
; if the predicate fail on an element (for-all) or if
; if the predicate holds on an element (there-exists)
; Notice that both functions are tail-recursive.

(define (for-all lst p)
  (cond ((null? lst) #t)
        ((p (car lst)) (for-all (cdr lst) p))
        (else #f)))

(define (there-exists lst p)
  (cond ((null? lst) #f)
        ((p (car lst)) #t)
        (else (there-exists (cdr lst) p))))

; It is most natural to program there-exists-1 by use of
; filter - see below.





; Versions of for-all and there-exists programmed with
; mapping and accumulation. These function will traverse the 
; whole list twice. This should be avoided, if possible.

(define (for-all lst p)
  (accumulate-right and-fn #t (map p lst)))

(define (there-exist lst p)
  (accumulate-right or-fn #f (map p lst)))

(define (there-exists-1 lst p)
  (= (length (filter p lst)) 1))

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.