Question: Common lisp workin with list

Question

Common lisp workin with list

Answers 1
Added at 2016-12-18 18:12
Tags
Question

my task is to count all element within a list, which have duplicates, eg ( 2 2 (3 3) 4 (3)) will result in 2 (because only 2 and 3 have duplicates) Searchdeep - just returns a nill if WHAT isn't find in list WHERE Count2 - go through the single elements and sub-lists

If it finds atom he will use SEARCHDEEP to figure out does it have duplicates, then list OUT will be checked (to make sure if this atom was not already counted (e.g. like ( 3 3 3), which should return 1, not 2) , increase counter and add atom to the OUT list.

However, i don't understand why, but it constantly returns only 1. I think it is some kind of logical mistake or wrong use of function.

My code is:

(SETQ OUT NIL)
(SETQ X (LIST  2 -3 (LIST 4 3 0 2) (LIST 4 -4) (LIST 2 (LIST 2 0 2))-5)) 
(SETQ count 0)
(DEFUN SEARCHDEEP (WHAT WHERE)    (COND
    ((NULL WHERE) NIL)
    (T (OR 
            (COND 
                ((ATOM (CAR WHERE)) (EQUAL WHAT (CAR WHERE)))
                (T (SEARCHDEEP WHAT  (CAR WHERE)))
            )
            (SEARCHDEEP WHAT (CDR WHERE))
        )
    )
)
)
(DEFUN Count2 ( input) 
(print input)
(COND
    ((NULL input) NIL)
    (T  
        (or
            (COND 
                ((ATOM (CAR input)) 
                            (COND 
                                (
                                    (and ;if
                                        (SEARCHDEEP (CAR INPUT) (CDR INPUT))
                                        (NOT (SEARCHDEEP (CAR INPUT) OUT))
                                    ) 
                                    (and ;do
                                        (Setq Count (+ count 1)) 
                                        (SETQ OUT (append OUT (LIST (CAR INPUT))))
                                        (Count2 (CDR input))
                                    )
                                )
                                (t (Count2 (CDR input)))
                            )
                )
                (T (Count2 (CAR input)))
            )
            (Count2 (CDR input))
        )
    )
)
)
(Count2 x)
(print count)
Answers
nr: #1 dodano: 2016-12-18 19:12

First, your code has some big style issues. Don't write in uppercase (some, like myself, like to write symbols in uppercase in comments and in text outside of code, but the code itself should be written in lowercase), and don't put parentheses on their own lines. So the SEARCHDEEP function should look more like

(defun search-deep (what where)
  (cond ((null where) nil)
        (t (or (cond ((atom (car where)) (equal what (car where)))
                     (t (searchdeep what (car where))))
               (searchdeep what (cdr where))))))

You also should not use SETQ to define variables. Use DEFPARAMETER or DEFVAR instead, although in this case you should not use global variables in the first place. You should name global variables with asterisks around the name (*X* instead of x, but use a more descriptive name).

For the problem itself, I would start by writing a function to traverse a tree.

(defun traverse-tree (function tree)
  "Traverse TREE, calling FUNCTION on every atom."
  (typecase tree
    (atom (funcall function tree))
    (list (dolist (item tree)
            (traverse-tree function item))))
  (values))

Notice that TYPECASE is more readable than COND in this case. You should also use the mapping or looping constructs provided by the language instead of writing recursive loops yourself. The (values) at the end says that the function will not return anything.

(let ((tree '(2 -3 (4 3 0 2) (4 -4) (2 (2 0 2)) -5)))
  (traverse-tree (lambda (item)
                   (format t "~a " item))
                 tree))
; 2 -3 4 3 0 2 4 -4 2 2 0 2 -5 
; No values

If you were traversing trees a lot, you could hide that function behind a DO-TREE macro

(defmacro do-tree ((var tree &optional result) &body body)
  `(progn (traverse-tree (lambda (,var)
                           ,@body)
                         ,tree)
          ,result))

(let ((tree '(2 -3 (4 3 0 2) (4 -4) (2 (2 0 2)) -5)))
  (do-tree (item tree)
    (format t "~a " item)))
; 2 -3 4 3 0 2 4 -4 2 2 0 2 -5 
;=> NIL

Using this, we can write a function that counts every element in the tree, returning an alist. I'll use a hash table to keep track of the counts. If you're only interested in counting numbers that will stay in a small range, you might want to use a vector instead.

(defun tree-count-elements (tree &key (test 'eql))
  "Count each item in TREE. Returns an alist in 
form ((item1 . count1) ... (itemn . countn))"
  (let ((table (make-hash-table :test test)))
    (do-tree (item tree)
      (incf (gethash item table 0)))
    (loop for value being the hash-value in table using (hash-key key)
          collect (cons key value))))

(let ((tree '(2 -3 (4 3 0 2) (4 -4) (2 (2 0 2)) -5)))
  (tree-count-elements tree))
;=> ((2 . 5) (-3 . 1) (4 . 2) (3 . 1) (0 . 2) (-4 . 1) (-5 . 1))

The function takes a keyword argument for the TEST to use with the hash table. For numbers or characters, EQL works.

Now you can use the standard COUNT-IF-function to count the elements that occur more than once.

(let ((tree '(2 -3 (4 3 0 2) (4 -4) (2 (2 0 2)) -5)))
  (count-if (lambda (item)
              (> item 1))
            (tree-count-elements tree)
            :key #'cdr))
;=> 3
Source Show
◀ Wstecz