l'inversion de liste en Lisp

Votre code écrit est logiquement correct et produit le résultat que vous voulez:

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)

Cela dit, il ya quelques problèmes avec elle en termes de performances. Le ajouter la fonction produit une copie de tous, mais son argument final. E. g., lorsque vous ne (append '(1 2) '(a b) '(3 4)), vous êtes en train de créer quatre nouveaux cons cellules, dont les voitures sont 1, 2, a et b. Le cdr de la dernière, c'est la liste existante (3 4). C'est parce que la mise en œuvre de ajouter est quelque chose comme ceci:

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

Ce n'est pas exactement Common Lisp est ajouter, puisque la Common Lisp est ajouter peut prendre plus de deux arguments. Il est assez proche de démontrer pourquoi tous, mais le dernier de la liste est copié, si. Maintenant, regardez ce que cela signifie en termes de mise en œuvre de rev:

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

Cela signifie que lorsque vous êtes à l'inversion d'une liste comme (1 2 3 4), c'est comme vous êtes:

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

Dans la ligne (2), vous êtes à la copie de la liste (4 3). En ligne, vous êtes la copie de la liste (4 3 2), qui comprend une copie de (4 3). Qui est, vous êtes de la copie d'une copie. C'est un joli gaspillage dans l'utilisation de la mémoire.

Une approche plus commune utilise un accumulateur variable et une fonction d'assistance. (Notez que j'utilise endp, reste, première, et liste* au lieu de null, cdr, voiture, et contre, car cela les rend plus clair le fait que nous travaillons avec des listes, pas arbitraire contre-arbres. Ils sont à peu près la même (mais il y a quelques différences).)

(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)

Avec cette fonction d'assistance, il est facile de définir 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)

Cela dit, plutôt que d'avoir un externe de la fonction d'assistance, il serait probablement plus courant d'utiliser étiquettes à définir une fonction d'assistance:

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

Ou, depuis Common Lisp n'est pas garanti pour optimiser la queue des appels, un ne boucle est agréable et propre, ici aussi:

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

OriginalL'auteur Joshua Taylor

Si vous pouvez utiliser la norme CL des fonctions de la bibliothèque comme append, vous devez utiliser inverse (comme Kaz a suggéré).

Sinon, si c'est un exercice (h/l ou pas), vous pouvez essayer ceci:

(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. Votre erreur est incompréhensible, veuillez contacter votre fournisseur.

OriginalL'auteur sds