CLISP - Inverser une simple liste

Je dois inverser les éléments d'une liste simple (une dimension). Je sais qu'il y a une fonction inverse intégrée mais je ne peux pas l'utiliser pour ça.CLISP - Inverser une simple liste

Voilà ma tentative:

(defun LISTREVERSE (LISTR) 
    (cond 
     ((< (length LISTR) 2) LISTR) ; listr is 1 atom or smaller 
     (t (cons (LISTREVERSE (cdr LISTR)) (car LISTR))) ; move first to the end 
    ) 
)

sortie assez proche, mais est faux.

[88]> (LISTREVERSE '(0 1 2 3)) 
((((3) . 2) . 1) . 0)

J'ai donc essayé d'utiliser append au lieu de cons:

(t (append (LISTREVERSE (cdr LISTR)) (car LISTR)))

mais nous avons eu cette erreur:

*** - APPEND: A proper list must not end with 2

Toute aide?

Source

2012-04-19 user1342836

L'utilisation de LENGTH n'est pas une bonne idée. Cela va à l'encontre de l'objectif des listes de cellules contre liées. LONGUEUR traverse toute la liste pour déterminer la longueur. –

L'erreur APPEND est un peu cryptique, mais cela signifie que le dernier des arguments n'est pas une liste, mais le numéro 2. –

Sauf erreur, votre version 'append' devrait fonctionner tant que vous faites le dernier argument dans une liste. – Marcin

Je peux vous donner quelques indications, parce que cela ressemble à des devoirs:

Le cas de base de la récursion est lorsque la liste est vide (null) et pas quand il y a moins de deux éléments de la liste
Envisager de définir une fonction d'assistance avec un paramètre supplémentaire, un "accumulateur" initialisé dans la liste vide. Pour chaque élément dans la liste d'origine, cons il en tête de l'accumulateur. Lorsque la liste d'entrée est vide, renvoyer l'accumulateur

En note de côté, la solution ci-dessus est récursive en queue.

Source

2012-04-19 03:09:15

J'ai essayé de le faire avec la base de référence null, mais alors j'obtiens '((((NIL 3) 2) 1) 0)'. Aussi Je sais que la récursion en queue est nécessaire en Lisp pour que ça marche vite mais je ne veux pas en faire trop quand les spécifications disent 'une fonction'. – user1342836

@ user1342836 vous obtenez ces résultats étrangement _precisely_ parce que vous n'utilisez pas un paramètre en tant qu'accumulateur pour contenir vos résultats. Dans ce cas, la solution la plus simple est aussi celle qui est la plus efficace: utiliser l'accumulateur - d'ailleurs, c'est une récursion de la queue, vous ne serez pas en train de l'exagérer. –

Je l'ai eu fonctionnant sans la récursion de queue, mais seulement parce que c'est une liste de dimension simple (avec plus de dimensions je peux voir le besoin). null était le cas de base cependant. merci pour cet indice – user1342836

En tant que suivi de Óscar López (et la lutte contre la tentation de simplement écrire une autre solution vers le bas):

utilisant à la fois append et length fait la solution affichée à peu près la façon la moins efficace de renverser un liste. Consultez la documentation sur cons et null pour de meilleures idées sur la façon de mettre en œuvre cela.
S'il vous plaît, s'il vous plaîtindent properly.
La récursion de queue est à la fois plus efficace et raisonnablement simple dans ce cas. Essayez-le si vous ne l'avez pas déjà fait. labels est le formulaire que vous souhaitez utiliser pour définir les fonctions récursives locales. Il peut être utile de passer par The Little Schemer. Cela vous donnera une meilleure idée de la récursivité en général.

Source

2012-04-19 14:05:31 Inaimathi

Ces règles d'indentation sont stupides. +1 pour les autres parties de la réponse. –

@SethCarnegie - Je déduis que vous êtes un programmeur C++ ou Java dont l'éditeur ne fait pas de paren-matching. – Inaimathi

Quel éditeur n'effectue pas de correspondance paren? –

C'est bien ce que vous avez fait. Vous avez seulement manqué la composition de la liste des résultats.

Pensez-y: Vous devez ajouter la liste 1 élément de la RCA à la fin de la liste des CDR inversée:

(defun LISTREVERSE (LISTR) 
    (cons 
     ((< (length LISTR) 2) LISTR) ; listr is 1 atom or smaller 
     (t (append (LISTREVERSE (cdr LISTR)) (list (car LISTR))))))

Source

2012-04-20 20:11:42 Patrick

(defun listreverse (list) 
    (let (result) 
    (dolist (item list result) 
     (push item result))))

Ne pas utiliser récursivité en commun Lisp quand il y a un moyen itératif simple d'atteindre le même but.Common Lisp ne donne aucune garantie sur la récursivité de la queue, et votre invocation de la fonction récursive de queue ne peut pas être optimisée pour un saut à la discrétion du compilateur.
push ajoute l'élément au résultat
dolist a un troisième argument optionnel qui est la valeur retournée. Il est évalué lorsque la boucle est quittée.

Source

2013-03-17 19:33:05 hans23

CLISP - Inverser une simple liste

Répondre

Questions connexes