Recherche récursive des atomes dans une liste

Question

Je tente d'écrire un petit programme récursif qui teste une liste et renvoie t si chaque élément est un atome. Le problème que j'ai est que lorsque la fonction reçoit une liste vide, il renvoie t au lieu du résultat souhaité de nul. Je ne peux pas trouver un moyen de l'obtenir nul pour une liste initialement vide et encore fonctionner correctement d'une manière récursive.

(defun only-atoms (in) 
    (if (null in) 
    t 
    (and (atom (first in)) (only-atoms (cdr in))) 
) 
) 

Answer 1

La fonction peut être mis en œuvre sans récursion en utilisant par exemple every, comme dans:

(defun only-atoms (list) 
    (and list (every #'atom list))) 

Quand il vient à votre problème déclaré que la fonction retourne T au lieu du résultat souhaité de NIL lorsque la fonction est appelée avec une liste vide:

1. Votre récursive La mise en œuvre renvoie explicitement T si (null in) est vrai, ce qui explique votre conclusion. Il suffit de le changer à la valeur désirée NIL. Envisagez de remplacer la construction if par and.

2. uniquement l'appel récursif lorsque la liste a plus d'un élément. Un test bien placé pour (rest in) fera l'affaire. Fournir une valeur réelle au lieu de faire l'appel récursif si la liste est à son dernier élément.

3. Recherchez avec soin l'appel only-atoms pour vous assurer que la fonction peut être récursive.

Par exemple:

(defun only-atoms (list) 
     (and list 
      (atom (first list)) 
      (or (null (rest list)) 
       (only-atoms (rest list))))) 

Answer 2

Vous pouvez diviser votre fonction en deux, et de fournir la projection nil initiale avant d'entrer récursivité. Le code suivant est une façon de le faire (j'ai essayé de le garder aussi près de code fourni que possible):

(defun only-atoms (in) 
    (defun only-atoms-iter (in) 
    (if (null in) 
     t 
     (and (atom (first in)) (only-atoms-iter (cdr in))))) 

    (unless (null in) 
     (only-atoms-iter in))) 

Ceci est aussi une bonne occasion de faire votre récursive de queue de fonction:

(defun only-atoms (in) 
    (defun only-atoms-iter (in state) 
    (if (null in) 
     state 
     (only-atoms-iter (cdr in) (and state (atom (first in)))))) 

    (unless (null in) 
     (only-atoms-iter in t))) 

Answer 3

Utilisez COND, qui vous permet de tester plusieurs cas:

• liste vide -> nil
• une liste d'éléments -> atome? ; indice: ne pas utiliser LONGUEUR
• autre -> atome? pour le premier élément et appel récursif pour les éléments de repos

Answer 4

Cette solution fonctionne correctement:

(defun lat-p (lst) 
      (labels ((lat-p* (lst) 
         (cond 
         ((null lst) t) 
         ((atom (car lst)) (lat-p* (cdr lst))) 
         (t nil)))) 
      (if lst 
       (lat-p* lst) 
       nil))) 

Cependant, une solution beaucoup plus élégante (sans récursivité) serait:

(defun lat-p (lst) 
      (and lst (every #'atom lst))) 

Answer 5

La liste vide ne remplir la condition que chaque élément est un atome! Votre exigence selon laquelle il doit contenir au moins un élément est une exigence supplémentaire.

La manière la plus simple d'exprimer "chaque élément de la liste est un atome" est (every #'atom list). Vous pouvez le combiner avec votre exigence supplémentaire avec and.

Si vous insistez pour le faire récursivement dans un style SICP, séparez vos besoins:

(defun not-empty-and-all-atoms (list) 
    (and list 
     (all-atoms list))) 

(defun all-atoms (list) 
    (if (endp list) 
     t 
     (and (atom (first list)) 
      (all-atoms (rest list)))))