J'essaye d'inverser une liste en Lisp, mais j'obtiens l'erreur: "Erreur: Exception C0000005 [flags 0] at 20303FF3 {Offset 25 inside #} eax 108 ebx 200925CA ecx 200 edx 2EFDD4D esp 2EFDCC8 ebp 2EFDCE0 esi 628 edi 628 "

Mon code est le suivant:

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

Quelqu'un peut-il me dire ce que je fais de mal? Merci d'avance!

6
Nelly 22 déc. 2015 à 22:01

4 réponses

Meilleure réponse

Votre code tel qu'il est écrit est logiquement correct et produit le résultat souhaité:

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 y a quelques problèmes en termes de performances. La fonction append produit une copie de tout sauf son argument final. Par exemple, lorsque vous faites (ajouter '(1 2)' (ab) '(3 4))) , vous créez quatre nouvelles cellules contre, dont les voitures sont 1, 2, a et b. Le cdr du dernier est la liste existante (3 4). En effet, la mise en œuvre de ajouter ressemble à ceci:

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

Ce n'est pas exactement l ' append de Common Lisp, car l' append de Common Lisp peut prendre plus de deux arguments. C'est assez proche pour montrer pourquoi toutes les listes sauf la dernière sont copiées. Maintenant, regardez ce que cela signifie en termes de mise en œuvre de rev , cependant:

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

Cela signifie que lorsque vous inversez une liste comme (1 2 3 4) , c'est comme si vous étiez:

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

Maintenant, à la ligne (2), vous copiez la liste (4 3). Dans la première ligne, vous copiez la liste (4 3 2) qui comprend une copie de (4 3). Autrement dit, vous copiez une copie . C'est une utilisation assez inutile de la mémoire.

Une approche plus courante utilise une variable d'accumulation et une fonction d'assistance. (Notez que j'utilise endp , rest , first et list * au lieu de null , cdr , voiture et contre , car il est plus clair que nous travaillons avec des listes, pas des contre-arbres arbitraires. Ils sont à peu près les mêmes (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 une fonction d'assistance externe, il serait probablement plus courant d'utiliser des étiquettes pour définir une fonction d'assistance locale:

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

Ou, comme Common Lisp n'est pas garanti pour optimiser les appels de queue, une boucle do est également agréable et propre:

(defun rev (list)
  (do ((list list (rest list))
       (reversed '() (list* (first list) reversed)))
      ((endp list) reversed)))
5
Joshua Taylor 23 déc. 2015 à 13:45

Vous n'avez probablement plus d'espace dans la pile; c'est la conséquence de l'appel d'une fonction récursive, rev, en dehors de la position de la queue. L'approche de conversion en une fonction récursive de queue consiste à introduire un accumulateur, la variable result dans ce qui suit:

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

Votre fonction rev devient alors:

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

Exemples:

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

* (reving '1 '())
(1)
0
GoZoner 26 déc. 2015 à 17:36

Si vous pouvez utiliser les fonctions de bibliothèque CL standard telles que append, vous devez utilisez reverse (comme Kaz suggéré).

Sinon, s'il s'agit d'un exercice (h / w ou non), 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 spécifique est incompréhensible, veuillez contacter votre fournisseur.

0
Community 23 mai 2017 à 12:30

Dans ANSI Common Lisp, vous pouvez inverser une liste en utilisant la fonction reverse (non destructive: alloue une nouvelle liste), ou nreverse (réorganise les blocs de construction ou les données de la liste existante pour produire celle inversée) .

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

N'utilisez pas nreverse sur les littéraux de liste entre guillemets; il s'agit d'un comportement non défini et peut se comporter de manière surprenante, car il s'agit de facto de code auto-modifiable.

3
Kaz 22 déc. 2015 à 19:37