Subject: Re: Cons Cells From: Erik Naggum <erik@naggum.no> Date: 27 Nov 2002 14:07:15 +0000 Newsgroups: comp.lang.lisp Message-ID: <3247394835670439@naggum.no> * A.Melon <juicy@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.