If something is a cons, add one to the sum of counts of the cons cells
in its car and cdr, otherwise there are no cons cells.
--tim
> How can I create a function in Lisp to count the number of cons cells that a
> list is using? For
> example, (num-cons-cells '(1 2 (3 (4 5)) 6)) => 8.
>
(defun num-cons-cells (lst)
(if (null lst)
0
(if (consp (first lst))
(+ (num-cons-cells (first lst)) (num-cons-cells (rest lst)) 1)
(+ (num-cons-cells (rest lst)) 1))))
> Also, how can I create another function to create an associative list mapping
> a symbol to the number
> of times it occurs. For example, (map '(a)) => ((a . 1))
Just a 'sec.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
That /list/ uses only 4 cons cells. The /tree/ uses 8 cons cells, however.
The difference between a list and a tree is evident in functions like
`copy-list´ and `copy-tree´.
The trivial count of cons cells in a list is obtained with the function
`length´, but if the list is circular, it will never return, which means
you may think you want the function `list-length´, but it returns `nil´
when the list is circular.
To count the number of cons cells used in a list, you need to set up an
`eq´ hashtable keyed on the cons cell and traverse the `cdr´ of each cons
cell you visit while you store the cons cell in the hashtable. When you
hit a `cdr´ that points to a cons cell already in the hashtable or is nil,
you need only count the number of elements in the hashtable. The
function `hash-table-count´ conveninently returns this number.
To count the number of cons cells used in a tree, you need to do the same
thing, except you now need to traverse both `car´ and `cdr´ of each cons
cell you visit. The termination condition is left as an exercise.
--
Erik Naggum, Oslo, Norway
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
(defun num-cons-cells (object)
(if (consp object)
(+ 1 (num-cons-cells (first object)) (num-cons-cells (rest object)))
0))
(defun occurrences (list &key (test #'eql))
(if (consp list)
(let (alist)
(labels ((occurrences-aux (object)
(cond ((null object))
((consp object)
(occurrences-aux (first object))
(occurrences-aux (rest object)))
(t
(let ((count (assoc object alist :test test)))
(if (null count)
(setf alist (acons object 1 alist))
(incf (rest count))))))))
(occurrences-aux (first list))
(occurrences-aux (rest list)))
alist)))
Regards,
jag