COMMUNE LISP MERGE BRAKING DUPPORD

Question

Je me suis mis au défi de faire toutes les missions dans ma classe d'algorithmes en LISP commun. Je suis dans le premier jour de l'apprentissage de Lisp et j'ai frappé un obstacle.

L'attribution consiste à créer un tri de fusion qui se convertit en insertion lorsque vous arrivez à une longueur de sous-ensemble arbitraire (TIMSORT). La section d'insertion fonctionne parfaitement, mais la partie partagée de la fusion ne fonctionne que lorsque le programme doit se séparer deux fois. Je sais que cela a à voir avec la façon dont les listes fonctionnent dans LISP, je suis trop nouveau pour identifier le problème.

Je pense que cela frappe une boucle infinie ... Je ne suis pas sûr parce que lorsque je l'exécute avec des instructions de débogage, ils ne sont jamais imprimés lorsque l'ensemble a trop d'éléments.

Je ne suis pas ici en train de mendier des réponses spécifiques ou pour que quelqu'un rédige mon code. Peut-être qu'une explication ou un point dans la bonne direction aiderait beaucoup!

Mon code:

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

Remarque: c'est du code que j'ai écrit, je ne suis pas sorti d'Internet ... vous pouvez probablement le dire haha

Answer 1

Vous êtes mordu par des variables de portée dynamiquement. La première fois que vous appelez setf pour définir A, b, vous créez implicitement des variables globales et gênées dynamiquement. Utilisez à la place pour les déclarer. Vous permet d'inclure une liste d'expressions à exécuter, tout comme PROGN, donc mon indice est que vous pouvez résoudre ce problème en modifiant vos 2 pronostics en location. Faites-moi savoir si vous avez besoin de plus que cela pour vous décoller.