CODEWITHSUNDEEP
recursioncommon-lisp
Bort
Bort

Reputation: 835

Recursively check for atoms in a list

I am attempting to write a small recursive program that tests a list and returns t if every element is an atom. The problem I am having is that when the function receives an empty list, it returns t instead of the desired result of nil. I cannot come up with a way to have it return nil for an initially empty list and still function properly in a recursive manner.

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

Upvotes: 5

Views: 2391

Answers (5)

Svante
Svante

Reputation: 51501

The empty list does fulfill the condition that every element is an atom! Your requirement that it should contain at least one element is an additional requirement.

The simplest way to express "every element of the list is an atom" is (every #'atom list). You can combine it with your additional requirement with and.

If you insist on doing it recursively in SICP-style, separate your requirements:

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

Upvotes: 1

Terje Norderhaug
Terje Norderhaug

Reputation: 3689

The function can be implemented without recursion using e.g. every, as in:

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

When it comes to your stated problem that the function returns T instead of the desired result of NIL when the function is called with an empty list:

  1. Your recursive implementation explicitly returns T if (null in) is true, which explains your finding. Simply change it to the desired value NIL. Consider changing the if construct to and.

  2. Only make the recursive call when the list has more than one item. A well placed test for (rest in) will do. Provide a true value instead of making the recursive call if the list is at its last item.

  3. Carefully locate the only-atoms call to ensure that the function can be tail-recursive.

For example:

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

Upvotes: 2

Bozhidar Batsov
Bozhidar Batsov

Reputation: 56595

This solution works correctly:

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

However a much more elegant solution(with no recursion) would be:

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

Upvotes: 0

Rainer Joswig
Rainer Joswig

Reputation: 139261

Use COND, which allows you to test for several cases:

  • empty list -> nil
  • one element list -> atom? ; hint: don't use LENGTH
  • else -> atom? for first element and recursive call for rest elements

Upvotes: 1

vhallac
vhallac

Reputation: 13907

You can split your function in two, and provide the initial nil screening before you enter recursion. The following code is one way to do so (I tried to keep it as close to provided code as 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)))

This is also a good opportunity to make your function tail recursive:

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

Upvotes: -1

Related Questions