Exercises in this lecture   Go to the notes, in which this exercise belongs -- Keyboard shortcut: 'u'   Alphabetic index   Course home   

Exercise solution:
Iterative mapping function


Here is my attempt to define an iterative mapping function:

(define (mymap-iter f lst)
  (mymap-help-iter f lst '()))

(define (mymap-help-iter f lst result)
  (cond ((null? lst) (reverse result)) 
        (else (mymap-help-iter f (cdr lst) (cons (f (car lst)) result)))))

Please notice the reversing of the result in the case where lst becomes empty. It is not efficient to operate on the rear end of a list. Therefore we insert (f (car lst)) in the front of the list, and 'turn the list around' (reverses it) once and for all as the last thing before finally returning the result.

An iteratively programmed function is characterized by having all its 'state' in the parameter list. The relevant 'state' for the iterative mapping task is the original list (which gradually becomes shorter) and the new list of f applications (which gradually gets longer).

Talking about state that changes over time does not fit with well with functional programming. However, recall from an earlier lecture, that a chain of tail recursive calls in principle creates new 'state variables' for each new call. In reality, however, the state (parameters) are updated imperatively, as a memory optimization. This does not compromise the functional nature of the program.