How can I create a recursive function in LISP that counts the number of times an atom occurs in a nested list

Question

Just started learning lisp and I need to write a function, COUNTER, that would do as mentioned in the title. For example,

(COUNTER 'fizz '(fizz (buzz (fizz) (buzz fizz)) fizz))

should return 4

First try

I've written the following

(defun COUNTER (atom list)
  (cond
   ((null list) 0)
   ((equal atom (first list)) (+ 1 (COUNTER atom (rest list))))
   (t (COUNTER atom (rest list)))))

Which only counts the atom at the top most level (in the case of the example, my output is 2). What do I need to add to have it read the nested lists? I know I should be traversing the sublist and sum the results, but I'm not exactly sure which predicate I should be using and where exactly I should place it. I'm thinking right after

((equal atom (first list)) (+ 1 (COUNTER atom (rest list))))

Second try

I have tried the following to no avail

(defun COUNTER (target nest_list)
  (cond ((null nest_list) 0)
    (cond (atom (first nest_list) ((equal target (first nest_list)) (+ 1 (COUNTER target (rest nest_list)))))
      (t (COUNTER target (first nest_list))))
    (t (COUNTER target (rest nest_list)))))

I am receiving compilation errors from it. The logic to me seems to make sense. I'm testing to see whether the entity is an atom or a list, if atom, then see if it's equal and add 1, otherwise recur if it's a list. I'm not sure if I'm doing something wrong with the parenthesis placement or whether I'm allowed to use a cond within a cond like that.

Answer 1

You can close over a counter to avoid passing too many parameters. Also, you probably should pass a custom test function like CL functions do.

(defun counter (search tree &key (test #'eql))
  (let ((total 0))
    (labels
        ;; Our tree walker. Both counter and search are accessible
        ;; from the lexical environment, so there is no need to
        ;; pass them as arguments.
        ((walk (tree)
           (cond
             ;; First, see if current element matches the search.
             ;; That allows to search for a list inside a tree.
             ((funcall test tree search) (incf total))

             ;; Otherwise, if this is a cons-cell, recurse in CAR and CDR
             ((consp tree)
              (walk (car tree))
              (walk (cdr tree))))))

      ;; Initiate walk
      (walk tree)

      ;; Return total
      total)))

If this is a homework, I don't think this could satisfy your requirements (you are probably expected to provide a purely recursive function). However, if you understand the above, it should not be hard to build a recursive approach that never mutates variables.

For reference:

• LABELS: local, possibly recursive, functional bindings

• COND : generalized, cascading if

• LET : local variable bindings

• &KEY : named arguments in lambda lists

• INCF : increment place

• What's the difference between eq, eql, equal, and equalp in Common Lisp?

Example

(counter '(3 2)
         '(a b (c d 3) (3 2) e f)
         :test #'equalp)
=> 1

(counter 3 '(a b (c d 3) (3 2) e f))
=> 2

Answer 2

You also need to check whether first list is, itself, an atom or a list. If it's an atom, then your current logic is correct; if it's a list, then you also need to recur on this list.

I removed my comment about parameter names, since it's not a problem in most full-featured LISP versions. Thanks to coredump for the correction.

(defun COUNTER (target nest_list)
  (cond ((null nest_list) 0)
    (cond (atom (first nest_list))
      (equal target (first nest_list)) (+ 1 (COUNTER target (rest nest_list))))
      (t (COUNTER target (rest nest_list)))))

Now, in the else branch of the new cond, insert another recursion:

(COUNTER (target (first nest_list)))

You'll need to add this (instead of 1) to the count for (rest nest_list). Does this get you moving? I know I haven't been careful with my structure, but I'm trying to avoid doing the job for you.