* A.Melon <·····@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.