如何让过程在Scheme中迭代列表中的每一项？

Question

我正在使用高级学生设置在Scheme中编写一个函数。该函数遍历图G并查看顶点X和Y之间是否存在路径。它“有点”有效，但并不是在所有情况下都有效。我知道问题出在哪里，但我不确定如何解决它。首先，我查看我正在查看的顶点X是否已被访问，如果没有，则继续并将其标记为已访问。然后是函数find-adju。该函数返回给定顶点的所有邻居的列表。例如，如果我有一个这样的图：

(define-struct graph (vertices edges))
(define-struct vertice (name visited))
(define-struct edge (start-vertice end-vertice length))

(define vertices-list
  (list (make-vertice 0 0)
        (make-vertice 1 0)
        (make-vertice 2 0)
        (make-vertice 3 0)
        (make-vertice 4 0)
        )
  )

(define edges-list
  (list (make-edge 0 1 0)
        (make-edge 0 2 0)
        (make-edge 1 3 0)
        (make-edge 2 0 0)
        (make-edge 2 4 0)
        (make-edge 4 2 0)
        )
)
(define G (make-graf vertices-list edge-list))
(traverse-graph? 0 4 G)

然后对于给定的顶点0，它将返回list(1 2)。接下来，我查看列表并询问，我想要的顶点Y是否在其中。如果没有，请再次递归查看列表中的第一项。但在这样做的过程中，我丢失了所有其他邻居的信息。在相同的情况下，它将查看顶点1，找到他的所有邻居，然后该过程将退出，因为它找不到方法。但是顶点2将保持未访问状态。

