lista inversione in Lisp

Question

Sto cercando di invertire una lista in Lisp, ma ottengo l'errore: "Errore: C0000005 di eccezione [flags 0] a 20303FF3 {Offset 25 all'interno #} eax 108 ebx 200925CA ecx 200 edx 2EFDD4D esp 2EFDCC8 ebp 2EFDCE0 esi 628 edi 628 "

Il mio codice è il seguente:

(defun rev (l) 
    (cond 
     ((null l) '()) 
     (T (append (rev (cdr l)) (list (car l)))))) 

qualcuno può dirmi che cosa sto facendo di sbagliato? Grazie in anticipo!

Answer 1

Il codice come scritto è logicamente corretto e produce il risultato che ci si vuole a:

CL-USER> (defun rev (l) 
      (cond 
      ((null l) '()) 
      (T (append (rev (cdr l)) (list (car l)))))) 
REV 
CL-USER> (rev '(1 2 3 4)) 
(4 3 2 1) 
CL-USER> (rev '()) 
NIL 
CL-USER> (rev '(1 2)) 
(2 1) 

Detto questo, ci sono alcuni problemi con esso in termini di prestazioni. La funzione append produce una copia di tutto tranne il suo argomento finale. Ad esempio, quando fai (append '(1 2)' (a b) '(3 4)), stai creando quattro nuove celle contro, le cui macchine sono 1, 2, ae b. Il cdr di quello finale è l'elenco esistente (3 4). Questo perché l'attuazione della accodare è qualcosa di simile:

(defun append (l1 l2) 
    (if (null l1) 
     l2 
     (cons (first l1) 
      (append (rest l1) 
        l2)))) 

che non è esattamente comune di Lisp accodare, perché aggiungere può durare più di due argomenti di Common Lisp. È abbastanza vicino da dimostrare perché tutti tranne l'ultimo elenco vengono copiati, però. Ora, guardare a ciò che significa in termini di vostra implementazione di rev, però:

(defun rev (l) 
    (cond 
    ((null l) '()) 
    (T (append (rev (cdr l)) (list (car l)))))) 

Questo significa che quando si sta invertendo una lista come (1 2 3 4), è come se fossi :

(append '(4 3 2) '(1))    ; as a result of (1) 
(append (append '(4 3) '(2)) '(1)) ; and so on...  (2) 

Ora, nella riga (2), si sta copiando l'elenco (4 3). Nella prima riga, stai copiando l'elenco (4 3 2) che include una copia di (4 3). Cioè, sei copiando una copia. Questo è un uso piuttosto dispendioso della memoria.

Un approccio più comune utilizza una variabile di accumulo e una funzione di supporto. (Si noti che io uso endp, resto, prima, e lista * invece di nulla, cdr, auto, e contro, dal momento che rende più chiaro che siamo uso delle liste, non arbitrari contro-alberi. sono più o meno lo stesso (ma ci sono alcune differenze).)

(defun rev-helper (list reversed) 
    "A helper function for reversing a list. Returns a new list 
containing the elements of LIST in reverse order, followed by the 
elements in REVERSED. (So, when REVERSED is the empty list, returns 
exactly a reversed copy of LIST.)" 
    (if (endp list) 
     reversed 
     (rev-helper (rest list) 
        (list* (first list) 
         reversed)))) 

CL-USER> (rev-helper '(1 2 3) '(4 5)) 
(3 2 1 4 5) 
CL-USER> (rev-helper '(1 2 3) '()) 
(3 2 1) 

Con questa funzione di supporto, è facile da definire rev:

(defun rev (list) 
    "Returns a new list containing the elements of LIST in reverse 
order." 
    (rev-helper list '())) 

CL-USER> (rev '(1 2 3)) 
(3 2 1) 

Detto questo, piuttosto che avere una funzione di supporto esterno, sarebbe probabilmente più comune l'uso di etichette per definire una funzione di supporto locale:

(defun rev (list) 
    (labels ((rev-helper (list reversed) 
      #| ... |#)) 
    (rev-helper list '()))) 

Or , Dal momento che Common Lisp non è garantito per ottimizzare le chiamate di coda, un ciclo fare è bella e pulita anche qui:

(defun rev (list) 
    (do ((list list (rest list)) 
     (reversed '() (list* (first list) reversed))) 
     ((endp list) reversed))) 

Answer 2

In ANSI Common Lisp, è possibile invertire un elenco utilizzando la funzione reverse (non distruttiva: alloca un nuovo elenco) o nreverse (riorganizza i blocchi predefiniti oi dati dell'elenco esistente per produrre quello invertito).

> (reverse '(1 2 3)) 
(3 2 1) 

Non usare nreverse sui valori letterali lista citate; è un comportamento indefinito e può comportarsi in modi sorprendenti, dal momento che è codice auto-modificante di fatto.

Answer 3

Se è possibile utilizzare le funzioni della libreria CL standard come append, è necessario utilizzare reverse (come Kaz suggested).

In caso contrario, se si tratta di un esercizio (h/w o no), si può provare questo:

(defun rev (l) 
    (labels ((r (todo) 
      (if todo 
       (multiple-value-bind (res-head res-tail) (r (cdr todo)) 
        (if res-head 
         (setf (cdr res-tail) (list (car todo)) 
          res-tail (cdr res-tail)) 
         (setq res-head (list (car todo)) 
          res-tail res-head)) 
        (values res-head res-tail)) 
       (values nil nil)))) 
    (values (r l)))) 

PS. Il tuo errore specifico è incomprensibile, contatta il tuo fornitore.

Answer 4

Probabilmente avete esaurito lo spazio di stack; questa è la conseguenza della chiamata a una funzione ricorsiva, rev, al di fuori della posizione di coda. L'approccio alla conversione in una funzione ricorsiva in coda comporta l'introduzione di un accumulatore, la variabile result nella seguente:

(defun reving (list result) 
    (cond ((consp list) (reving (cdr list) (cons (car list) result))) 
     ((null list) result) 
     (t (cons list result)))) 

È rev funzione diventa quindi:

(define rev (list) (reving list '())) 

Esempi:

* (reving '(1 2 3) '()) 
(3 2 1) 
* (reving '(1 2 . 3) '()) 
(3 2 1) 

* (reving '1 '()) 
(1)