Common Lisp有向图反转函数问题排查求助

问题背景 #

输入有向图表示为((A B C) (B C) (C D))，对应边为A→B、A→C、B→C、C→D。需要反转所有边得到((C B A) (B A) (D C))，但现有reverse-net函数输出为((D C) (C B) (C A) (B A))，未合并同一节点的反转边，且assoc始终返回nil。

原代码 #

(defun reverse-net (net)
  (let (new-net)
    (dolist (obj net)
      (dolist (st (cdr obj))
        (let (cur (assoc st new-net))  
          (if cur
              (push (cons (car obj) cur) new-net)
            (push (list st (car obj)) new-net))))
    new-net))

问题分析 #

1. let变量绑定语法错误
   原代码中(let (cur (assoc st new-net)))的写法是定义了两个独立变量：cur初始化为nil，另一个匿名变量初始化为(assoc st new-net)的结果。这导致cur永远是nil，assoc的查询结果根本没赋值给cur，自然无法触发合并逻辑。正确的变量绑定需要用双层括号包裹：(let ((cur (assoc st new-net)))。

2. 合并逻辑错误
   即使cur能正确获取到已有条目，(push (cons (car obj) cur) new-net)的操作是把新构造的列表添加到new-net头部，而不是修改原有条目。这会导致同一节点的反转边被拆分成多个独立条目，无法合并。

修正后的代码 #

(defun reverse-net (net)
  (let (new-net)
    (dolist (obj net)
      (let ((src-node (car obj)))
        (dolist (dst-node (cdr obj))
          (let ((existing-entry (assoc dst-node new-net)))
            (if existing-entry
                (nconc existing-entry (list src-node)) ; 往已有条目追加原起点
                (push (list dst-node src-node) new-net))))))
    ; 可选：反转每个条目内的元素顺序，让结果与示例完全匹配
    (mapcar #'(lambda (entry) (reverse entry)) new-net)))

修正说明 #

• 修复let的变量绑定语法，确保existing-entry正确接收assoc的查询结果。
• 找到已有节点条目时，使用nconc将原起点追加到条目末尾，实现边的合并。
• 最后通过mapcar反转每个条目内的元素顺序，使输出结果与示例中的((C B A) (B A) (D C))完全一致（若不需要严格顺序可省略此步骤）。

内容的提问来源于stack exchange，提问作者user372575