将子列表保留为列表形式

Question

我正在做一项家庭作业，以遍历DAG，找到最短的路线。 在一些SO答案的帮助下，我有相当多的作品。 话虽如此，我无法获得一个函数来返回子列表列表，例如我需要进一步处理数据。 数据文件具有以下形式的子列表列表(节点 1 节点 2 权重)

(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))))

当我跑步时(孩子？'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，但更重要的是，头部哨兵技巧意味着你会返回真实结果为(cdr lst)，所以没有必要改变它的头部内容。然后代码简化，这就是首先使用头部哨兵的全部目的：

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

没有替代条款？一般来说，不赞成，但在这里你做地图是为了它的副作用，所以，只要你不使用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，每次你append!它时，你都会cdr它;所以你可以直接做(set-cdr! lst (list item))。当然，您不能为此使用lst变量(为什么？

Answer 2

你的代码看起来你正在通过应用来自 Algol 编程经验(如 C 或 Java)的知识来学习 Scheme。在 Scheme 中，你应该尝试在没有突变的情况下进行编程，除非你有充分的理由这样做。保持大多数程序的纯正意味着更容易测试。

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

;; 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)
; ==> ()