Comprobación recursiva de átomos en una lista

Question

Estoy intentando escribir un pequeño programa recursivo que prueba una lista y devuelve t si cada elemento es un átomo. El problema que tengo es que cuando la función recibe una lista vacía, devuelve t en lugar del resultado deseado de nil. No puedo encontrar una forma de que devuelva nil para una lista inicialmente vacía y todavía funcione correctamente de forma recursiva.

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

Answer 1

La función puede implementarse sin recursión utilizando, por ejemplo every, como en:

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

Cuando se trata de su problema indicado que la función devuelve T en lugar del resultado deseado de NIL cuando la función es llamada con una lista vacía:

1. Su recursiva la implementación devuelve explícitamente T si (null in) es verdadero, lo que explica su hallazgo. Simplemente cámbielo al valor deseado NIL. Considere cambiar la construcción if a and.

2. Solo realice la llamada recursiva cuando la lista tenga más de un elemento. Una prueba bien colocada para (rest in) servirá. Proporcione un valor verdadero en lugar de hacer la llamada recursiva si la lista está en su último elemento.

3. Busque con cuidado la llamada only-atoms para asegurarse de que la función puede ser recursiva.

Por ejemplo:

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

Answer 2

Usted puede dividir su función en dos, y proporcionar la selección inicial nil antes de entrar en la recursividad. El código siguiente es una manera de hacerlo (He intentado mantener lo más cerca posible código proporcionado como sea posible):

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

Ésta es también una buena oportunidad para hacer su función de cola recursiva:

(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

uso COND, lo que le permite probar varios casos:

• lista vacía -> nil
• una lista de elementos -> átomo? ; sugerencia: no use LENGTH
• else -> atom? para el primer elemento y llamada recursiva para elementos de apoyo

Answer 4

Esta solución funciona correctamente:

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

Sin embargo, una solución mucho más elegante (sin recursividad) sería:

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

Answer 5

La lista vacía qué cumplir con la condición de que cada elemento es un átomo! Su requisito de que debe contener al menos un elemento es un requisito adicional.

La forma más sencilla de expresar "cada elemento de la lista es un átomo" es (every #'atom list). Puede combinarlo con su requisito adicional con and.

Si insiste en hacerlo de forma recursiva en SICP de estilo, separar sus requisitos:

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