Unione comune di unione ordinarsi

Question

Mi sono sfidato a fare tutti i compiti nella mia classe di algoritmi in comune lisp.Sono al giorno uno di apprendimento LISP e ho colpito un ostacolo.

L'assegnazione è creare un tipo di unione che si converte in inserimento quando si arriva a una lunghezza del sottoinsieme arbitrario (Timsort).La sezione di inserimento funziona perfettamente, ma la parte divisa della fusione funziona solo quando il programma deve dividere due volte.So che ha a che fare con il modo in cui le liste funzionano a Lisp, sono semplicemente troppo nuovo per individuare il problema.

Penso che colpisca un ciclo infinito ... Non sono sicuro perché quando lo eseguo con le dichiarazioni di debug, non vengono mai stampati quando il set ha troppi elementi.

Non sono qui implorando risposte specifiche o per qualcuno di scrivere il mio codice.Forse una spiegazione o un punto nella giusta direzione aiuterebbe molto!

Il mio codice:

;; 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: questo è il codice che ho scritto, non è uscito da Internet ... probabilmente puoi dire a Haha

Answer 1

Sei morso da variabili scambiate dinamicamente.La prima volta che chiami SetF per impostare A, B crea implicitamente variabili globali e dinamicamente ambiti.Usare lascia invece di dichiararli.Consente di includere un elenco di espressioni da eseguire, proprio come PRUGN, quindi il mio suggerimento è che puoi risolverlo cambiando i tuoi 2 progns in lascia.Fammi sapere se hai bisogno di più di questo per essere scollato.