CODEWITHSUNDEEP
listrecursioncommon-lisp
IsaacS
IsaacS

Reputation: 3611

Returned list is redundant after recursion

I'm new to Lisp and I have a problem when appending a list to an existing list.

(Funcion spec) The following function takes 2 args; an atom and a list. The list takes 2-dimensional form where each sub-list looks like (index counter) (both index and counter are atoms). If target is equal to one of the indexes, counter increments. If no sub-list contains target, add a new sub-list with counter = 1.

(defun contained (target list)
  (cond ((null list) (list target 1))
    ((= (car (car list)) target)
     (setf (cadr (car list))
           (+ (cadr (car list)) 1)))
    (t (push (contained target (cdr list)) list))))

The problem is when target doesn't exist yet. As shown below, lists and parentheses get redundant.

> la
((1 4) (2 1))
> (contained 3 la)
(((3 1) (2 1)) (1 4) (2 1))

What I want is something like:

((3 1) (1 4) (2 1))

Sorry not to have been able to simplify the problem, but thanks.

Upvotes: 0

Views: 120

Answers (1)

Doug Currie
Doug Currie

Reputation: 41170

(defun contained (target list)
  (cond
    ((null list) (list target 1)) ; you are returning a new element of target

    ((= (car (car list)) target)
     (setf (cadr (car list))
           (+ (cadr (car list)) 1))) ; you are returning... what?

    ;; yet you are pushing on every recursive call!
    (t (push (contained target (cdr list)) list))))

At the risk of doing your homework for you, here's one way to do it (with help from Miron Brezuleanu):

(defun contained (target list)
    (let ((elm (assoc target list)))
        (if elm 
            (progn (incf (cadr elm)) list)
            (cons (list target 1) list))))

Here's a way to do it closer to your original

(defun contained (target list)
  (cond
    ((null list) (list (list target 1)))
    ((= (car (car list)) target)
     (setf (cadr (car list))
           (+ (cadr (car list)) 1))
     list)
    (t (setf (cdr list) (contained target (cdr list)))
       list)))

Upvotes: 2

Related Questions