Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Cons Cells

43 views
Skip to first unread message

Tim Bradshaw

unread,
Nov 27, 2002, 8:16:45 AM11/27/02
to
* A Melon wrote:
> 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.

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

Chris Gehlker

unread,
Nov 27, 2002, 8:56:40 AM11/27/02
to
On 11/27/02 3:20 AM, in article
1f39e7a690019cef...@melontraffickers.com, "A.Melon"
<ju...@melontraffickers.com> wrote:

> 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! =-----

Erik Naggum

unread,
Nov 27, 2002, 9:07:15 AM11/27/02
to
* A.Melon <ju...@melontraffickers.com>

| 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.

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.

John Gilson

unread,
Nov 27, 2002, 9:31:21 AM11/27/02
to
"A.Melon" <ju...@melontraffickers.com> wrote in message
news:1f39e7a690019cef...@melontraffickers.com...

> 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.
>
> 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))
>
> Thank you
> Jane

(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


0 new messages