Count atoms in a list structure

Question

I need to find how many elements a given input has. the input can be a list or a symbol, for example:

• 'a => 1 element
• '(3 . 4) => 2 elements
• '(a b . c) => 3 elements
• '((a b . c) 3 . 4) => 5 elements

one problem is that when I'm going through the input, every element can be a list of its own, or a pair (just started learning scheme, so my tools for right now are mainly car/cdr), so, when should I stop my loop? when if (null? x) condition is true? or maybe when if (null? (car x)) is true?

Answer 1

The title of your question should be changes to how to count atoms in a list structure. There are numerous questions on SE about it. Here is how:

1. if element is a pair, the result would be the sum of the car and the cdr applied to the same procedure.
2. else the length is 1

EDIT

Here's the above algorithm as code:

(define (count-all-atoms x)
  (if (pair? x)
      (+ (count-all-atoms (car x))
         (count-all-atoms (cdr x)))
      1))

To comment the comments I've got there are actually 2 more ways to implement this and all of them will give the correct answer to OP's examples. It all has to do with how we interpret () to be.

Depending on '(()) should be counted as 0, 1 or 2 elements. Zero since it's all lists without any atoms, 1 since its one list with one null element (not counting null terminator) or 2 since it's the same as a dotted pair with two null elements ((() ())). It's the last one that my text described, but here are the two other ways:

;; count (()) and () as 0
;; no nil value is counted as it is a list without elements
(define (count-non-nil-atoms x)
  (if (pair? x) 
      (+ (count-non-nil-atoms (car x)) 
         (count-non-nil-atoms (cdr x)))
      (if (null? x)
          0 
          1)))

;; count (()) as 1 and () as 0
;; ie. count only nil as atom in car position but not as a list terminator
;; probably most common
(define (count-atoms x)
  (if (pair? x)
      (let ((a (car x)) (d (cdr x)))        
        (+  (if (null? a) 1 (count-atoms a))
            (count-atoms d)))
      (if (null? x) 0 1)))

Answer 2

In Common Lisp, an atom is anything that isn't a pair, and you can check whether something is an atom with the atom function. If something is not an atom, then it's a pair, which means that you can call car and cdr with it to retrieve the parts of the pair. A simple solution to this, then, is simply:

(defun count-atoms (object)
  (if (atom object) 1
      (+ (count-atoms (car object))
         (count-atoms (cdr object)))))

Note that this counts the nil terminator of a proper list, so

(a b . c)   ;=> 3
(a b . nil) ;=> 3, even though (a b . nil) == (a b)

but this seems to be in line with your description of counting atoms, rather than elements in a list. This implementation does consume stack space, though, so you might have problems with very large structures. You might use a continuation passing approach instead that a Lisp implementation that supports tail call optimization could do with constant stack space:

(defun count-atoms (object)
  (labels ((kount (object k)
             (if (atom object)
                 (funcall k 1)
                 (kount (car object)
                        (lambda (l)
                          (kount (cdr object)
                                 (lambda (r)
                                   (funcall k (+ l r)))))))))
    (kount object 'identity)))

That continuation passing style avoids using lots of stack space (if the implementation optimizes tail calls), but its not all that transparent (unless you're very accustomed to that style). We can use an explicit stack and a loop to get something that's much more likely to use constant stack space:

(defun count-atoms (object)
  (do ((objects (list object)) (natoms 0))
      ((endp objects) natoms)
    (let ((object (pop objects)))
      (cond
        ((atom object) (incf natoms))
        (t (push (car object) objects)
           (push (cdr object) objects))))))

Now that we have it as a do loop, it's easy to see how we might write it using tail recursion (what you'd probably do if you were working in Scheme):

(defun count-atoms (object)
  (labels ((kount (objects natoms)
             (cond
               ((endp objects)
                natoms)
               ((atom (first objects))
                (kount (rest objects) (1+ natoms)))
               (t 
                (kount (list* (car (first objects))
                              (cdr (first objects))
                              (rest objects))
                       natoms)))))
    (kount (list object) 0)))