CODEWITHSUNDEEP
listlispcommon-lisps-expression
darksky
darksky

Reputation: 21019

Lisp S-Expressions and Lists Length/Size

I am trying to write a function using Common Lisp functions only that will count how many s-expressions are in an s-expression. For example:

((x = y)(z = 1)) ;; returns 2

and

((x - y)) ;; returns 1

Nested expressions are possible so:

((if x then (x = y)(z = w))) ;; returns 3

I wrote a function which finds the length and it works if no nested expressions are there. It is:

(define (length exp)
  (cond
    ((null? exp) 0)
    (#t (+ 1 (length (cdr exp))))))

Now I modified this in an attempt to support nested expressions to the following:

(define (length exp)
  (cond
    ((null? exp) 0)
    ((list? (car exp)) (+ 1 (length (cdr exp))))
    (#t (length (cdr exp)))))

This works for expressions with no nests, but is always 1 less than the answer for nested expressions. This is because taking the example above, ((if x then (x = y)(z = w))), this will look at if at first and which satisfies the third condition, returning the cdr (the rest of the expression as a list) into length. The same happens up until (x=y) is reached, at which point a +1 is returned. This means that the expression (if x then .... ) has not been counted.

In what ways would I be able to account for it? Adding +2 will over-count un-nested expressions.

I will need this to work in one function as nesting can happen anywhere, so:

((x = y) (if y then (z = w)))

Upvotes: 2

Views: 2658

Answers (1)

huaiyuan
huaiyuan

Reputation: 26529

At first sight, your code only recurses to the right (cdr-side) and not to the left (car-side), so that definitely is a problem there.

On second sight, this is even a little bit more tricky than that, because you are not exactly counting conses; you need to differentiate the case where a cons starts a proper list vs where it's the cdr of a list. If you were to recurse to the car and cdr, that information would be lost. We need to iterate over the sexp as a proper list,

(defun count-proper-list (sexp)
  (cond ((atom sexp) 0)
        (t (1+ (reduce #'+ (mapcar #'count-proper-list sexp))))))

But this will also count the top level list, therefor always return one more than what you seem to want. So perhaps,

(defun count-proper-sublist (sexp)
  (1- (count-proper-list sexp)))

Upvotes: 2

Related Questions