scheme - 以列表形式保存子列表

Question

我正在做一项遍历 DAG 的家庭作业，寻找最短路线。在一些 SO 答案的帮助下，我已经准备好了很多东西。话虽如此，我在获取返回子列表列表的函数时遇到了麻烦，就像我需要进一步处理数据一样。数据文件有一个形式为(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 技巧意味着您将返回真实结果 (cdr lst) ，因此无需更改其头部的内容。然后代码进行了简化，这就是首先使用 head sentinel 的全部目的:

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

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

  (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))将返回与 (list 1 2) 相同的结果和 (append! (list 1) (list 2 3))与(list 1 2 3)相同.要在列表末尾添加一个项目(如 2 )，我们必须先将其放入另一个列表中。因此，如果我们添加的项目本身就是一个列表，例如 '(2 3) , 我们想得到 '(1 (2 3))后退。为此，一个项目必须在附加之前包含在列表中。因此必须修改您的函数才能做到这一点。

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

在这里，您扫描(不断增长)的结果列表以找到它的最后一个单元格，再次每次添加的项目。您可以通过自己维护最后一个单元格指针并直接使用它来解决这个问题。那个“指针”是什么？这是lst ，你cdr每次你append!对它有所帮助；所以你可以做 (set-cdr! lst (list item))直接你自己。你当然不能使用 lst变量(为什么？)。