From: ·····@orsi.com
Subject: Self Study Question (mapcar) NOT HOMEWORK!
Date:
Message-ID: <876928568.10844@dejanews.com>
I was leafing through ANSI CL by Paul Graham, when I came upon this
exercise. Write a function pos+ that takes a list of numbers and returns
a list of numbers plus their position in the list
(pos+ '(1 2 3 4)) => (1 3 5 7)
(1+0 = 1, 2+1 = 3, 3+2=5, 4+3=7)
a condition on the exercise is to use mapcar. It is possible to use
(mapcar #'+ l (enumerated-interval 0 (- n 1)), but I did not
want to create so much garbage.
(enumerated-interval a b)is a procedure that could easily be defined. It
returns a list from a to b, inclusive.
This is my solution
(defun pos+ (l)
"Create a new list consisting of each number added to its position.
Does no error checking, but l should consist entirely of numbers"
;; this works. But is it kosher?
(let ((counter 0))
(mapcar
#'(lambda (x) (prog1 (+ x counter)
(incf counter)))
l)))
This is my question:
1) Is it possible to do this without using a setf?
2) Is this a reasonable way to do this exercise. (the prog1 and the incf
bother me a bit)
3) I think it might take a bit of experience to see a solution like this.
Is there a way that is more transparent?
4) Which solution do you think Graham intended?
Note that internal defuns and labels are not allowed for this exercise.
Opinions and criticisms are welcome - I've got my flameproof jacket on.
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
From: Ken Tilton
Subject: Re: Self Study Question (mapcar) NOT HOMEWORK!
Date:
Message-ID: <34450B7D.227F@bway.net>
·····@orsi.com wrote:
>
> This is my solution
>
> (defun pos+ (l)
> "Create a new list consisting of each number added to its position.
> Does no error checking, but l should consist entirely of numbers"
> ;; this works. But is it kosher?
> (let ((counter 0))
> (mapcar
> #'(lambda (x) (prog1 (+ x counter)
> (incf counter)))
> l)))
>
> This is my question:
>
> 1) Is it possible to do this without using a setf?
(defun pos+ (numbers)
(mapcar #'(lambda (number)
(+ number (position number numbers))) numbers))
Not too good if you allow duplicates in the list. <g>
(defun pos+ (numbers)
(maplist #'(lambda (remaining)
(+ (car remaining) (- (length numbers) (length
remaining))))
numbers))
Uh-oh. He said #'mapcar. <g>
> 2) Is this a reasonable way to do this exercise. (the prog1 and the incf
> bother me a bit)
Your solution was the first that popped into my mind. Start at -1 to
avoid the prog1 <g>, and in general I have learned not to be squeamish
about being locally "impure".
> 3) I think it might take a bit of experience to see a solution like this.
> Is there a way that is more transparent?
I agree most neophytes would not realize they could muck with counter
(something outside the lambda) and spend the excess CPU of repeatedly
calling #'position (perhaps not thinking to worry about duplicates).
Then again, neophytes might not worry about consings as you did.
> 4) Which solution do you think Graham intended?
>
I bet he just wanted readers to wrestle with #'mapcar vs iteration vs
recursion to make sure they were aware of the different tools they could
apply to a given problem, and had no solution in mind. Which would he
write? May be yours but using #'1+.
In article <···············@dejanews.com>, <·····@orsi.com> wrote:
>3) I think it might take a bit of experience to see a solution like this.
> Is there a way that is more transparent?
I think it was intended that you would have to think hard to solve this
exercise. The normal way to compute that result would *not* use MAPCAR.
A solution using DO or LOOP would be much clearer. This is why the
exercise had to require you to use MAPCAR.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.
From: Ann Fok
Subject: Re: Self Study Question (mapcar) NOT HOMEWORK!
Date:
Message-ID: <34470CFA.6618@isu.edu>
Hi,
I looked at one of the question on POS+ (which takes a list and return
a list of each element plus its position)
Such that:
(pos+ '(8 7 6 6))
(8 8 8 9)
I tried to write a function by using recursion instead of iteration for
it. However, somehow, I just could get it work at all! If any people
here can do that, just let me know, I 'll appreciate!
Thanks,
From: Philip Lijnzaad
Subject: Re: Self Study Question (mapcar) NOT HOMEWORK!
Date:
Message-ID: <u7k9fc683f.fsf@o2-4.ebi.ac.uk>
Ann Fok <·····@isu.edu> writes:
>
> Hi,
>
> I looked at one of the question on POS+ (which takes a list and return
> a list of each element plus its position)
>
> Such that:
> (pos+ '(8 7 6 6))
>
> (8 8 8 9)
> NOT HOMEWORK!
OK, I believe you. Try:
(defun pos+ (l)
(pos2 l 0))
(defun pos2 (l n)
(if (null l)
nil
(cons (+ (car l) n) (pos2 (cdr l) (1+ n)))))
All the work is done by pos2, which gets an extra argument n to keep the
track of how far down the list we are. With the same trick you can make
some recursive functions tail-recursive (see SICP's treatment of the
factorial function).
Philip
--
Philip Lijnzaad, ········@ebi.ac.uk | European Bioinformatics Institute
+44 (0)1223 49 4639 | Wellcome Trust Genome Campus, Hinxton
+44 (0)1223 49 4468 (fax) | Cambridge CB10 1SD, GREAT BRITAIN
PGP fingerprint: E1 03 BF 80 94 61 B6 FC 50 3D 1F 64 40 75 FB 53
Philip Lijnzaad <········@ebi.ac.uk> writes:
> (defun pos+ (l)
> (pos2 l 0))
>
> (defun pos2 (l n)
> (if (null l)
> nil
> (cons (+ (car l) n) (pos2 (cdr l) (1+ n)))))
Out of curiosity, why not use an &optional argument to
pos+ so that you don't need to fiddle with a helper
function?
(defun pos+ (l &optional (position 0))
(if (null l)
nil
(cons (+ (car l) position) (pos+ (cdr l) (1+ position)))))
Sean.
From: Kent M Pitman
Subject: Re: Self Study Question (mapcar) NOT HOMEWORK!
Date:
Message-ID: <sfwd8l1fd6a.fsf@world.std.com>
Sean Doran <···@sean.ebone.net> writes:
> Philip Lijnzaad <········@ebi.ac.uk> writes:
>
> > (defun pos+ (l) (pos2 l 0))
> > (defun pos2 (l n) (if [...]))
>
> Out of curiosity, why not use an &optional argument to pos+ [...]
>
> (defun pos+ (l &optional (position 0)) (if [....]))
Usually this is just an issue of personal style. A lot of people
just never discover this idiom and among those who do discover it,
some don't find it perspicuous.
However, there is an efficiency component, too. The solution
involving two functions probably takes up slightly more storage. The
solution involving the optional argument is probably slower because on
every recursive call it does a check for the optional argument and
only in the last case will that case be warranted.
Some people solve this dilemma by using an internal function defined
by LABELS.
(defun pos+ (l) (labels ((pos2 (l n) (if [...]))) (pos2 l 0)))
but of course some compilers compile this into two functions, and so
it might not save any space.
Personally, I think using recursion is the dominating style issue.
Tail recursion is good in Scheme because Scheme promises to optimize
away the stack use. Common Lisp makes no such promise, so I never
use recursion when my data structure might grow arbitrarily in size.
If the list l could be hundreds long, I *always* think that the
issue of stack space *must* dominate because stack errors cannot be
ignored in practice.
I generally use recursion in Lisp only where I know the depth is
limited or where I'm walking down a tree that I expect to grow only
as the log of the size of the tree. Even then, I sometimes get stack
overflows and have to reconsider and/or fuss with stack size in an
implementation-dependent way.
I remind people again that "good style" is never absolute. It is
always in the context of a great many practical considerations. There
may be competing aesthetics and competing praticalities driving a
final decision.
In article <···············@world.std.com>,
Kent M Pitman <······@world.std.com> wrote:
>Personally, I think using recursion is the dominating style issue.
>Tail recursion is good in Scheme because Scheme promises to optimize
>away the stack use. Common Lisp makes no such promise, so I never
>use recursion when my data structure might grow arbitrarily in size.
I agree.
If you'll recall, in my answer to the initial post in this thread (where
the exercise was to implement this using MAPCAR), I said that in real life
this would probably be implemented using DO or LOOP. Then someone asked
for a recursive solution. Both the MAPCAR and recursive functions are
interesting academic problems, but they aren't necessarily the most natural
solution for this particular problem.
A simple, easy-to-understand solution, IMHO, is:
(defun pos+ (list)
(loop for pos upfrom 0
for element in list
collect (+ pos element)))
Crystal clear (even if you don't "like" LOOP, you should have little
trouble understanding it), and about as efficient as possible.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.
From: ·····@orsi.com
Subject: Re: Self Study Question (overview) & a netiquette question
Date:
Message-ID: <877549115.31122@dejanews.com>
The basic thrust behind some of these answers seems to be - in working
academic exercises, focus on clarity rather than on efficiency, and
also don't worry if a solution is the clearest since in many cases
the reader's hands are tied. I agree with Barry Margolin that the LOOP or
DOLIST solution is the clearest.
I appreciate getting all the comments and input from all the people,
especially some of the stars of the community who have added their $.02.
I suppose I did not expect as many "toughies" in the early sections of a
programming text (is it a text, a reference, or both?) aimed at a wide
audience. I thought that I would write an answer notebook, and it would
be pretty much a walk in the park :-)
I still would be interested to know what the solution to the recursion is
if internal functions and optional arguments, two concepts not discussed
at that point in the book, are excluded. Of course, perhaps Graham did
not intend for us to work these in "academic" order and peeks to later
sections are perhaps supposed to be encouraged.
Obviously, I do not want to continually post "send your comments on
problem so&so" because I don't want to be annoying. I do want to
emphasize though that my goal throughout was to stimulate discussion and
introduce myself to the community. Any ideas on what would be the most
net-polite way to continue these discussions?
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
Sean Doran <···@sean.ebone.net> writes:
> Philip Lijnzaad <········@ebi.ac.uk> writes:
>
> > (defun pos+ (l)
> > (pos2 l 0))
> >
> > (defun pos2 (l n)
> > (if (null l)
> > nil
> > (cons (+ (car l) n) (pos2 (cdr l) (1+ n)))))
>
> Out of curiosity, why not use an &optional argument to
> pos+ so that you don't need to fiddle with a helper
> function?
>
> (defun pos+ (l &optional (position 0))
> (if (null l)
> nil
> (cons (+ (car l) position) (pos+ (cdr l) (1+ position)))))
I think this is bad style. It makes things slightly simpler for the
programmer, but clutters up the interface for the user. Why should the
user have to learn about some optional parameter when he'll always end
up using the default value anyway? Either the optional parameter
really belongs in the interface, in which case the fact that it
eliminates the need for an auxiliary function is just icing on the
cake; or the parameter doesn't really belong in the interface, in
which case it shouldn't be there. I think the usual style with LABELS
is much better.
Aaron
Ann Fok <·····@isu.edu> writes:
> Hi,
>
> I looked at one of the question on POS+ (which takes a list and return
> a list of each element plus its position)
>
> Such that:
> (pos+ '(8 7 6 6))
>
> (8 8 8 9)
>
> I tried to write a function by using recursion instead of iteration for
> it. However, somehow, I just could get it work at all! If any people
> here can do that, just let me know, I 'll appreciate!
>
> Thanks,
I think I saw someone post the same question from the same domain yesterday.