Higherorder Functions 
Higherorder functions is another key area in the functional programming paradigm; Perhaps the most important at all. In this chapter we will explore this exiting area, and we will give a number of webrelated examples.
14.1 Higherorder functions  14.3 Linear search in lists 
14.2 Some simple and general higherorder functions  14.4 Generation of list selectors 
14.1. Higherorder functions
Contents Up Previous Next Slide Subject index Program index Exercise index
Let us first define the concepts of higherorder functions and higherorder languages.

When some functions are 'higherorder' others are bound to be 'lowerorder'. What, exactly, do we mean by the 'order of functions'. This is explained in below.

With this understanding, we can define higherorder functions more precisely.
Functions of order i, i >= 2, are called higherorder functions 
14.2. Some simple and general higherorder functions
Contents Up Previous Next Slide Subject index Program index Exercise index
The flip function is given in two versions below. flip takes a function as input, which is returned with reversed parameters, cf. Program 14.1.
The first version of flip uses the shallow syntactic form, discussed in Section 8.12. The one in Program 14.2 uses the raw lambda expression, also at the outer level.
1 2 3  (define (flip f) (lambda (x y) (f y x)))  

The read expression in Program 14.1 and Program 14.2 are the values returned from the function flip.
1 2 3 4 5 6 7 8 9  (define flip (lambda (f) (lambda (x y) (f y x)))) (define (flip f) (lambda (x y) (f y x)))  

The function negate, as shown in Program 14.3, takes a predicate p as parameter. negate returns the negated predicate. Thus, if (p x) is true, then ((negate p) x) is false.
1 2 3  (define (negate p) (lambda (x) (if (p x) #f #t)))  

The function compose in Program 14.4 is the classical function composition operator, known by all high school students as 'f o g'
1 2 3  (define (compose f g) (lambda (x) (f (g x))))  

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.
Solution
14.3. Linear search in lists
Contents Up Previous Next Slide Subject index Program index Exercise index
Let us program a simple, but useful higherorder function which searches a list by linear search. The function findinlist, shown in Program 14.5 takes a predicate pred and a list lst as parameters. This predicate is applied on the elements in the list. The first element which satisfy the predicate is returned.
Search criterias can be passed as predicates to linear search functions 
1 2 3 4 5 6 7  ;; A simple linear list search function. ;; Return the first element which satisfies the predicate pred. ;; If no such element is found, return #f. (define (findinlist pred lst) (cond ((null? lst) #f) ((pred (car lst)) (car lst)) (else (findinlist pred (cdr lst)))))  

The dialogue below shows examples of linear list search with findinlist.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  1> (define haircolors (pairup '(ib per ann) '("black" "green" "pink"))) 2> haircolors ((ib . "black") (per . "green") (ann . "pink")) 3> (findinlist (lambda (ass) (eq? (car ass) 'per)) haircolors) (per . "green") 4> (findinlist (lambda (ass) (equal? (cdr ass) "pink")) haircolors) (ann . "pink") 5> (findinlist (lambda (ass) (equal? (cdr ass) "yellow")) haircolors) #f 6> (let ((pinkperson (findinlist (lambda (ass) (equal? (cdr ass) "pink")) haircolors))) (if pinkperson (car pinkperson) #f)) ann  

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 findinlist. Will you just replicate the parameters from findinlist, or will you prefer something different?
Next program your function in Scheme.
SolutionIt is sometimes useful to know where in a list a certain element occurs, if it occurs at all. Program the function indexinlistbypredicate 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 indexinlistbypredicate. 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:
(indexinlistbypredicate '(a b c c b a) 'c eq?) => 2 (indexinlistbypredicate '(a b c c b a) 'x eq?) => #f (indexinlistbypredicate '(two 2 "two") 2 (lambda (x y) (and (number? x) (number? y) (= x y)))) => 1
Be aware if your function is tail recursive.
SolutionLinear 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 reallife higherorder function, generalized with several parameters that are functions themselves.
Program a function binarysearchinvector, with the following signature:
(binarysearchinvector v el sel eleq? elleq?)
v is the sorted vector. el is the element to search for. If vel is an element in the vector, the actual comparison is done between el and (sel vel). Thus, the function sel is used as a selector on vector elements. Equality between elements is done by the eleq? function. Thus, (eleq? (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 elleq? function. (elleq? (sel x) (sel y)) makes sense on elements x and y in the vector.
The call (binarysearchinvector v el sel eleq? elleq?) searches the vector via binary search and it returns an element elv from the vector which satisfies (eleq? (sel elv) el). If no such element can be located, it returns #f.
Here are some examples, with elements being cons pairs:
(binarysearchinvector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 7 car = <=) => (7 . i) (binarysearchinvector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 2 car = <=) => (2 . x) (binarysearchinvector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 10 car = <=) => #f
Be sure to program a tail recursive solution.
There is no solution to this exercise
14.4. Generation of list selectors
Contents Up Previous Next Slide Subject index Program index Exercise index
The function findinlist took a function as parameter. In this section we will give an example of a higherorder function which returns a function as result.
It is attractive to generate generalizations of the list selector functions car, cadr, etc 
The function makeselectorfunction generates a list selector function which returns element number n from a list. It should be noticed that the first element in a list is counted as number one. This is contrary to the convention of the function listref and other similar Scheme function, which counts the first element in a list as number zero. This explains the ( n 1) expression in Program 14.7.
1 2  (define (makeselectorfunction n) (lambda (lst) (listref lst ( n 1))))  

In the web version of the material (slide view or annotated slide view) you will find yet another version of the function makeselectorfunction, which provides for better error messages, in case element number n does not exist in the list. We have taken it out of this version because of its size and format.
The dialogue below shows examples of definitions and uses of list selector functions generated by makeselectorfunction.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  1> (define first (makeselectorfunction 1 "first")) 2> (first '(a b c)) a 3> (first '()) The selector function first: The list () is is too short for selection. It must have at least 1 elements. > 4> (define (makepersonrecord firstname lastname department) (list 'personrecord firstname lastname department)) 5> (define personrecord (makepersonrecord "Kurt" "Normark" "Computer Science")) 6> (define firstnameof (makeselectorfunction 2 "firstnameof")) 7> (define lastnameof (makeselectorfunction 3 "lastnameof")) 8> (lastnameof personrecord) "Normark" 9> (firstnameof personrecord) "Kurt"  
