common-lisp - Common Lisp 合并排序崩溃

Question

我挑战自己完成了 Common Lisp 算法课上的所有作业。我在学习 lisp 的第一天就遇到了障碍。

任务是创建一个合并排序，当您达到任意子集长度时转换为插入排序 (Timsort)。插入部分工作完美，但合并的拆分部分仅在程序必须拆分两次时才有效。我知道这与列表在 lisp 中的工作方式有关，我太新了，无法确定问题所在。

我认为它要么进入无限循环......我不确定，因为当我使用调试语句运行它时，当集合中的元素太多时它们永远不会被打印出来。

我不是在这里乞求具体答案或要求某人编写我的代码。也许解释或指出正确的方向会有很大帮助!

我的代码:

;; Insertion sort method call (returns sorted list)
(defun insert-sort (lst) ... )

;; Merge sort method call
(defun merge-sort (lst)
  (print 'Merge)
  (print lst)
  (if (< (length lst) 7) ; Check to see if list is small enough to insert sort
      (insert-sort lst) ; Do so
      (progn ; else
        (setf b (merge-split lst)) ; Split the list, store into b
        (setf (car b) (merge-sort (car b))) ; Merge sort on first half
        ;; --- I think it's happening here ---
        (setf (cdr b) (merge-sort (cdr b))) ; Merge sort on second half
        (merge 'list (car b) (cdr b) #'<)))) ; Merge the two lists together (using API)

;; Split a list into two parts
(defun merge-split (lst)
   (progn
     (setf b lst) ; Set b to first index
     (setf a (cdr lst)) ; Set a to the rest of the list
     (loop while a do ; Loop while a != null
           (setf a (cdr a)) ; Make a equal next list node
           (if a ; If it still exists
               (progn
                 (setf a (cdr a)) ; Inc a again
                 (setf b (cdr b))))) ; Also inc b (b should always be half of a)
     (setf a (cdr b)) ; Set a to the list after b
     (setf (cdr b) NIL) ; Delete link after b
     (cons lst a))) ; Return in a cons

注意:这是我写的代码，不是从网上下载的...不过你大概能看出来哈哈

Answer 1

您正被动态范围的变量所困扰。第一次调用 SETF 设置 a、b 时，您隐式创建了全局的、动态作用域的变量。请改用 LET 来声明它们。 LET 允许您包含要执行的表达式列表，就像 PROGN 一样，所以我的提示是您可以通过将 2 个 PROGN 更改为 LET 来解决此问题。让我知道您是否需要比这更多的东西才能摆脱困境。