scheme, sicp, solution 3.19, procedure with infinite loop works in case it provided as argument

Question

有人可以帮助我澄清练习 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)

这看起来很神奇。如果有任何帮助，我将不胜感激。

Answer 1

mystery 通过重复删除每个条目的 cdr 并将其替换为前一个 x 的 cdr 来反转数组 "in-place"。

如果此列表没有循环，那么当您回到原来的 '() 时，它最终会反转。如果是一个循环，您将得到原始数组的指针。

这绝对是一个很难理解的问题。如果你画了一个方框指针图肯定会有帮助，你只需要画3张图。

自动生成列表图表

在 doing SICP myself 的过程中，我发现自己想要一种可视化列表突变的方法（并跳过无数的 "draw a list diagram of..." 练习）。我为此编写了一个小函数，我想如果我分享它，您可能会觉得有用。

这些图表是每次 loop（在 mystery 函数内）为运行时运行在 x 上的一个示例。

下面的代码是我用来生成这些图表的。我作为一个 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 (Graphviz) 处理以呈现为图形格式。

例如，您可以运行上面的代码并将其通过管道传输到 dot:

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

此命令生成一个 postscript 文件，如果您运行 list->graphviz 不止一次，该文件的优点是可以将每个列表分隔到它自己的页面中。 dot 还可以将 PNG、PDF 和许多其他文件格式输出为 manpage describes。

scheme, sicp, solution 3.19, procedure with infinite loop works in case it provided as argument

scheme, sicp, solution 3.19, procedure with infinite loop works in case it is provided as argument

lisp

scheme

sicp

自动生成列表图表