From ... Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!uio.no!nntp.uio.no!ifi.uio.no!not-for-mail From: Erik Naggum Newsgroups: comp.lang.lisp Subject: Re: Cons Cells Date: 27 Nov 2002 14:07:15 +0000 Organization: Naggum Software, Oslo, Norway Lines: 30 Message-ID: <3247394835670439@naggum.no> References: <1f39e7a690019ceff6bb4c47605e4f11@melontraffickers.com> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Trace: maud.ifi.uio.no 1038406036 16721 129.240.65.5 (27 Nov 2002 14:07:16 GMT) X-Complaints-To: abuse@ifi.uio.no NNTP-Posting-Date: 27 Nov 2002 14:07:16 GMT Mail-Copies-To: never User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 Xref: archiver1.google.com comp.lang.lisp:47656 * 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.