Re: cons and list behaviour


Kenny Tilton wrote:
Jason wrote:
Please excuse me if this has been addressed before. I searched the
recent posts and the FAQ and did not see find the answer I am seeking.

I am learnin LISP (actually elisp ;)), and have written the following:

;; here I am using cons notation
(setq node-1 (cons 'a 'b))
(setq node-2 (cons 'c 'd))
(setq node-3 (cons 'e node-1))
(setq node-4 (cons node-3 'f))
(setq node-5 (cons node-2 'g))
(setq tree (cons node-4 node-5))
;; (((e a . b) . f) (c . d) . g) <<<<< value

;; here we can see that a cons is *not* the same as a list
(setq tree2 (copy-tree tree)) ;; <<<<<<<<<<<< works fine
(setq tree3 (copy-sequence tree)) ;; <<<<<<<< generates an error!

It looks as if elisp's copy-sequence is like the CL copy-seq: it wants a
proper list, not just any list.

Well, that is what CLHS says:

"17.3.2 copy-seq Function
Syntax: copy-seq sequence copied-sequence

Arguments and Values:
sequence - a proper sequence.
copied-sequence - a proper sequence. "

But AllegroCL does not mind:

(copy-seq '(((e a . b) . f) (c . d) . g))
-> (((e a . b) . f) (c . d) . g)

I just would not bet on that being portable or even working in the
future. Anyway....





;; now I am redefing the above using list notation
(setq node-1 (list 'a 'b))
(setq node-2 (list 'c 'd))
(setq node-3 (list 'e node-1))
(setq node-4 (list node-3 'f))
(setq node-5 (list node-2 'g))
(setq tree (list node-4 node-5))
;; (((e (a b)) f) ((c d) g)) <<<<< value

;; however, here we see that a list *is* the same as a cons!

Hmmm, where do see that? I see a big difference between these two lines:
> ;; (((e a . b) . f) (c . d) . g) <<<<< value
> ;; (((e (a b)) f) ((c d) g)) <<<<< value

Those dots (full stops) mean a lot. they are the Lisp printer trying to
tell you that the cdr of a cons is not another cons.

(setq tree2 (copy-tree tree)) ;; <<<<<<<<<<<< works fine
(setq tree3 (copy-sequence tree)) ;; <<<<<<<< also works fine!

It seems that the list notation works well with the cons notation, but
the reverse is not the case. I am wondering why is this? Also, if a
list is a cons, but a cons is not a list, then why do we have cons?

Start over on this subject, which I encourage you to master fully before
getting into any interesting Lisp programming. Try to find one of those
references that has fancy diagrams showing cons cells as two little
squares, one for the car one for the cdr. Go slow and make sure you get
what is going on. Focus on CONS (the function) first, then understand
LIST as a function calling CONS to do its job.

The quick intro is that cons is a function that might have been called
MAKE-CONS but was not. It takes two arguments and produces a data
structure known as a cons. This data structure has two attributes known
as the CAR and the CDR. There are functions of the same name (CAR and
CDR) that take a CONS as an argument and return what you would hope they
would return. <g>

So far, so simple, and notive that I have not said anything about lists.
There is no such thing as a list, really. It is an abstraction over NIL
and conses.

The /function/ LIST takes any number of arguments and calls CONS to
generate enough cons data structures to hold them all:

(list 1 2 3) -> (cons 1 (cons 2 (cons 3 nil)))

Likewise:

(list 'a 'b) -> (cons 'a (cons 'b nil)), /not/ (cons 'a 'b)

Like I said, find a good reference that goes into this in detail and
work any exercises until you can think in CONSese. You will really need
this as you start writing sometimes even simple Lisp code.

hth, kenny

Thanks, Kenny. I'm working through "ANSI Common Lisp" by Paul Graham.
He's using those boxes and such to describe conses and lists. I'm
having a lot of fun since I've got clisp running in a terminal, and
elisp running in emacs, and the commands are not always the same. :(

Cons threw me for a loop, since I've never known a language to be built
around such a concept before. The closest I've experieced is TCL, where
the command is the basic unit, and everything is arranged around that.
When I saw cons used in examples, then list used, and the output seemed
similar, I did not immediately realise how important the change in
subject was!

I'm sure I'll have a lot more questions. I'll come back here with 'em
when I do. :)

-Jason

.

Relevant Pages

  • Re: When CANNOT use first/rest in place of car/cdr?
    ... >> to run ancient LISP code? ... a cons cell has no REST; ... I use CAR/CDR to emphasize the view as a cons qua cons. ... I think a belief that all conses are lists, that is, that ...
    (comp.lang.lisp)
  • Re: Equality, Assignment and The Emperors New Clothes
    ... In the case of copy-cons, only one new cons is allocated. ... In the case of copy-tree, a new cons for all the conses of the tree ... show lists: ... don't clone the class of account, neither the classes of account or of ...
    (comp.lang.scheme)
  • Re: delete command weirdness
    ... A appears only in the car of the first cons). ... Now delete is forced to do some work, and makes the cdr of the first ... always just (setq testing (remove 'a testing)). ... If you've got lists millions of items long, ...
    (comp.lang.lisp)
  • Re: When is Xah going to ease up on Emacs...
    ... One part of the cons problem in lisp is that it forces programer to ... extracts the leafs of a tree. ... has abstracted low-level access to lists with functions, e.g. get-children, ...
    (comp.lang.lisp)
  • Re: Why cons *pairs*?
    ... architecture when he designed Lisp. ... It seems to me the main idea was to use lists (characterised as a head ... forms of list processing based on what Schemers ... cons cells are usually two words. ...
    (comp.lang.scheme)