Sunday, June 13, 2010

modification of Ex 3.19 of SICP - use constant amount of space to determine if a list contains loop

There was a flaw in my last post and modified it as below.
前回のアルゴリズムに欠陥があり、修正した。
上次的算法有问题,修改后可以保证只是用固定的存储空间

(define (loop? x)
  (define (iter y mk)
    (if (null? y) #f
      (if (eq? (car y) mk) #t
 (iter (cdr y) mk))))
  (if (null? x) #f
    (let ((mark (car x)))
      (iter (cdr x) mark))))
gosh> loop?
gosh>  (define s '( 1 2 3))
s
gosh>  (set-cdr! (cddr s) s)
#
gosh> 
(loop? s)
#t
gosh> (loop? '(1 2 3))
#f

No comments:

Post a Comment