Common Lisp merge sort quebrar

Question

Eu já desafiou-me para fazer todas as tarefas no meu algoritmos de classe em Common Lisp.Eu estou em um dia de aprendizagem lisp e eu bati um obstáculo.

A missão é criar uma mesclagem de classificação que converte a inserção quando você chegar a um subconjunto arbitrário comprimento (Timsort).A inserção seção funciona perfeitamente, mas a parte dividida da série só funciona quando o programa tem para dividir duas vezes.Eu sei que tem a ver com a forma como funcionam as listas em lisp, eu sou muito nova para identificar o problema.

Eu acho que atingir um loop infinito...Eu não tenho certeza porque quando eu executar com instruções de depuração, que nunca se impresso quando o conjunto tem muitos elementos.

Eu não estou aqui implorando por respostas específicas ou para alguém para escrever o meu código.Talvez uma explicação ou um ponto na direção certa, iria ajudar muito!

O meu código:

;; 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

Nota:Este é o código que eu escrevi, não ficaram fora da internet...você provavelmente pode dizer que haha

Answer 1

Você está sendo mordido por escopo dinamicamente variáveis.A primeira vez que você chamar SETF para definir a, b implicitamente criar globais, escopo dinamicamente variáveis.Usar o que em vez de declará-los.DEIXE permite que você inclua uma lista de expressões para executar, assim como PROGN, então a minha dica é que você pode corrigir isso alterando o seu 2 PROGNs para o Permite.Deixe-me saber se você precisar de mais do que isso para obter o coreto.