Pour écrire une fonction Lisp commune qui renverra la négation d'une liste

Question

Je reçois cette erreur avec mon code actuel:

LET: illegal variable specification 
    (COND (LISTP A (IF (NEGATE A) (NEGATE (REST L)) NIL)) 
    (T (SETF A (-A) (APPEND (LIST A) (REST L)) (NEGATE (REST L)) NIL))) 

mon code actuel:

(defun negate(L) 
(setq x -1) 

(if (not (null L)) 

    (let ((a (fitst L)) 
     (cond (listp a 
       (if (negate a) 
        (negate (rest L)) 
       nil)) 
     (t 
     (setf a (-a) (append (list a)(rest L)) 
       (negate (rest L)) 
       nil)))) 
) 
)) 

et les cas de test, il doit passer

o List is (1 2 3 4) 
o Output should be: (-1 -2 -3 -4) 

o List is (1 -2 (3 4)) 
o Output should be: (-1 2 (-3 -4)) 

Answer 1

Dans le sens le plus poli, votre code est un peu hors tension. Tu apprends Lisp cette semaine, n'est-ce pas? C'est bon! C'est un langage amusant et peut vraiment faire des choses géniales. Je vais donc passer en revue la création de la routine et vous emmener le long de la visite.

Votre cas de base est -

(defun negate (n) 
    (if (> n 0) (- 0 n))) 

