CS5001 Lab7: Higher-order functions and generalizations.

1. Higher-Order functions

A higher-order function is a name given to any function that does at least one of the following

One or more of its arguments is a function.
Returns a function as a result.

Here are the signatures of some of the higher-order functions provided by DrRacket.

;;;; Signature
;; map : [X -> Y] List<X> -> List<Y>
;;;; Purpose
;; GIVEN: a function and a list
;; RETURNS: a list that holds the results of applying the function
;;          to each element of the input list.

;;;; Signature
;; andmap: [X -> Boolean] List<X> -> Boolean
;;;; Purpose
;; GIVEN: a predicate from some kind of data X to a boolean and
;;        a list of X
;; RETURNS: the result of logically and-ing all results from applying
;;          the function to each list element.



;;;; Signature
;; ormap: [X -> Boolean] List<X> -> Boolean
;;;; Purpose
;; GIVEN: a predicate from some kind of data X to a boolean and
;;        a list of X
;; RETURNS: the result of logically or-ing all results from applying
;;          the function to each list element.

;;;; Signature
;; foldr: [X Y -> Y] Y List<X> -> Y
;;;; Purpose
;; GIVEN: a function, a value for empty and a list of elements
;; RETURNS: the result or applying the cumulative result of applying f
;;          the list elements from the last to the first

;;;; Signature
;; foldl: [X Y -> Y] Y List<X> -> Y
;;;; Purpose
;; GIVEN: a function, a value for empty and a list of elements
;; RETURNS: the result or applying the cumulative result of applying f
;;          the list elements from the last to the first

;;;; Signature
;; filter: [X -> Boolean] LoF<X> -> LoF<X>
;;;; Purpose
;; GIVEN: a predicate function and a list of items
;; RETURNS: all elements of the list for which the function returns #true

Practise Exercises

For each of the following functions provide

a purpose statement
tests

1)
```
(define (f1 lst)
 (filter number? lst))
```
2)
```
(define (f2 lst)
 (ormap number? lst))
```
3)
```
(define (f3 lst)
 (andmap number? lst))
```
4)
```
(define (f4 lst)
 (foldl + 0 (f1 lst)))
```

(define (f5 lst)
 (foldl + 0 (map add1 (f1 lst))))

2. Concrete Signatures for Higher-Order Functions

When we use a one of the predefined higher-order functions we are providing concrete data definitions (i.e., non-abstract). For example

> (map add1 (list 1 2 3 4))
(list 2 3 4 5)

we are using map with the following concrete signature

> (map add1 (list 1 2 3 4))  ;; [Number -> Number] List<Number> -> List<Number>
(list 2 3 4 5)

Practice Exercises

6) Provide the concrete signatures for each use of a higher-order function used in the following code

> (map number->string (list 1 2 3 4))
(list "1" "2" "3" "4")

> (foldr + 0 (list 1 2 3 4))
10

> (foldl + 0 (list 1 2 3 4))
10

> (map string-length
       (map number->string (list 12 234 12 3456 89765)))
(list 2 3 2 4 5)

> (andmap even?
          (map string-length
               (map number->string (list 12 234 12 3456 89765))))
#false

;; add1-append: Number LoF<Number> -> LoF<Number>
;; Given a number, n, and a list of numbers add 1 to n and
;; add the result to the list
(define (add1-append n lst)
  (cons (add1 n) lst))

> (foldl add1-append empty (list 1 2 3 4))
(list 5 4 3 2)

>  (foldr add1-append empty (list 1 2 3 4))
(list 2 3 4 5)

3. Lists of Lists

One of your friends is finding it difficult to work with lists of lists and higher-order functions (HOF). His TA gave him same extra simple questions to help them practise and your friend is sharing these questions with you.

Practice Exercises

7) Given a Lof<Lof<Numbers>> use HOF to add 1 to each number.
8) Given a Lof<Lof<Numbers>> and a number n use HOF to multiply each number by n.
9) Given a Lof<Lof<Numbers>> use HOF to get the sum of all numbers.
10) Given a Lof<Lof<Numbers>> use HOF to get the product of all numbers.
11) Given a Lof<Lof<Numbers>> use HOF to filter all even numbers.
12) Given a Lof<Lof<Numbers>> use HOF to filter all numbers greater than 10.
13) Given a Lof<Lof<Numbers>> use HOF to filter all numbers greater than 10 and less than 50.
14) Given a Lof<Lof<String>> use HOF to filter all strings that have length less than 5.

4. Managing a class of students

One of the professors in the department is asking for your help in developing programs to help them manage their class.

The would like to keep a list of all students in their class. For each student we would like to capture

the student’s name
the student’s id
a list of all the students homework grades

Practise Exercises

Design a data definition that will allow the professor to keep a list of all his students and their grades
Using your new data definition, design a program that given the list of students returns a list of each students average grade
Design a new program that given the list of students and the passing grade returns the list of students whose average is above the passing grade
Design a new program that given the list of students and the passing grade returns the list of students whose average is below the passing grade
Design a new program that given the list of students and a bonus points returns the list of students with each student’s homework increases by the bonus points
Design a new program that given the list of students and adjustment points returns the list of students with each student’s homework decreases by the bonus points

HINT: These programs lend themselves to the use of higher-order functions. You might find it easier at first to complete your design without higher order functions and then come back and refactor your code to use higher-order functions.