3.4 Lisp and Higher-Order Functions

Lisp functions compose, mapcar, and maplist are defined as follows, with #t written for true and () for the empty list. Text begining with ;; and continuing to the end of a line is a comment.

(define compose (lambda (f g) (labmda (x) (f (g x))))) (define mapcar (lambda (f xs) (cond (eq? xs ()) ()) ;; If the list is empty, return the empty list (#t ;; Otherwise, apply f to the first element... (cons (f (car xs)) ;; and map f on the rest of the list (mapcar f (cdr xs)) )))) (define maplist (lambda (f xs) (cond ((eq? xs ()) ());; If the list is empy, return the empty list (#t ;; Otherwise, apply f to the list... (cons (f xs) ;; and map f on the rest of the list (maplist f (cdr xs)) ))))) 

The Differences between maplist and mapcar is that maplist applies f to every sublist, whereas mapcar applies f to every element. (The two function expressions differ in only the sixth line.)

For example, if inc is a function that adds one to any number, then

(mapchar inc '(1 2 3 4)) = (2 3 4 5) 

where as

(maplist (lambda (xs) (mapcar inc xs)) '(1 2 3 4)) = ((2 3 4 5) (3 4 5) (4 5) (5)) 

However, you can almost get mapcar from maplist by composing with the car function.

In particular, note that

(mapcar f '(1 2 3 4)) = (f (car (1 2 3 4))) (f (car (2 3 4))) (f (car (3 4))) (f (car (4))) 

Write a version of compose

for any function f and list xs.

((compose2 maplist car) f xs) = (mapcar f xs) 

(a) Fill in the missing code in the following definition. The correct answer is short and fits here easily. You may also want to answer parts (b) and (c) first.

(define compose2 (lambda (g h) (lambda (f xs) (g (lambda (xs) ( _______ )) xs) ))) 

(b) When (compose2 maplist car) is evaluated, the result is a function defined by (lambda (f xs)(g ...)) above, with

• which function replacing g?
• and which function replacing h?

(c) We could also write the subexpression (labmda (xs) (...)) as (compose (...) (...)) for two functions. Which two functions are these?