[r6rs-discuss] [Formal] Map returning twice

From: Abdulaziz Ghuloum <aghuloum>
Date: Thu Mar 15 05:40:22 2007

On Mar 13, 2007, at 3:36 PM, AndrevanTonder wrote:

> For this to work correctly, MAP should allocate new list structure
> not only the first time, but /every subsequent/ time it returns.

I'm not sure I understand this requirement (or maybe I'm sure I don't
understand it :-))

Suppose I implement map1 (restricted to one list and does no error
checking for simplification) as the standard textbook implementation:

(define (map1 f ls)
   (if (null? ls)
       '()
       (cons (f (car ls)) (map1 f (cdr ls)))))

This implementation, depending on the order of evaluation, and
depending on which invocation of f captures a continuation, may
return a fresh list every time, or may return a partially-fresh and
partially-recycled list sometimes. From reading the sentence above,
it seems that you're suggesting that this is incorrect, and instead,
map1 should be implemented as:

(define (map1 f ls)
   (define (map1 f ls)
     (if (null? ls)
         '()
         (cons (f (car ls)) (map1 f (cdr ls)))))
   (map1 (lambda (x) x)
         (map1 f ls)))

to keep the order of invocations of f unspecified but at the expense
of copying the list (needlessly most of the time), or as:

(define (map1 f ls)
   (if (null? ls)
       '()
       (let ([t (f (car ls))])
         (cons t (map1 f (cdr ls))))))

which fixes the calls to f in a left-to-right order and thus ensures
that all the conses of the resulting list are created only after all
calls to f return.

If your comment is not going as far as this, maybe it should just say
"map should not destructively update the list it returns" instead.

Aziz,,,
Received on Thu Mar 15 2007 - 05:40:07 UTC