sicp-3-3-1

Posted on 2015-02-26 20:23:25 +0900 in SICP Lisp

3.16

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

(define z3 '(a b c))
(count-pairs z3)

(define z1 '(c))
(define z4
  (list z1 z1))

(define z23
  (cons z1 z1))
(define z7
  (cons z23 z23))


(define zi '(a b c))
(set-cdr! (cddr zi) zi)
(count-pairs zi)

The construct of zi is hard for me. It could be built with the lazy evaluation as well.

3.17

(eq? x y) tests whether x and y are the same object (that is, whether x and y are equal as pointers)

Understanding the pointer is the key to understand sameness and sharing.

(define (count-pairs x)
  (let ((aux '()))
    (define (uncounted? x)
      (if (memq x aux)
        0
        (begin
          (set! aux (cons x aux))
          1)))
    (define (count x)
      (if (not (pair? x))
        0
        (+
          (count (car x))
          (count (cdr x))
          (uncounted? x))))
    (count x)))

3.18

(define (cycle? l)
  (define (detect pair countedList)
    (cond ((not (pair? pair)) #f)
          ((memq pair countedList) #t)
          (else
            (detect (cdr pair) (cons pair countedList)))))
  (detect l '()))

3.19

(define (has_cycle? l)
  (define (iter l r)
    (cond ((eq? l r) #t)
          ((not (pair? r)) #f)
          ((not (pair? (cdr r))) #f)
          (else (iter (cdr l) (cdr (cdr r))))))
  (cond ((not (pair? l)) #f)
        ((not (pair? (cdr l))) #f)
        (else (iter (cdr l) (cdr (cdr l))))))

It is a frequently asked question in a interview. Special attention should be paied to the corner cases.

----------------------------------- 本文内容遵从CC版权协议转载请注明出自kamelzcs -----------------------------------
«  | sicp-3-2 »

Hide Comments

comments powered by Disqus