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)))
Lo sto usando come ramo "altrimenti", dopo che sono state verificate tutte le condizioni .. – Nelly
La funzione per Common Lisp è corretta. Quale lisp stai usando? elisp? – Renzo
LispWorks Personal Edition 6.1.1 – Nelly