一般的なLispのマージソートの崩壊

Question

私のアルゴリズムクラスは簡単すぎるので、Common Lispですべての割り当てを行うように挑戦しました（いくつかの理由で）。私はlispを学ぶのに1日目に入り、障害にぶつかった。

割り当ては、任意のサブセット長（Timsort）に達したときに挿入に変換するマージソートを作成することです。挿入セクションは完全に動作しますが、マージの分割部分は、プログラムを2回分割する必要がある場合にのみ機能します。私はそれがリスプで動作する方法リストと関係があることを知っています、私は問題を正確に突き止めるにはあまりにも新しいです。

私はそれが無限ループにぶつかると思います...デバッグステートメントで実行すると、セットに要素が多すぎると決して印刷されないので、わかりません。

私は特定の回答や誰かが自分のコードを書くことを求めているわけではありません。たぶん、説明や正しい方向のポイントが大いに役立ちます！

ありがとうございました！

マイコード：

;; 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に変更することでこれを修正できるというヒントです。あなたがこれ以上欲求不満を抱く必要があるかどうかを教えてください。