Subject: Re: Cons Cells
From: Erik Naggum <>
Date: 27 Nov 2002 14:07:15 +0000
Newsgroups: comp.lang.lisp
Message-ID: <>

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