[r6rs-discuss] Re: Plausible list problems

[AndrevanTonder]

On Tue, 3 Oct 2006, William D Clinger wrote:

> Although it is undecidable whether a list is
> plausible, the draft R6RS requirement can be
> implemented because it *requires* an exception
> to be raised if list is not a plausible list,
> while *allowing* an exception to be raised even
> if list is a plausible list.

Does this requirement that an exception be raised
disqualify the following implementation of map:

(define (map-circ f clist)
   (define (map-0 hare tortoise)
     (if (null? hare)
         '()
         (cons (f (car hare))
               (map-1 (cdr hare) tortoise))))
   (define (map-1 hare tortoise)
     (if (eq? hare tortoise)
         (error "Circular list"))
     (if (null? hare)
         '()
         (cons (f (car hare))
               (map-0 (cdr hare) (cdr tortoise)))))
   (map-0 clist clist))

Since this does not check the arguments up front, it
will not terminate in the following example, apparently
violating the requirement that an exception be raised:

(let* ((ones (list 1))
        (pointer ones))
   (set-cdr! pointer (cons 1 ones))
   (set! pointer (cdr pointer))
   (map-circ (lambda (x)
               (set-cdr! pointer (cons 1 (cdr pointer)))
               (set! pointer (cdr pointer))
               x)
             ones))

Here ones is never a plausible list during the map-circ
call (it is an ever-growing circular list).

Cheers
Andre