There is a question in ANSI Common Lisp in Lists chapter-
"Suppose the function pos+ takes a list and returns a list of each
element
plus its position:
> (pos+ ' ( 7 5 1 4 ) )
(7 6 3 7)
Define this function using (a) recursion, (b) iteration, (c) mapcar."
I have done them in following manner
(a) recursion
(defun ret-add-recur(lst n)(if(and (< n (length lst)) (not nil))
(progn(cons (+ (nth n lst) n) (ret-add-recur lst (+ n 1))))))
(b)iteration
(defun ret-add(lst)(let ((newlst nil))(dolist(obj lst)(push(+ obj
(position obj lst)) newlst))(reverse newlst)))
(c)
(defun ret-add(lst)(mapcar #'(lambda(x)(+ (position x lst) x)) lst))
What do you think of my solutions? How else one could attemt these
problems?
For recursion case,i added extra parameter,the starting position.
regards
vishy
On Nov 21, 7:46 am, vishy <············@gmail.com> wrote:
> There is a question in ANSI Common Lisp in Lists chapter-
> "Suppose the function pos+ takes a list and returns a list of each
> element
> plus its position:> (pos+ ' ( 7 5 1 4 ) )
>
> (7 6 3 7)
> Define this function using (a) recursion, (b) iteration, (c) mapcar."
>
> I have done them in following manner
> (a) recursion
It's very helpful to indent your Lisp like so:
(defun ret-add-recur (lst n)
(if (and (< n (length lst)) (not nil))
(progn
(cons (+ (nth n lst) n)
(ret-add-recur lst (+ n 1))))))
It makes the structure immediately apparent, without requiring anyone
to read parentheses. Your editor should assist you in doing this
automatically. If it doesn't, you should probably find a better
editor.
On to the function.
It has one minor problem, in that it might blow up on long lists,
because you can only call it so many times before you run out of stack
space. Sometimes that's not a big deal, but it's something to
consider.
Next, it has a major problem: it's slow. Really slow. (length list)
needs to walk down the whole list each time you call it, and (nth n
list) has to walk to element n each time you call it. That's a lot of
extra work to be doing.
Do you know about CAR and CDR (or FIRST and REST)? If you don't know
about them, read about them in /ANSI Common Lisp/, since you need to
understand them to understand lists at all.
If you're using recursion to move down a list, you want to be using
those functions instead of NTH.
Also, you should either make the second parameter optional, or use a
LABELS form to create a local function which you can pass the second
parameter (of 0) to.
Cheers,
Pillsy
I changed the iteration solution to:
(defun ret-add(lst)
(let ((newlst nil))
(let ((n 0))
(dolist(obj lst)
(push(+ obj n) newlst)(setq n (+ n 1)))
(reverse newlst))))
From: Ken Tilton
Subject: Re: Newbie-solved a problem in ANSI common lisp
Date:
Message-ID: <l1f1j.2$QX7.0@newsfe09.lga>
vishy wrote:
> I changed the iteration solution to:
>
> (defun ret-add(lst)
> (let ((newlst nil))
> (let ((n 0))
Let takes multiple initializations, so there is no need for two.
> (dolist(obj lst)
the third parameter of the first parameter to dolist is a good place to
mop up the iteration's work (reversing, in this case).
> (push(+ obj n) newlst)(setq n (+ n 1)))
Just use setf. And incf. And if you start at -1 you can increment JIT in
the sum.
> (reverse newlst))))
It is vitally important to understand consing. This code just generated
all the structure reverse will be touching, so it can use nreverse.
(let (newlst (n -1))
(dolist (o l (nreverse n))
(push (+ o (incf n)) n)))
...or go green on the parens:
(loop for n upfrom 0
for o in l
collecting (+ o n))
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
P� Thu, 22 Nov 2007 10:33:20 +0100, skrev vishy <············@gmail.com>:
> I changed the iteration solution to:
>
> (defun ret-add(lst)
> (let ((newlst nil))
> (let ((n 0))
> (dolist(obj lst)
> (push(+ obj n) newlst)(setq n (+ n 1)))
> (reverse newlst))))
>
>
this is a bit better
(defun add-index (number-list)
(let (new-list (index 0))
(dolist (number number-list)
(push (+ number index) new-list)
(incf index))
(nreverse new-list)))
more descriptive names, null is the default value for variables, (incf n)
rather than (setq n (+ n 1)), nreverse s better when you know the list is
fresh (faster).
or using loop
(defun add-index (number-list)
(loop for number in number-list
for index from 0
collect (+ number index)))
--------------
John Thingstad
In article
<····································@b36g2000hsa.googlegroups.com>,
vishy <············@gmail.com> wrote:
> There is a question in ANSI Common Lisp in Lists chapter-
> "Suppose the function pos+ takes a list and returns a list of each
> element
> plus its position:
> > (pos+ ' ( 7 5 1 4 ) )
> (7 6 3 7)
> Define this function using (a) recursion, (b) iteration, (c) mapcar."
>
> I have done them in following manner
> (a) recursion
> (defun ret-add-recur(lst n)(if(and (< n (length lst)) (not nil))
> (progn(cons (+ (nth n lst) n) (ret-add-recur lst (+ n 1))))))
> (b)iteration
> (defun ret-add(lst)(let ((newlst nil))(dolist(obj lst)(push(+ obj
> (position obj lst)) newlst))(reverse newlst)))
> (c)
> (defun ret-add(lst)(mapcar #'(lambda(x)(+ (position x lst) x)) lst))
>
> What do you think of my solutions? How else one could attemt these
> problems?
> For recursion case,i added extra parameter,the starting position.
>
> regards
> vishy
You should really format the Lisp code so that we can read it.
Right now it is just a stream of characters.
A)
Inefficient, needs two args. (NOT NIL) is always T.
B)
Try '(1 1 1) as input. Gives the wrong result.
POSITION is inefficient.
C)
Try '(1 1 1) as input. Gives the wrong result.
POSITION is inefficient.
Generally it is not enough to write the functions.
Write a bunch of test cases with expected outcome
and run the test cases for each function.
For example like this:
(defun run-testcases ()
(let ((functions (list 'ret-add))
(testcases '((((1 1 1)) (1 2 3))
(((2 2 2)) (2 3 4))
(((1)) (1))
(((4 3 2)) (4 4 4)))))
(loop for function in functions collect
(loop for (args result) in testcases
collect (equal (apply function args) result)))))
? (run-testcases)
((NIL NIL T T))
--
http://lispm.dyndns.org/
On Nov 21, 6:09 pm, Rainer Joswig <······@lisp.de> wrote:
> In article
> <····································@b36g2000hsa.googlegroups.com>,
>
>
>
> vishy <············@gmail.com> wrote:
> > There is a question in ANSI Common Lisp in Lists chapter-
> > "Suppose the function pos+ takes a list and returns a list of each
> > element
> > plus its position:
> > > (pos+ ' ( 7 5 1 4 ) )
> > (7 6 3 7)
> > Define this function using (a) recursion, (b) iteration, (c) mapcar."
>
> > I have done them in following manner
> > (a) recursion
> > (defun ret-add-recur(lst n)(if(and (< n (length lst)) (not nil))
> > (progn(cons (+ (nth n lst) n) (ret-add-recur lst (+ n 1))))))
> > (b)iteration
> > (defun ret-add(lst)(let ((newlst nil))(dolist(obj lst)(push(+ obj
> > (position obj lst)) newlst))(reverse newlst)))
> > (c)
> > (defun ret-add(lst)(mapcar #'(lambda(x)(+ (position x lst) x)) lst))
>
> > What do you think of my solutions? How else one could attemt these
> > problems?
> > For recursion case,i added extra parameter,the starting position.
>
> > regards
> > vishy
>
> You should really format the Lisp code so that we can read it.
> Right now it is just a stream of characters.
>
> A)
>
> Inefficient, needs two args. (NOT NIL) is always T.
>
> B)
>
> Try '(1 1 1) as input. Gives the wrong result.
> POSITION is inefficient.
>
> C)
>
> Try '(1 1 1) as input. Gives the wrong result.
> POSITION is inefficient.
>
> Generally it is not enough to write the functions.
> Write a bunch of test cases with expected outcome
> and run the test cases for each function.
>
> For example like this:
>
> (defun run-testcases ()
> (let ((functions (list 'ret-add))
> (testcases '((((1 1 1)) (1 2 3))
> (((2 2 2)) (2 3 4))
> (((1)) (1))
> (((4 3 2)) (4 4 4)))))
> (loop for function in functions collect
> (loop for (args result) in testcases
> collect (equal (apply function args) result)))))
>
> ? (run-testcases)
> ((NIL NIL T T))
>
> --http://lispm.dyndns.org/
So,are you saying recursion can be written with one argument only-a
list .
thanks