I am trying to teach myself Lisp by reading LISPCraft by Robert
Wilensky. Each chapter has exercises at the end, and I am stuck on one
of them. Sadly, it is at the end of chapter 2.
How do you construct the following list using only atoms and calls to
cons?
(a (b (x d)))
The closest I can get is:
(cons 'b '((x d)))
This creates the following:
(b (x d))
However, I cannot get the last surrounding list to work.
Hints, anyone?
I am using CLisp 3.0, from Sourceforge.net.
Thanks.
Chris
On 10 Jan 2003 21:38:49 -0800, ··········@yahoo.com (javacrypto)
wrote:
>I am trying to teach myself Lisp by reading LISPCraft by Robert
>Wilensky. Each chapter has exercises at the end, and I am stuck on one
>of them. Sadly, it is at the end of chapter 2.
>
>How do you construct the following list using only atoms and calls to
>cons?
>
>(a (b (x d)))
>
>The closest I can get is:
>
>(cons 'b '((x d)))
>
>This creates the following:
>
>(b (x d))
>
>However, I cannot get the last surrounding list to work.
>
>Hints, anyone?
(cons 'a (cons (cons 'b (cons (cons 'x (cons 'd nil)) nil)) nil))
But it's a fairly useless exercise, IMHO.
You should go on to more interesting and useful stuff.
> (cons 'a (cons (cons 'b (cons (cons 'x (cons 'd nil)) nil)) nil))
Thanks. I got an email suggesting this:
(cons 'a '(b (x d)))
which does not get the parens around the b atom.
And you are right. I am hoping to get to some more useful stuff.
Thanks for the help.
Chris
··········@yahoo.com (javacrypto) writes:
> > (cons 'a (cons (cons 'b (cons (cons 'x (cons 'd nil)) nil)) nil))
>
>
> Thanks. I got an email suggesting this:
>
> (cons 'a '(b (x d)))
aside from not having 'b' as a list it is not just
atoms and conses. Here are the steps to build (b (x d )) :
(cons 'd nil)
( cons 'x (cons 'd nil))
(cons ( cons 'x (cons 'd nil)) nil)
(cons 'b (cons ( cons 'x (cons 'd nil)) nil))
and if you want ((b) (x d))
(cons (cons 'b nil)(cons ( cons 'x (cons 'd nil)) nil))
I would suggest that you work a few of these out with
a paper and pencil all the while keeping in mind the definition
of a list as it is defined in CL. I would use the dotted pair
notation and start from the innermost expression and work out,
like this:
(d . nil)
( x . (d . nil) )
( ( x . (d . nil) ) . nil)
( b ( ( x . (d . nil) ) . nil) )
This is very important, if you do not understand how conses work
you will have very large problems using them to build useful things.
I am not saying do it until it is completely automatic, but to do it
to the point where you can sit down and correctly work through what
you need to do/build to get the desired result or see why your result
is wrong and then what you need to do to fix it. This will save you
time in learning lisp.
marc
Em Sat, 11 Jan 2003 18:29:06 -0200, Marc Spitzer escreveu:
> ··········@yahoo.com (javacrypto) writes:
>
> I would suggest that you work a few of these out with a paper and pencil
> all the while keeping in mind the definition of a list as it is defined
> in CL. I would use the dotted pair notation and start from the
> innermost expression and work out, like this: (d . nil)
> ( x . (d . nil) )
> ( ( x . (d . nil) ) . nil)
> ( b ( ( x . (d . nil) ) . nil) )
>
> This is very important, if you do not understand how conses work you
> will have very large problems using them to build useful things.
>
Touretzky's book has the best explanation for newbies on cons cells.
Work through all the excercises.
Common Lisp - A Gentle Introduction to Symbolic Computation
You can get the whole book for free (PDF or PS) on the Internet:
http://www-2.cs.cmu.edu/~dst/LispBook/
Cheers
Henry
··········@yahoo.com (javacrypto) wrote in message news:<····························@posting.google.com>...
> > (cons 'a (cons (cons 'b (cons (cons 'x (cons 'd nil)) nil)) nil))
>
>
> Thanks. I got an email suggesting this:
>
> (cons 'a '(b (x d)))
>
> which does not get the parens around the b atom.
Parens are just a notation; you should really try to avoid thinking of
this in terms of text manipulation, but as structural manipulation.
The earlier you can get around this, the better.
What may help you, in addition to the pattern matching and
substitution method I outlined in the other article, is drawing a
box-and-arrow structural diagram of cons cells which represents the
list (a (b (x d))). From a traversal of this graph, you can pull out
the nested CONS calls needed to build the list. Plus visualizing the
cells graphically is a useful exercise in itself. It's more useful to
understand and visualize the structure than to be able to mechanically
spit out a CONS-based expression to produce a given complex list.
[ a | ] }
\ } top level list, two cons cells holding A and (B
...)
[ | NIL ] }
/
[ b | ] }
\ } inner two-cell list, B and (X D)
[ | NIL ] }
/
[ x | ] }
\ } the list (X D)
[ d | NIL ] }
So now it's easy, start at the leaves of the tree and work towards the
root:
(cons 'd nil)
add the next level:
(cons 'x (cons 'd nil))
this becomes the left or CAR child of the next level:
(cons (cons 'x (cons 'd nil)) nil)
and so on.
From: Tim Bradshaw
Subject: Re: Help with Lisp exercise in book
Date:
Message-ID: <ey38yxr60sd.fsf@cley.com>
* javacrypto wrote:
> How do you construct the following list using only atoms and calls to
> cons?
> (a (b (x d)))
You don't, you write a program to do it for you:
(defun sexp->constructor (form)
;; fails to preserve eqness, and is simple-minded about printablness
(if (atom form)
`(quote ,form)
`(cons ,(sexp->constructor (car form))
,(sexp->constructor (cdr form)))))
> (pprint (sexp->constructor '(a . (b x (((d .e)))))))
(cons 'a
(cons 'b (cons 'x (cons (cons (cons (cons 'd (cons '.e 'nil)) 'nil) 'nil) 'nil))))
--tim
··········@yahoo.com (javacrypto) wrote in message news:<····························@posting.google.com>...
> I am trying to teach myself Lisp by reading LISPCraft by Robert
> Wilensky. Each chapter has exercises at the end, and I am stuck on one
> of them. Sadly, it is at the end of chapter 2.
>
> How do you construct the following list using only atoms and calls to
> cons?
>
> (a (b (x d)))
>
> The closest I can get is:
>
> (cons 'b '((x d)))
>
> This creates the following:
>
> (b (x d))
Hint: try the approach of repeatedly matching one of several patterns
and replacing it with a substitution, like this:
Pattern Substitution
'(X Y ...) (cons 'X '(Y ...))
'(X) (cons 'X NIL)
Keep matching and replacing until no more matches can be found. Pay
attention to the quotes; they are part of the pattern and must be
matched, and note that the whole list is quoted to begin with to start
the matching process.
The first match would therefore be this:
'(a (b (x d)))
^^^^^^^^^^^^^^
where X is identified with a, and Y is identified with (b (x d)), so
the substitution is:
(cons 'a '((b (x d))))
^^^^^^^^^^^^
I have underlined the next place where a pattern matches. It maches
the second pattern, '(X), where X is identified as (b (x d)). The
replacement therefore produces (cons 'X nil), or (cons '(b (x d))
nil):
(cons 'a (cons '(b (x d)) nil))
^^^^^^^^^^
Your next pattern match is here. It's pretty obvious by now how to
continue substituting until you run out of matches.
So you can see, it's really a syntax-directed language translation
task: you are matching a pair of grammar rules against a sentence, and
then reducing each rule by producing a translation. You are basically
doing the actions of a list-literal-notation to
cons-construction-notation compiler by hand.