CODEWITHSUNDEEP
mathlispcommon-lisp
Aditya Nishtala
Aditya Nishtala

Reputation: 23

Counter variable in LISP

Define the function 'occ' that takes a list L and a symbol A and counts the occurance of symbol A in L. Example: (occ '(((s) o ) d) 'f) --> 0

What i have gotten so far:

(defun occ(list a)
(setq counter 0)
  ;Checks if the given list is has an nested list
  (if (consp list)
    ; Breaking the list down atom by atom and recursing
    (or (occ a (car list))
        (occ a (cdr list)))
    ; checks if symbols are the same
    (if(eq a list)
        (setq counter(1+ counter)))))

However My output keep saying Nil instead of displaying the counter value. I cannot use any higher-functions of LISP.

Upvotes: 1

Views: 2434

Answers (2)

sheikh_anton
sheikh_anton

Reputation: 3452

First of all, don't use setq for variable initialization inside yout function, use let. Second, let's look why you doing it wrong, your code:

(defun occ(list a)
(setq counter 0) ;; You always setting counter to 0 on new
                 ;; level of recursion
  (if (consp list)
   (or (occ a (car list))  ;; You reversed arguments order?
        (occ a (cdr list))) ;; according to your definition it must be
                            ;; (occ (car list) a)
    (if(eq a list)
        (setq counter(1+ counter)))))

Anyway, you don't need any counter variables to do what you want.

Right function may look like this (i changed arguments order becaus it looks better for me to find SYMBOL in LIST):

(defun occ (sym nested-list)
  (cond
    ((consp nested-list)
     (+ (occ sym (car nested-list)) (occ sym (cdr nested-list))))
    ((eq sym nested-list) 1)
    (t 0)))

CL-USER> (occ 'x '(((s) o ((f ()) f)) d))
0

CL-USER> (occ 'f '(((s) o ((f (x (((f))))) f)) d f))
4

Upvotes: 6

Sylwester
Sylwester

Reputation: 48745

If you feed your definition to SBCL: 

; in: DEFUN OCC
;     (SETQ COUNTER 0)
; 
; caught WARNING:
;   undefined variable: COUNTER
; 
; compilation unit finished
;   Undefined variable:
;     COUNTER
;   caught 1 WARNING condition

So you are modifying a global undefined variable counter. When do the function return? Well, or will return the very first non nil return from recursion with car or cdr. What returns values? Well when it's not a cons it will evaluate to the intermediate value of a incf of counter when the symbol matches or nil when it doesn't.

Try doing it like this:

(defun occ (list a &optional (counter 0))
  (cond ((equal list a) (1+ counter))
        ((atom list) counter)
        (t (occ (cdr list)
                a
                (occ (car list)
                   a
                   counter)))))

counter is an optional accumulator that you use to hold the values. Since it's passed it isn't shared between the recursive calls but replaced with the updated value at each call making it functional and easy to follow. When you need to search both car and cdr you recurse car with the counter of this stage and the returning value will be used as the counter in the cdr. For lists of atom this will be tail recursive if the implementation supports it. This supports finding symbols as tails of lists. eg. (occ '((x . x) . x) 'x) ; ==> 3 If you are sure you have no dotted list (every list is nil terminated) you can use the loop macro:

(defun occ (list a)
  (loop :for e :in list 
        :counting (equal e a) :into count
        :if (consp e)
            :summing (occ e a) :into sum
        :finally  (return (+ count sum))))

;; tests
(occ '(x (x x (x (x ) x)) y z) 'y) ; ==> 1
(occ '(x (x x (x (x ) x)) y z) 'x) ; ==> 6
(occ '((x . x) . x) 'x) ; ERROR like "A proper list must not end with X".

Upvotes: 1

Related Questions