(map #'negate '(1 2 3 4)) 

marche l'arbre est plus complexe, mais nous allons marcher à travers les idées. Essentiellement, vous avez trois cas pour répondre: l'élément courant est-il nul, une liste ou un atome?

(if (not (car seq)) 
    (if (listp (car seq)) 
    ;;Recurse 
    ;;Otherwise negate the current element and append it to the recursed. 

Essayons d'abord à cette coupe:

(defun negate-seq (seq) 
    (if (not seq) 
     (return-from negate-seq)) 

    (if (listp (car seq)) 
     (negate-seq seq) 
    (list (negate (car seq)) (negate-seq (cdr seq))))) 

C'est génial! Sauf que ...

(negate-seq '(1 2)) ==> (-1 (-2 NIL)) 

Et ...

(negate-seq '(1 (1 2 -3))) ==> STACK OVERFLOW! 

Oh boy. Nous avons des problèmes maintenant. Tout d'abord, essayons un cons au lieu d'un list. Cela nettoie le problème de la liste imbriquée étrange.

Il est évident que nous sommes dans une boucle de récursion infinie. Cela ne devrait pas être possible, car nous avons la garde not seq. Ok, alors essayons un débogage. J'utilise CLISP, et je peux tracer avec des arguments:

(trace 'negate-seq) 

puis,

(negate-seq '(1 (1 2 -3))) 

Tout à coup, je vois une explosion de

1621. Trace: (NEGATE-SEQ '((1 2 -3))) 
1622. Trace: (NEGATE-SEQ '((1 2 -3))) 
1623. Trace: (NEGATE-SEQ '((1 2 -3))) 
1624. Trace: (NEGATE-SEQ '((1 2 -3))) 

Crikey, j'ai oublié mon cdr et Contre le cas de liste! Hmmmm.

Essayons:

(defun negate-seq (seq) 
    (if (not seq) 
     (return-from negate-seq)) 

    (if (listp (car seq)) 
     (cons (negate-seq (car seq)) 
     (negate-seq (cdr seq))) 
    (cons (negate (car seq)) (negate-seq (cdr seq))))) 

Recurse pour la voiture, récuser sur la voiture, les contre ensemble, nous pourrions être à quelque chose.

(negate-seq '(1 (1 2 -3))) => (-1 (-1 -2 NIL) 

Hmmmm. Jetons un coup d'oeil à la trace.

1. Trace: (Negate-SEQ '(1 (1 2 -3)))
2. Trace: (Negate-SEQ' ((1 2 -3)))
3. Trace: (nions-SEQ '(1 2 -3))
4. Trace: (negate-SEQ' (2 -3))
5. Trace: (negate-SEQ « (-3))
6. Trace: (NEGATE- SEQ 'NIL)
7. Trace: NEGATE-SEQ ==> NIL
8. Trace: NEGATE-SEQ ==> (NIL)
9. Trace: NEGATE-SEQ ==> (-2 NIL)
10. Trace: NEGATE-SEQ ==> (-1 -2 NIL)
11. trace: (SEQ nions-NIL)
12. trace: nEGATE-SEQ ==> NIL
13. trace: nEGATE-SEQ ==> ((-1 -2 NIL))
14. trace: nEGATE-SEQ = => (-1 (-1 -2 NIL))

Je répète e jusqu'à ce que le -3, alors ... il tombe? Impair. Ah! Je saisis continuellement le CDR des choses. Un CDR est toujours une liste. (cdr '(-3)) est nul!

Voyons voir ....

(beaucoup farfouiller)

Négation retourne nul sur positif. D'oh.

(defun negate (n) 
    (if (> n 0) 
     (- 0 n) 
    n)) 


(defun negate-seq (seq) 
    "Written by Paul Nathan" 
    (if (not seq) 
     (return-from negate-seq)) 

    (if (listp (car seq)) 
     (cons (negate-seq (car seq)) 
     (negate-seq (cdr seq))) 
    (cons (negate (car seq)) 
     (negate-seq (cdr seq))))) 

Answer 2

Je ne suis pas sûr si vous cherchez un petit coup de pouce pour corriger le code présenté, ou si vous êtes de solliciter d'autres façons de le faire. Ma première pensée est allé à mapcar:

(defun negate-tree (tree) 
    (mapcar (lambda (e) 
      (cond 
       ((null e) nil) 
       ((listp e) (negate-tree e)) 
       (t (- e)))) 
      tree)) 

Vous pouvez ensuite généraliser sur l'aspect de la négation, et écrire à la place map-tree, d'accepter une fonction d'appliquer aux atomes dans l'arbre:

(defun map-tree (f tree) 
    (mapcar (lambda (e) 
      (cond 
       ((null e) nil) 
       ((listp e) (map-tree f e)) 
       (t (funcall f e)))) 
      tree)) 

Vous pouvez appeler dessus avec, par exemple, la fonction de négation unaire:

(map-tree #'- '(1 -2 (3 4))) 

un tel appel suppose que toutes les feuilles de l'arbre sont soit nil une pris en charge par la fonction de négation unaire.

Accepter nil comme une feuille possible dans l'arbre fait l'algorithme de visite un peu en désordre, et on ne sait pas si la fonction fournie f doit être appliquée à toutes les feuilles — même celles qui sont nil — de sorte que la fonction elle-même peut décider si et comment traiter nil.

Un autre inconvénient de cette version est de savoir comment elle traite les cellules qui ne sont pas proper lists.Notez que la fonction listp renvoie la valeur true pour toutes les cellules —, même celles qui ne constituent pas des listes correctes — mais mapcar exige que son entrée soit une liste correcte. Nous pouvons remonter le long de notre chemin "listp true", en appelant récursivement mapcar, et avoir mapcar échouer pour recevoir une liste incorrecte. Cela signifie que l'algorithme ci-dessus aurait besoin de tester les cellules pour voir si elles sont correctes avant de les passer à mapcar, en traitant peut-être celles qui ne le sont pas (je répugne à dire "atomes" ici), ou être documenté que la structure arborescente attendue est constituée de listes appropriées de listes appropriées. Si vous devez accepter des «arbres» de premier niveau qui ne sont pas nécessairement des listes eux-mêmes, ce qui signifie qu'un atome solitaire est un arbre valide, ou nil est un arbre valide, vous pouvez déchirer les parties constituantes de la fonction ci-dessus et en écrire une qui n'utilise que mapcar après avoir déterminé que l'arbre sous inspection est une liste.

Answer 3

Si vous écrivez:

(defun negate (n) 
    (if (> n 0) 
    (- 0 n) 
    n)) 

vous limitez votre code à des nombres réels.

Si au contraire, vous utilisez la fonction primitive negate fournie par Common Lisp, il travaillera sur un nombre:

(mapcar (function -) '(1 2/3 #C(4 5)))  
--> (-1 -2/3 #C(-4 -5)) 

Answer 4

Voici ce que je ferais. Bien sûr, je ne considère que les listes numérotées. Donc, il y aurait des erreurs si la liste n'est pas entièrement numérique.

(defun negate (list) 
     (flet ((negate-number (x) 
      (- x))) 
    (labels ((negate-helper (list neg-list) 
      (if (null list) 
       neg-list ; when all elements are considered return neg-list 
       (let ((num-or-list (car list))) 
      (if (numberp num-or-list) 
       ;; if number then negate it and add it into the new list (i.e. neg-list) 
       (negate-helper (cdr list) (append neg-list (list (negate-number num-or-list)))) 
       ;; if list then first negate the sublist 
       (negate-helper (cdr list) (append neg-list (list (negate-helper num-or-list nil))))))))) 
     (negate-helper list nil)))) 

Answer 5

Vous pouvez y parvenir par la procédure suivante:

(defun negate (l)"returns a list of multiplication negative of elements of a list l, 
        element of list l to be each numbers for not to type err, 
        and list l may not be a list of atoms." 
    (cond 
    ((null l) nil) 
    ((consp (car l)) (cons (negate (car l)) 
          (negate (cdr l)))) 
    (t (cons (* -1 (car l)) 
      (negate (cdr l)))))) 

on peut aussi avoir une autre version. J'ai essayé d'écrire une procédure récursive en queue, mais ce n'est pas complètement tr.

réalise la même chose sauf qu'il ne donne pas le même ordre que celui d'origine. Je ne peux pas maintenant résoudre ce problème:

(defun negate (l) 
    (negate-aux l '())) 

(defun negate-aux (l A) 
    (cond 
    ((null l) (reverse A));or A 
    ((consp (car l)) (cons (negate (car l)) 
          (negate-aux (cdr l) A))) 
    (t (negate-aux (cdr l) (cons (* -1 (car l)) A)))))