Iterative map in scheme

Question

I am watching SICP video lectures and i came to a section where tutors are showing procedures to work with lists, so, here is one of them:

(define (map p l)
   (if (null? l) 
       (list)
       (cons (p (car l))
                    (map p (cdr l)))))

What i want to ask is: is there a way to define map in iterative way, or that cons requires lazy evaluation to be executed right?

Answer 1

You original code is almost tail recursive.. the only thing that makes it not is the cons part. If Scheme had equal requirement for having TRMC optimization as it has TCO requirement you could leave your code as is and the implementation would have made it tail recursive for you.

Since it isn't a requirement we need to do our own TRMC optimization. Usually when iterating a list in a loop and having it tail recursive by using an accumulator you get the result in the opposite order, thus you can do linear update reverse:

(define (map proc lst)
  (let loop ((lst lst) (acc '()))
    (cond ((null? lst) (reverse! acc) acc)
          (else (loop (cdr lst) 
                      (cons (proc (car lst)) acc))))))

Or you can do it all in one pass:

(define (map proc lst)
  (define head (list 1))
  (let loop ((tail head) (lst lst))
    (cond ((null? lst) (cdr head))
          (else (set-cdr! tail (list (proc (car lst))))
                (loop (cdr tail) (cdr lst))))))

Now in both cases you mutate only the structure the procedure has itself created, thus for the user it might as well be implemented in the same manner as your example.

When you use higher order procedures like map from your implementation it could happen it has been implemented like this. It's easy to find out by comparing performance on the supplied map with the different implementations with a very long list. The difference between the executions would tell you if it's TRMCO or how the supplied map probably has been implemented.

Answer 2

You need to embrace recursion in order to appreciate SICP and Scheme in general, so try to get used to it, you will appreciate it later, promised.

But yes, you can:

(define (iterative-map f lst)
  (define res null)
  (do ((i (- (length lst) 1) (- i 1))) ((= i -1))
    (set! res (cons (f (list-ref lst i)) res)))
  res)

(iterative-map (lambda (x) (+ x 1)) '(1 3 5))
=> '(2 4 6)

but using set! is considered bad style if avoidable.

In Racket you have a different set of loops that are more elegant:

(define (for-map f lst)
  (for/list ((i lst))
    (f i)))

(for-map add1 '(1 3 5))
=> '(2 4 6)