Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'Higher-order Functions
14.  Introduction to 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 functions14.3 Linear search in lists
14.2 Some simple and general higher-order functions14.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.

A higher-order function accepts functions as arguments and is able to return a function as its result

A higher-order language supports higher-order functions and allows functions to be constituents of data structures

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.

  • The order of data

    • Order 0: Non function data

    • Order 1: Functions with domain and range of order 0

    • Order 2: Functions with domain and range of order 1

    • Order k: Functions with domain and range of order k-1

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)))
Program 14.1    The function flip changes the order of it's parameters.

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)))
Program 14.2    An alternative formulation of flip without use of the sugared define syntax.

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)))
Program 14.3    The function negate negates a predicate.

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))))
Program 14.4    The function compose composes two functions which both are assumed to take a single argument.


Exercise 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.

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)))))
Program 14.5    A linear list search function.

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
Program 14.6    A sample interaction using find-in-list.


Exercise 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.

Solution


Exercise 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.

Solution


Exercise 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.

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))))
Program 14.7    A simple version of the make-selector-function function.

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"
Program 14.8    Example usages of the function make-selector-function.

Generated: Tuesday July 2, 2013, 09:15:34
Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'