Subject: Re: Ansi Common Lisp chapter 3 exercise 6
From: rpw3@rpw3.org (Rob Warnock)
Date: Thu, 26 Oct 2006 23:24:00 -0500
Newsgroups: comp.lang.lisp
Message-ID: <O4Gdnajpl_F9FNzYnZ2dnUVZ_rWdnZ2d@speakeasy.net>
Erick Lopez Carreon <erick@fsl.org.mx> wrote:
+---------------
| And complemented with KT response pointing i'm misunderstanding the
| normal cons (and list) let me reach the following points:
| - cons: Is a pair of pointers.
| cons:
| [a|nil] or [a|b] or [a| ] -> [b|nil]
+---------------

If you think that's an exhaustive partition of CONS then you're
still misunderstanding it a little (though maybe less than before).
Common Lisp CONS is *not* restricted to those three cases. *Both*
the CAR & CDR can point to other conses, which is how you get general
binary trees from CONS cells, as well as even more complex structures.
So in addition to the ones you've shown, you need to add this case,
and an infinity of similar ones:

  Start
    |
    |  +-------------------------------------------------+
    |  |                                                 |
    v  v                                                 |
    +---+   +---+   +---+   +---+                        |
    |*|*+-->|*|*|-->|*|*|-->|*|*|-->XYZ                  |
    ++--+   ++--+   ++--+   ++--+                        |
     |       |       |       |                           |
     |       |       |       v                           |
     |       |       |     +---+   +---+                 |
     |       |       |     |*|*+-->|*|*|-->#(17 35 26)   |
     |       |       |     ++--+   ++--+                 |
     |       |       |      |       |                    |
     |       |       |      v       v                    |
     |       |       v     789     "hello"               |
     |       |     +---+                                 |
     |       |     |*|*+-->"Bar"                         |
     |       |     ++--+                                 |
     |       |      |                                    |
     |       |      +------------------------------------+
     |       v
     |     +---+
     |     |*|*+-->FOO
     |     ++--+
     |      |
     |      v
     |    "qkwj"
     v
    +---+   +---+
    |*|*+-->|*|*+-->"bletch"
    ++--+   ++--+
     |       |
     v       v
    853    +---+
           |*|*+-->FOO
           ++--+
            |
	    v
	  191.25

Note: If you actually built that and printed it (with *PRINT-CIRCLE*
non-NIL, of course), it would print like this (I *think*, if I
haven't made a silly mistake somewhere):

    #1=((853 (191.25 . FOO) . "bletch") ("qkwj" . FOO) (#1# . "Bar")
	(789 "hello" . #(17 35 26)) . XYZ)

+---------------
| My first error was made the assumption that all the cons
| must end with nil...
+---------------

The other false assumption referred to above is that the CAR
of a cons is not itself a CONS. It can be. [Though you indirectly
show that you already know that at some level by describing
(CL-LIST->GOV-LIST '(a b c)) as (((NIL . c) . b ) . a).]

+---------------
| - With cons i can construct lists, pairs and mixed lists
|   (proper lists or dotted lists)
+---------------

And much, much more than that: arbitrary binary trees,
as well as general directed graphs of nodes with two
or fewer outgoing edges [a.k.a. binary directed graphs].


-Rob

p.s. Bonus problem: Write a function GRAPH-REVERSE that will
reverse the CAR & CDR of each cons cell in an arbitrary binary
directed graph -- *including* those with self-referential
or circular structure (as above) -- and return the resulting
"mirror" graph.

Bonus problem#2: Given such a GRAPH-REVERSE, does this suffice
for a definition of CL-LIST->GOV-LIST? If not, why not?

    (defun cl-list->gov-list (list)
      (graph-reverse list))

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607