Common Lisp广度优先列表遍历get-children lambda实现问题

我编写了一个简易的广度优先图遍历函数，在尝试将其应用于普通列表形式的树结构、而非原生适配该函数的结构化图时，始终无法编写出能返回预期结果的get-children lambda函数，这是个很值得尝试的趣味问题，相关内容如下：

现有广度优先遍历实现 #

遍历函数的核心逻辑是维护一个待处理节点队列，每次取出队首节点执行访问逻辑，再将该节点的所有子节点追加到队尾，实现代码如下：

(defun run-breadth-first (node fn get-children)
  "Run fn breadth-first starting from node, traversing the whole tree."
  (let ((queue (list node)))
    (loop for i = (first queue)
          for inners = (if i (funcall get-children i) nil)
          until (null i)
          when inners do (setf queue (append queue inners))
          do 
          (funcall fn i)
          (pop queue))))

该抽象实用性很强，可以用一行调用完成搜索操作，适配自定义图结构的调用示例如下：

(run-breadth-first sg-node #'find-sg-at-aux #'inner-nodes)

遇到的问题 #

我希望这个函数可以直接遍历普通嵌套列表，而非依赖get-children返回子节点列表的自定义图结构。最初用5am测试语法编写的尝试用例如下：

(test run-breadth-first.test.list
      (let (output)
        (run-breadth-first '(1 2 (3 (4.1 4.2)) 5 (6 (6.1)) 7)
                           (lambda (node) (push (first node) output))
                           (lambda (node) (if (atom (first node))
                                              (list (rest node))
                                            (list (append (rest node) (first node)))))))
      (is (equal output (reverse '(1 2 5 7 3 6 4.1 4.2 6.1)))))

拆分出可单独运行的调试代码：

(let (output)
        (run-breadth-first '(1 2 (3 (4.1 4.2)) 5 (6 (6.1)) 7)
                           (lambda (node) (push (first node) output))
                           (lambda (node) (if (atom (first node))
                                              (list (rest node))
                                            (list (append (rest node) (first node))))))
        output)

运行后返回结果为：

(6.1 4.2 4.1 #1=(6.1) 6 #2=(4.1 4.2) 3 7 (6 #1#) 5 (3 #2#) 2 1)

元素遍历顺序是正确的，但结果中混入了内部列表结构，不符合预期。预期的正确输出为：

(6.1 4.2 4.1 6 3 7 5 2 1)

原因分析 #

原有实现的问题出在两个核心逻辑错误：

• get-children逻辑错误：不管当前节点是什么结构，都将子节点包装为单个元素的列表加入队列，没有把嵌套列表的多个直接子元素拆分为独立节点入队，导致整个子列表被当作单个节点处理，最终混入输出。
• 访问函数fn逻辑错误：默认所有节点都有first可以提取，没有区分子节点类型——嵌套列表只是承载子树的分支容器，不是需要输出的叶子节点，不需要提取内容。

可行解决方案 #

不需要修改原有广度优先遍历函数，只需要调整两个lambda的逻辑即可适配普通嵌套列表结构：

• 对于get-children：非空列表（分支节点）的子节点就是它包含的所有直接元素，直接返回列表本身即可；原子节点（叶子节点）和空列表没有子节点，返回nil。
• 对于访问函数fn：仅对非空的原子节点（叶子节点）执行记录操作，跳过作为容器的列表节点。

修正后的可运行代码如下：

(let (output)
  (run-breadth-first '(1 2 (3 (4.1 4.2)) 5 (6 (6.1)) 7)
                     ;; 访问逻辑：仅记录非空原子（叶子节点）
                     (lambda (node) (when (and node (atom node)) (push node output)))
                     ;; 子节点获取逻辑：非空列表的直接元素就是子节点，原子无后代
                     (lambda (node) (when (consp node) node))))

运行上述代码即可得到预期输出(6.1 4.2 4.1 6 3 7 5 2 1)，对应的5am测试用例可以直接修正为：

(test run-breadth-first.test.list
      (let (output)
        (run-breadth-first '(1 2 (3 (4.1 4.2)) 5 (6 (6.1)) 7)
                           (lambda (node) (when (and node (atom node)) (push node output)))
                           (lambda (node) (when (consp node) node))))
      (is (equal output (reverse '(1 2 5 7 3 6 4.1 4.2 6.1)))))

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