(define (traverse-graph X Y G)
  (cond
    [(not(eq? (vertex-visited (find-vertex X (graph-vertices G))) VISITED))
     (begin
       (set-vertex-visited! (find-vertex X (graph-vertices G)) VISITED)
       (cond
         [(member Y (find-adju X (graph-edges G))) #t]
         [(not (empty? (find-adju X (graph-edges G)))) (traverse-graph (car (find-adju X (graph-edges G))) Y G) ]
         [else #f]
         )
       )
     ]
    [else #f]
    )
  )

我想也许可以用cdr返回整个列表，而不是将car返回给traverse-function，但我不知道如何实现。当X是一个数字而不是一个列表时，我该如何处理第一步呢？

编辑：

没有对或错。如果我一步一步地调试它，我看到它可能是正确的遍历，但当它到达[(成员条件)时，它停止而不返回任何东西，即使条件为真。

(define (traverse-graph X Y G)
  (cond
    [(not(eq? (vertex-visited (find-vertex X (graph-vertices G))) VISITED))
     (begin
       (set-vertex-visited! (find-vertex X (graph-vertices G)) VISITED)
       (cond
         [(member Y (find-adju X (graph-edges G))) #t]
         [(not (empty? (find-adju X (graph-edges G)))) 
            (for-each (lambda (h)
                  (traverse-graph h Y G)
                  ) (find-adju X (graph-edges G))
                    )
          ]
         [else #f]
         )
       )
     ]
    [else #f]
    )
  )

Answer 1

使用for-each是正确的，但该函数是一个命令式构造。对于列表中的每一条边，它都会说“做这个，做那个”，但不保留任何值。使用map会更幸运，它会遍历列表，并将结果聚合到列表中。

使用map，遍历图的结果将是一个具有深度优先搜索遍历形状的树：

'(result0 (result1 (result3))
          (result2 (result4)))

您可以在每个步骤中使用(apply append (map (lambda …) (find-adju …))附加列表列表，并使用cons预先附加当前节点的结果。不要忘了返回一个包含单个元素的列表，用于遍历的叶子节点，即使用'(#t)和'(#f)。然而，这有一个很大的缺点，在最坏的情况下，时间复杂度是O(N²)。想象一个图，其中每个节点都有两个子节点:一个叶子作为它的右子节点，而图的其余部分作为它的左子节点：

(→ 0 2)    (→ 0 1)
(→ 2 4)    (→ 2 3)
(→ 4 6)    (→ 4 5)
(→ 6 8)    (→ 6 7)
(→ 8 10)   (→ 8 9)
…
(→ 96 98)  (→ 96 97)
(→ 98 100) (→ 98 99)

使用该图，遍历将开始向下钻取左侧边缘，直到到达最左侧的节点(100)，

然后，

• 从to节点98返回，向下转到99，并返回到98，在那里它会将'(result100)附加到'(result99)并预先添加result98，

H120，然后它将向上移动到D21，检查D22，移动回D23，并将D24附加到结果96`、H226、H127…

• 然后，它将移回0，检查1，移回0，将'(… many results here …)附加到'(result1)，并预先添加result0.

由于append必须复制前缀中的所有元素，因此将长度为n的列表附加到长度为m的列表将耗费n操作(第二个列表是简单指向的，不需要复制，因为它形成的尾部与原始的整个第二个列表完全相同)，即它耗费O(n)操作。对append的调用顺序为：

append 1 element to 1 element
append 3 elements to 1 element
append 5 elements to 1 element
append 7 elements to 1 element
append 9 elements to 1 element
…
append 99 elements to 1 element

所以总成本是1+3+5+…+N，其中N是节点总数，大致相当于N²乘以常数因子，因此是O(n²)，这意味着对于大量节点，它将非常慢。有关此at wikipedia的更多信息。

为了避免O(N²)开销，您可以使用累加器:每一步都会在累加器前面加上一个项目，并将其传递。这意味着当处理一个节点时，你必须把当前的累加器给它的第一个邻居，拿回整个子树的修改过的累加器，把它传递给第二个邻居，拿回一个新的修改过的累加器，把它传递给第三个邻居，等等。

为此，您可以在列表上编写自己的递归函数，将最新的累加器和列表作为参数，并使用修改后的累加器(通过处理整个子树获得)和列表的尾部进行递归调用。

您还可以使用对此模式进行抽象的foldl函数。然后，节点处理函数将遵循以下结构：

(define (process node accumulator)
  (foldl ; the function applied to each neighbour of the list,
         ; it is passed the neighbour and the accumulator returned
         ; by the previous iteration
         (lambda (neighbour latest-accumulator)
           (if (visited? neighbour)
               (process neighbour latest-accumulator)
               latest-accumulator)) ; return unchanged
         ; initial accumulator for the first iteration,
         ; we already prepend the result for the current node,
         ; but that could be done afterwards, by prepending
         ; to the final result of `foldl`.
         (cons (compute-result-for node) accumulator)
         ; the list of neighbours:
         (neighbours-of node)))

因为这不会附加列表，而只是在每个步骤中添加一个结果，所以它的复杂度为O(N) (不计算neighbours-of函数的成本，请参阅下面关于哈希表和集合的注释)。虽然数据流有点复杂，但遗憾的是，对于不可变的数据结构，没有更好的选择。

在您的特定情况下，由于返回了一个布尔值，因此还可以简单地使用ormap，它将遍历列表，如果lambda为任何元素返回#t，则返回#t。

这是否像map一样具有O(N²)的复杂度？想一想为什么它不会。

注意，您应该使用#f和#t，而不是0和VISITED，或者#f和'visited (带引号的'符号visited，它在if语句中被认为是真的，就像#f以外的所有值一样)。

为了获得更好的性能，请使用哈希表和集合来存储边，因为如果有许多边，则在列表中查找边的成本会很高。

最后，我建议将一段代码的结束括号放在最后一行的末尾，而不是将它们单独放在各自的行上。这是Scheme、球拍和大多数其他Lisp变体中的常见做法，并使代码更具可读性。

Answer 2

但当它达到[(成员条件时，它将停止而不返回任何内容，即使该条件为真。)

首先检查列表是否由

 (find-adju X (graph-edges G)))

是空的。然后检查列表是否是非空的，以及Y是否在该列表中。然后有一个else情况，其中列表是非空的，但Y不在紧邻的列表中。