CS5001 Lab6: Higher-order functions and generalizations.

1. Higher-order functions

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

;; map : [X -> Y] List<X> -> List<Y>
;; andmap: [X -> Boolean] List<X> -> Boolean
;; ormap: [X -> Boolean] List<X> -> Boolean
;; foldr: [X Y -> Y] Y List<X> -> Y
;; foldl: [X Y -> Y] Y List<X> -> Y

When we use a one of this functions 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

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 List<Number> -> List<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)

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

3. Generic Binary Trees

A friend is working on an assignment that asks them to generalize over binary trees. They already have examples of binary tree data definitions

;; An SBT is one of
;; - empty
;; - (make-snode String SBT SBT)

(define-struct snode (val left right))

;; An IBT is one of
;; - empty
;; - (make-snode Integer IBT IBT)

(define-struct inode (val left right))

Your friend is having problems generalizing over these data definitions.

Practice Exercises

Create a generalized data definition for binary tries.

Now your friend is asked to generalize over functions of SBT and IBT.

Practice Exercises

Design the function ibt-sum that takes an IBT and adds all the number values in the IBT
Design the function sbt-append that takes an SBT and appends all the strings in the SBT into one big string.
Design a generic function bt-op that generalizes over operations on binary trees.
Use your bt-op to create new implementations, e.g., ibt-sum2 and sbt-append2 that use bt-op.