代码之家 › 专栏 › 技术社区 › Oliver

方案,sicp,解决方案3.19,无限循环过程在作为参数提供的情况下有效

sicp lisp scheme

0

Oliver · 技术社区 · 8 年前

有人能帮我澄清一下练习3.19中的一个可能的解决方案吗。程序的奥秘是案例列表循环中的无限循环作为参数给出。然而,当我们使用程序eq?为了检查列表是否包含循环,它可以工作并提供真实值。

(define (last-pair x)     
        (if (null? (cdr x))          
            x           
            (last-pair (cdr x))      
        ) 
)            
(define (make-cycle x)                
        (set-cdr! (last-pair x) x)                         
)                    
(define (mystery x)               
        (define (loop x y)                    
                (if (null? x)                
                    y                
                    (let ((temp (cdr x)))             
                          (set-cdr! x y)                     
                          (loop temp x)                  
                    )                
                )                   
        )                 
        (loop x '())              
)             
(define t (list 1 2 3))            
(define w (make-cycle t))                 
(eq? (mystery t) t)

1 回复 | 直到 8 年前

1

4

zetavolt 8 年前

mystery 通过反复剪掉 cdr 上一个的 x .

'() .如果有是一个循环,您将获得原始数组的指针。

自动生成列表图

正在进行中 doing SICP myself “绘制…的列表图” 练习)。我为此编写了一个小函数,我想如果我共享它,您可能会发现它很有用。

这些图是运行此功能的示例每次 loop 神秘的事物 函数)运行。

下面的代码是我用来生成这些图的代码。我作为Scheme新手编写了这段代码,但它的使用非常简单:函数( list->graphviz )接受参数 lst 哪一个是您想要的图表列表,以及可选参数 graph-name

(define* (list->graphviz lst #:optional graph-name)
  """Convert a list into a set of Graphviz instructions
       `lst' is the list you'd like a diagram of
       `graph-name` is an optional parameter indicating the name you'd like to give the graph."""

  (define number 0)
  (define result "")
  (define ordinals '())
  (define (result-append! str)
    (set! result (string-append result str)))

  (define* (nodename n #:optional cell)
    (format #f "cons~a~a" n (if cell (string-append ":" cell) "")))

  (define* (build-connector from to #:optional from-cell)
    (format #f "\t~a -> ~a;~%" (nodename from from-cell) (nodename to)))

  (define (build-shape elt)
    (define (build-label cell)
      (cond ((null? cell) "/");; "&#x2205;") ; null character
            ((pair? cell) "*");; "&#x2022;") ; bullet dot character
            (else (format #f "~a" cell))))
    (set! number (+ number 1))

    (format #f "\t~a [shape=record,label=\"<car> ~a | <cdr> ~a\"];~%"
            (nodename number)
            (build-label (car elt))
            (build-label (cdr elt))))

  (define* (search xs #:optional from-id from-cell)
    (let ((existing (assq xs ordinals)))
      (cond
       ;; if we're not dealing with a pair, don't bother making a shape
       ((not (pair? xs)) (result-append! "\tnothing [shape=polygon, label=\"not a pair\"]\n"))
       ((pair? existing)
        (result-append! (build-connector from-id (cdr existing) from-cell)))
       (else
        (begin
          (result-append! (build-shape xs))
          (set! ordinals (assq-set! ordinals xs number))
          (let ((parent-id number))
            ;; make a X->Y connector
            (if (number? from-id)
                (result-append! (build-connector from-id parent-id from-cell)))
            ;; recurse
            (if (pair? (car xs)) (search (car xs) parent-id "car"))
            (if (pair? (cdr xs)) (search (cdr xs) parent-id "cdr"))))))))

  (search lst)
  (string-append "digraph " graph-name " {\n" result "}\n"))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;; Here is where `mystery' begins ;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define t '(1 2 3))
(set-cdr! (cddr t) t)

(define (mystery x)
  (define (loop x y graph-num)
    (display (list->graphviz x (format #f "graph~a" graph-num)))
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x (+ 1 graph-num)))))
  (loop x '() 0))

(mystery t)

Graphviz 图形描述语句,然后必须由 dot

例如,您可以运行上面的代码并将其导入 点

$ scheme generate_box_ptr.scm  | dot -o ptrs.ps -Tps

此命令生成一个postscript文件,其优点是,如果已运行,则可以将每个列表分隔到其自己的页面中 列表->格拉夫维兹 不止一次。还可以输出PNG、PDF和许多其他文件格式作为 manpage describes .