以列表形式保存子列表

Question

我正在做一项家庭作业，遍历 DAG，寻找最短路线。在一些 SO 答案的帮助下，我已经准备好了很多东西。话虽这么说，但我无法获得 return 子列表列表的函数，就像我需要进一步处理数据一样。数据文件有一个形式为 (node1 node2 weight)

的子列表列表

(define (children? node)
  (define list '(1))
  (map (lambda (x)
         (cond
           ((equal? (car x) node)
           (if (equal? list '(1))
               (set-car! list x)
           (append! list x)))))
   data)
(if (equal? list '(1))
  #f
  list))

(define (append! lst . lsts)
  (if (not (null? lsts))
  (if (null? (cdr lst))
      (begin
        (set-cdr! lst (car lsts))
        (apply append! (car lsts) (cdr lsts)))
      (apply append! (cdr lst) lsts))))

当我运行 (children? 'b3) 时，我得到的结果如下所示：

((b3 b5 57) b3 b4 81 b3 b10 55 b3 b14 61 b3 b13 66)

什么时候应该看起来像

((b3 b5 57) (b3 b4 81) (b3 b10 55) (b3 b14 61) (b3 b13 66))

谁能稍微解释一下我的问题？

在此先感谢您的帮助。

Answer 1

修复缩进，您的代码变为

(define (children? node)
  (define list '(1))

使用头部哨兵技巧。不错嘛...）。但由于它的目的是通过手术改变，所以它应该是新鲜制作的，而不是引用数据：

  (define list (list 1))

等等，什么？两个 list？这不是 Common Lisp，是吗？ Scheme 是 Lisp-1，而不是 Lisp-2；函数名和值名在同一个命名空间中；所以;不要。

  (define lst (list 1))

  (map (lambda (x)
         (cond
           ((equal? (car x) node)
              (if (equal? list '(1))
                  (set-car! list x)
                  (append! list x)))))

连续两个条件只是一个and，但更重要的是，head sentinel trick意味着你会return真正的结果为(cdr lst)，所以没有必要改变其头部的内容。代码然后简化，这就是首先使用 head sentinel 的全部目的：

  (map (lambda (x)
         (if (equal? (car x) node)
             (append! lst x)))      ; changed the name

没有替代条款？一般来说，不受欢迎，但在这里你做地图是为了它的副作用，所以，只要你不使用map的结果，你就是美好的。更简单的方法是 always 将备用子句作为习惯和良好风格来处理，例如

  (map (lambda (x)
         (if (equal? (car x) node)
             (append! lst x)   ; append two lists together... (see below)
             #f))
       data)

data？那是什么？它应该作为 children?.

的另一个形式参数添加

  (if (equal? lst '(1))

equal?？为什么？要查看我们是否更改了它，只需要

  (if (null (cdr lst))

最少行动原则...

      #f
      (cdr lst)))    ; cdr carries the true payload

（所以基本上，

(define (children? node data)
    (let ((res (filter (lambda (x) (equal? (car x) node)) 
                       data)))
      (if (not (null? res))
         res
         #f)))

)。好的。是吗？好吧，这取决于以下工作是否正常。

(define (append! lst . lsts)
  (if (not (null? lsts))
      (if (null? (cdr lst))
        (begin
          (set-cdr! lst (car lsts))
          (apply append! (car lsts) (cdr lsts)))

它追加列表，因此 (append! (list 1) (list 2)) 将 return 与 (list 1 2) 和 (append! (list 1) (list 2 3)) 与 [ 相同的结果=31=]。要在列表末尾添加一个项目（如 2），我们必须先将其放入另一个列表中。因此，如果我们要添加的项目本身就是一个列表，例如 '(2 3)，我们希望返回 '(1 (2 3))。为此，一个项目必须在附加之前包含在列表中。因此必须修改您的功能才能做到这一点。

      (apply append! (cdr lst) lsts))))

在这里，您再次扫描 (growing) 结果列表以找到它的最后一个单元格，然后再次查找每个添加的项目.您可以通过自己维护最后一个单元格指针并直接使用它来解决这个问题。那是什么"pointer"？它是 lst，你每次 append! 时都会 cdr 它；所以你可以自己直接做(set-cdr! lst (list item))。您当然不能为此使用 lst 变量（为什么？）。

Answer 2

您的代码看起来您正在通过应用 Algol 编程经验（如 C 或 Java）中的知识来学习 Scheme。在 Scheme 中，除非你有充分的理由这样做，否则你应该尝试在不改变的情况下进行编程。保持大部分过程的纯净意味着它更容易测试。

命名约定很重要，并且以 ? 结尾的过程是一个谓词，因此它应该 return 两个值之一，#t 或 #f 就像 isString 应该 return true/false 在 Algol 语言中。

;; graph constructor/accessors not not use car, cadr, etc
;; later you can change it to boxes
(define (make-graph from to weight)
  (list from to weight))
(define graph-from car)
(define graph-to cadr)
(define graph-wight cddr)

;; gets the graphs that has node as starting point
(define (graphs-from node graphs)
  ; match? returns #t if graph starting point is the same as node
  ; since it's symbols we use eq?
  (define (match? graph)
    (eq? node (graph-from graph)))

  ; filters data by starting point
  ; this is the tail expression and thus the result of this procedure
  (filter match? graphs))

(define data (list (make-graph 'x 'y 20)
                   (make-graph 'y 'x 30)
                   (make-graph 'w 'e 20)
                   (make-graph 'x 'e 13)))

(graphs-from 'x data)
; ==> ((x y 20) (x e 13))

(graphs-from 'a data)
; ==> ()

以列表形式保存子列表

Keeping sublists in list form

scheme

lisp

sicp