| | Higher-order Functions |
Higher-order 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 web-related examples.
| 14.1 Higher-order functions | 14.3 Linear search in lists |
| 14.2 Some simple and general higher-order functions | 14.4 Generation of list selectors |
14.1. Higher-order functions
Contents Up Previous Next Slide Subject index Program index Exercise index
Let us first define the concepts of higher-order functions and higher-order languages.
|
When some functions are 'higher-order' others are bound to be 'lower-order'. What, exactly, do we mean by the 'order of functions'. This is explained in below.
|
With this understanding, we can define higher-order functions more precisely.
Functions of order i, i >= 2, are called higher-order functions |
14.2. Some simple and general higher-order 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 higher-order function which searches a list by linear search. The function find-in-list, 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 (find-in-list pred lst)
(cond ((null? lst) #f)
((pred (car lst)) (car lst))
(else (find-in-list pred (cdr lst))))) | |||
|
The dialogue below shows examples of linear list search with find-in-list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 1> (define hair-colors
(pair-up '(ib per ann) '("black" "green" "pink")))
2> hair-colors
((ib . "black") (per . "green") (ann . "pink"))
3> (find-in-list (lambda (ass) (eq? (car ass) 'per)) hair-colors)
(per . "green")
4> (find-in-list (lambda (ass) (equal? (cdr ass) "pink"))
hair-colors)
(ann . "pink")
5> (find-in-list (lambda (ass) (equal? (cdr ass) "yellow"))
hair-colors)
#f
6> (let ((pink-person
(find-in-list
(lambda (ass) (equal? (cdr ass) "pink")) hair-colors)))
(if pink-person (car pink-person) #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 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.
SolutionIt 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.
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 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.
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 find-in-list took a function as parameter. In this section we will give an example of a higher-order function which returns a function as result.
It is attractive to generate generalizations of the list selector functions car, cadr, etc |
The function make-selector-function 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 list-ref 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 (make-selector-function n) (lambda (lst) (list-ref 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 make-selector-function, 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 make-selector-function.
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 (make-selector-function 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 (make-person-record firstname lastname department)
(list 'person-record firstname lastname department))
5> (define person-record
(make-person-record "Kurt" "Normark" "Computer Science"))
6> (define first-name-of
(make-selector-function 2 "first-name-of"))
7> (define last-name-of
(make-selector-function 3 "last-name-of"))
8> (last-name-of person-record)
"Normark"
9> (first-name-of person-record)
"Kurt" | |||
|
| Generated: Tuesday July 2, 2013, 09:15:34 | |