Finger Exercises with Abstract List Functions

Scheme provides a number of abstract functions for processing lists. Figure  collects the specification of the most important ones. Using these functions greatly simplifies many programming tasks and helps readers understand programs quickly. The following exercises provide an opportunity to get acquainted with these functions.

;; build-list : N (N -> X) -> (listof X) ;; to construct (list (f 0) ... (f (- n 1))) (define (build-list n f) ...) ;; filter : (X -> boolean) (listof X) -> (listof X) ;; to construct a list from all those items on alox for which p holds (define (filter p alox) ...) ;; quick-sort : (X X -> boolean) (listof X) -> (listof X) ;; to construct a list from all items on alox in an order according to cmp (define (quick-sort cmp alox) ...) ;; map : (X -> Y) (listof X) -> (listof Y) ;; to construct a list by applying f to each item on alox ;; that is, (map f (list x-1 ... x-n)) = (list (f x-1) ... (f x-n)) (define (map f alox) ...) ;; andmap : (X -> boolean) (listof X) -> boolean ;; to determine whether p holds for every item on alox ;; that is, (andmap p (list x-1 ... x-n)) = (and (p x-1) (and ... (p x-n))) (define (andmap p alox) ...) ;; ormap : (X -> boolean) (listof X) -> boolean ;; to determine whether p holds for at least one item on alox ;; that is, (ormap p (list x-1 ... x-n)) = (or (p x-1) (or ... (p x-n))) (define (ormap p alox) ...) ;; foldr : (X Y -> Y) Y (listof X) -> Y ;; (foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base)) (define (foldr f base alox) ...) ;; foldl : (X Y -> Y) Y (listof X) -> Y ;; (foldl f base (list x-1 ... x-n)) = (f x-n ... (f x-1 base)) (define (foldl f base alox) ...) ;; assf : (X -> boolean) (listof (list X Y)) -> (list X Y) or false ;; to find the first item on alop for whose first item p? holds (define (assf p? alop) ...) Figure: Scheme's built-in abstract functions for list-processing

Exercise 21.2.1

Use build-list

1. to create the lists (list 0 ... 3) and (list 1 ... 4);
2. to create the list (list .1 .01 .001 .0001);
3. to define evens, which consumes a natural number n and creates the list of the first n even numbers;
4. to define tabulate from exercise ; and
5. to define diagonal, which consumes a natural number n and creates a list of lists of 0 and 1.
   

   Example:

   (equal? (diagonal 3)
           (list 
             (list 1 0 0) 
             (list 0 1 0) 
             (list 0 0 1))) 
   

Exercise 21.2.2

Use map to define the following functions:

1. convert-euro, which converts a list of U.S. dollar amounts into a list of euro amounts based on an exchange rate of 1.22 euro for each dollar;
2. convertFC, which converts a list of Fahrenheit measurements to a list of Celsius measurements;
3. move-all, which consumes a list of posn structures and translates each by adding 3 to the x-component. Solution

Exercise 21.2.3

Here is the version of filter that DrScheme provides:

 
;; filter : (X -> boolean) (listof X) -> (listof X) 
;; to construct a list of X from all those items on alon 
;; for which predicate? holds  
(define (filter predicate? alon) 
  (cond 
    [(empty? alon) empty] 
    [else (cond 
            [(predicate? (first alon)) 
             (cons (first alon) (filter predicate? (rest alon)))] 
            [else (filter predicate? (rest alon))])])) 

Use filter to define the following functions:

1. eliminate-exp, which consumes a number, ua, and a list of toy structures (containing name and price) and produces a list of all those descriptions whose price is below ua;
2. recall, which consumes the name of a toy, called ty, and a list of names, called lon, and produces a list of names that contains all components of lon with the exception of ty;
3. selection, which consumes two lists of names and selects all those from the second one that are also on the first. Solution