I'm new to Lisp and I'm having some difficulty. I'm
doing an exercise that asks you to write a function
pos+ that takes a list and returns a list of each
element plus its position.
> (pos+ '(7 5 1 4))
(7 6 3 7)
I'm trying to write a RECURSIVE function that uses
only PRIMITIVE operators.
So far I have:
(defun pos+ (lst)
(if (null lst)
nil
(cons (car lst) (add1 (pos+ (cdr lst))))))
(defun add1 (lst)
(if (null lst)
nil
(cons (+ (car lst) 1) (add1 (cdr lst)))))
which is not correct (it uses two functions) - and it's
pretty lame besides that :)
I think that the point of this exercise is that I
should figure how to send information forward through
a recursive call and later collapse it into a list.
Could anyone recommend a function template to do this
using only simple expressions.
Thanks,
Chuck
In article <····························@posting.google.com>, Charles
K Johnson wrote:
>I'm new to Lisp and I'm having some difficulty. I'm
>doing an exercise that asks you to write a function
>pos+ that takes a list and returns a list of each
>element plus its position.
>
>> (pos+ '(7 5 1 4))
>(7 6 3 7)
>
>I'm trying to write a RECURSIVE function that uses
>only PRIMITIVE operators.
>
>So far I have:
>
>(defun pos+ (lst)
> (if (null lst)
> nil
> (cons (car lst) (add1 (pos+ (cdr lst))))))
>
>(defun add1 (lst)
> (if (null lst)
> nil
> (cons (+ (car lst) 1) (add1 (cdr lst)))))
This is a little bit roundabout. Instead of add1,
why don't you have an extra parameter which tells
you what the initial position is?
Think, supose you have the list '(1 2 3 4). And suppose
that, recursively, you have reached a point where
you have the list '(3 4) and you want to process that.
Well, the result will have to be '(5 6). You have to
somehow know that the position of 3 is really 2, not 0.
That information can come from an extra parameter
that is passed down through the recursive calls.
(defun do-pos+ (lst pos)
(if (null lst)
nil
(cons (+ pos (first lst)) (do-pos+ (rest lst) (1+ pos)))))
(defun pos+ (lst) (do-pos+ lst 0))
So in other words, calculate do-pos+ on the rest of the list
with a position one greater than the one given, and then
tack on the first node of the list plus the position given.
You can collapse the interface function and the recursive
helper into one by making the position an optional parameter
whose value is zero if it is not specified:
(defun pos+ (lst &optional (pos 0))
(if (null lst)
nil
(cons (+ pos (first lst)) (pos+ (rest lst) (1+ pos)))))
Now see whether you can get your add1-based implementation working.
Hint: inside pos+, you construct a list formed by consing
the first element, and the remaining ones filtered through add1. But the
job is not done; you cannot just return that list. You have to divide
that new list it into car and cdr and do something with it. Simplify
the task by assigning the temporary list to a local variable:
(defun pos+ (lst)
(if (null lst)
nil
(let ((temp-list (cons (car lst) (add1 (pos+ (cdr lst))))))
; hint: do something with temp-list now!
)))
Good luck.
In article <····························@posting.google.com>, Charles
K Johnson wrote:
>I'm new to Lisp and I'm having some difficulty. I'm
>doing an exercise that asks you to write a function
>pos+ that takes a list and returns a list of each
>element plus its position.
>
>> (pos+ '(7 5 1 4))
>(7 6 3 7)
>
>I'm trying to write a RECURSIVE function that uses
>only PRIMITIVE operators.
>
>So far I have:
>
>(defun pos+ (lst)
> (if (null lst)
> nil
> (cons (car lst) (add1 (pos+ (cdr lst))))))
>
>(defun add1 (lst)
> (if (null lst)
> nil
> (cons (+ (car lst) 1) (add1 (cdr lst)))))
This is a little bit roundabout. Instead of add1,
why don't you have an extra parameter which tells
you what the initial position is?
Think, supose you have the list '(1 2 3 4). And suppose
that, recursively, you have reached a point where
you have the list '(3 4) and you want to process that.
Well, the result will have to be '(5 6). You have to
somehow know that the position of 3 is really 2, not 0.
That information can come from an extra parameter
that is passed down through the recursive calls.
(defun do-pos+ (lst pos)
(if (null lst)
nil
(cons (+ pos (first lst)) (do-pos+ (rest lst) (1+ pos)))))
(defun pos+ (lst) (do-pos+ lst 0))
So in other words, calculate do-pos+ on the rest of the list
with a position one greater than the one given, and then
tack on the first node of the list plus the position given.
You can collapse the interface function and the recursive
helper into one by making the position an optional parameter
whose value is zero if it is not specified:
(defun pos+ (lst &optional (pos 0))
(if (null lst)
nil
(cons (+ pos (first lst)) (pos+ (rest lst) (1+ pos)))))
Now see whether you can get your add1-based implementation working!
Hint: inside pos+, you need to put the cdr of the list through one
more transformation in addition to (add1 ...)
·················@hotmail.com (Charles K Johnson) writes:
> I'm new to Lisp and I'm having some difficulty. I'm
> doing an exercise that asks you to write a function
> pos+ that takes a list and returns a list of each
> element plus its position.
>
> > (pos+ '(7 5 1 4))
> (7 6 3 7)
>
> I'm trying to write a RECURSIVE function that uses
> only PRIMITIVE operators.
>
> So far I have:
>
> (defun pos+ (lst)
> (if (null lst)
> nil
> (cons (car lst) (add1 (pos+ (cdr lst))))))
>
> (defun add1 (lst)
> (if (null lst)
> nil
> (cons (+ (car lst) 1) (add1 (cdr lst)))))
>
> which is not correct (it uses two functions) - and it's
> pretty lame besides that :)
i don't think having two functions is necessarily bad.
> I think that the point of this exercise is that I
> should figure how to send information forward through
> a recursive call and later collapse it into a list.
consider the function of two arguments
(defun pos+ (lst acc)
....)
call it the first time with acc being '() aka nil.
hence call it like
(pos+ '(7 5 1 4) '())
the reason for acc is to make some more scratch pad for yourself which
you can pass to the next call of pos+. let acc accumulate the
incremented list as you go.
btw you can "hide" the acc with &optional
(defun pos+ (lst &optional acc)
....)
when given only one arg, acc is automatically set to nil.
another hint, i like CONSP which tells me if i have a non-emtpy list
or not. NULL finds NIL, but considers lists and, e.g., number atoms
to both be non-nil. so if CONSP is true, you can take CAR and CDR.
but if NULL is false, you might not. this may be beyond the scope
though.
> Could anyone recommend a function template to do this
> using only simple expressions.
if you get a lot this kind of exercise, consider writing MY-MAPCAR.
then you can apply the MAPCAR sledge-hammer at all sorts of problems.
hint, you will need FUNCALL. with MAPCAR this problem is trivial.
(defun pos+ (lst)
(mapcar #'1+ lst))
fwiw i figure that a Lisp without MAPCAR is no Lisp at all. and if
they won't let you have the full power of Lisp, you might need to
reinvent it. ;-)
> Thanks,
> Chuck
--
J o h a n K u l l s t a m
[········@ne.mediaone.net]
sysengr
"Johan Kullstam" <········@ne.mediaone.net> wrote in message
···················@sysengr.res.ray.com...
> ·················@hotmail.com (Charles K Johnson) writes:
>
> > I'm new to Lisp and I'm having some difficulty. I'm
> > doing an exercise that asks you to write a function
> > pos+ that takes a list and returns a list of each
> > element plus its position.
> >
> > > (pos+ '(7 5 1 4))
> > (7 6 3 7)
> >
[snip]
> (defun pos+ (lst)
> (mapcar #'1+ lst))
>
Despite the good tips in the rest of your post, I think that last one was a
little hasty!
CL-USER 1 > (mapcar #'1+ '(7 5 1 4))
(8 6 2 5)
How about:
(defun pos+ (numbers)
(let ((position -1))
(mapcar #'(lambda (num)
(+ num (incf position)))
numbers)))
CL-USER 3 > (pos+ '(7 5 1 4))
(7 6 3 7)
(I don't mind posting this solution because it violates the silly
requirement of being recursive, so no free homework done! : )
Coby
--
(remove #\space "coby . beck @ opentechgroup . com")
"Coby Beck" <·····@mercury.bc.ca> writes:
> "Johan Kullstam" <········@ne.mediaone.net> wrote in message
> ···················@sysengr.res.ray.com...
> > ·················@hotmail.com (Charles K Johnson) writes:
> >
> > > I'm new to Lisp and I'm having some difficulty. I'm
> > > doing an exercise that asks you to write a function
> > > pos+ that takes a list and returns a list of each
> > > element plus its position.
> > >
> > > > (pos+ '(7 5 1 4))
> > > (7 6 3 7)
> > >
> [snip]
> > (defun pos+ (lst)
> > (mapcar #'1+ lst))
> >
>
> Despite the good tips in the rest of your post, I think that last one was a
> little hasty!
good eye. i was too quick and didn't his question carefully enough.
--
J o h a n K u l l s t a m
[········@ne.mediaone.net]
sysengr
"Coby Beck" <·····@mercury.bc.ca> writes:
> How about:
>
> (defun pos+ (numbers)
> (let ((position -1))
> (mapcar #'(lambda (num)
> (+ num (incf position)))
> numbers)))
>
> CL-USER 3 > (pos+ '(7 5 1 4))
> (7 6 3 7)
>
>
> (I don't mind posting this solution because it violates the silly
> requirement of being recursive, so no free homework done! : )
>
I really want someone to write an automatic recursion obscurifier
which produces the answers I always seem to end up posting to these
questions.
(defun pos+ (l)
((lambda (p r)
(funcall r r (funcall p p l 0 '()) '()))
(lambda (c l p a)
(if (null l)
a
(funcall c c (cdr l) (1+ p)
(cons (+ p (car l)) a))))
(lambda (c l a)
(if (null l)
a
(funcall c c (cdr l)
(cons (car l) a))))))
I think this qualifies as a recursive solution which only uses
primitives. I leave it as an exercise to rewrite this using church
numerals.
--tim
Tim Bradshaw <···@tfeb.org> writes:
> "Coby Beck" <·····@mercury.bc.ca> writes:
>
> > How about:
> >
> > (defun pos+ (numbers)
> > (let ((position -1))
> > (mapcar #'(lambda (num)
> > (+ num (incf position)))
> > numbers)))
> >
> > CL-USER 3 > (pos+ '(7 5 1 4))
> > (7 6 3 7)
> >
> >
> > (I don't mind posting this solution because it violates the silly
> > requirement of being recursive, so no free homework done! : )
> >
>
> I really want someone to write an automatic recursion obscurifier
> which produces the answers I always seem to end up posting to these
> questions.
Wouldnt't:
(defun pos+ (list)
(mapcar #'1-
(mapcar #'+ list (loop for x from 1 to (length list) collect x))))
work?
Ah, violates the "must be recursive".
//Ingvar
--
"Madwolf opening conversational salvo will notice that's interesting."
Pfy
Ingvar Mattsson <······@bofh.se> writes:
> (defun pos+ (list)
> (mapcar #'1-
> (mapcar #'+ list (loop for x from 1 to (length list) collect x))))
> work?
>
> Ah, violates the "must be recursive".
Heh. The outer 1- could be avoided by counting x from 0, btw.
But as long as you're going to do that, I think
(defun pos+ (list)
(loop for pos from 0
for elt in list
collect (+ elt pos)))
is a nicely non-recursive solution. Usually LOOP of any kind can't
be used in homework. Too bad. I never used to be much of a fan of
it myself, but examples like these make things so clear that it's
ridiculous to fight its use on some sort of aesthetic grounds.
> I'm new to Lisp and I'm having some difficulty. I'm
> doing an exercise that asks you to write a function
> pos+ that takes a list and returns a list of each
> element plus its position.
I didn't see anyone use `labels' yet:
(defun pos+ (list)
(labels ((pos-helper (list return)
(if (endp list)
(reverse return)
(pos-helper (cdr list)
(cons (list (car list)
(1+ (length return)))
return)))))
(pos-helper list nil)))
* (pos+ '(8 2 4 9 3))
((8 1) (2 2) (4 3) (9 4) (3 5))
*
This is a recursive version that uses primitive common lisp
operations. It only has one defun in it, so one could argue (wrongly)
that it only uses one function. Actually in CMUCL at least the
pos-helper function winds up being optimized into a loop anyway.
--
Fred Gilham ······@csl.sri.com
I was storing data in every conceivable way, including keeping a chain
of sound waves running between the speaker and the microphone. There
was no more memory left to be had....
Fred Gilham wrote:
> > I'm new to Lisp and I'm having some difficulty. I'm
> > doing an exercise that asks you to write a function
> > pos+ that takes a list and returns a list of each
> > element plus its position.
>
I interpreted it as a list of all the elements added (+) with its
position, where the first position is 0.
> * (pos+ '(8 2 4 9 3))
> ((8 1) (2 2) (4 3) (9 4) (3 5))
> *
This is the list of lists, each with each element *in addition to* its
position, first position is 1 here. See original posting.
rg
Robert Gonzalez <·······@austin.rr.com> writes:
> Fred Gilham wrote:
>
> > > I'm new to Lisp and I'm having some difficulty. I'm
> > > doing an exercise that asks you to write a function
> > > pos+ that takes a list and returns a list of each
> > > element plus its position.
> >
>
> I interpreted it as a list of all the elements added (+) with its
> position, where the first position is 0.
>
> > * (pos+ '(8 2 4 9 3))
> > ((8 1) (2 2) (4 3) (9 4) (3 5))
> > *
>
> This is the list of lists, each with each element *in addition to* its
> position, first position is 1 here. See original posting.
>
> rg
>
Oops, I think you're right. However, they say that the mark of a good
program is that you can change it easily when the requirements change.
I change `list' to `+' and get:
(defun pos+ (list)
(declare (optimize (speed 3) (space 0)))
(labels ((pos-helper (list return)
(if (endp list)
(reverse return)
(pos-helper (cdr list)
(cons (+ (car list) (1+ (length return)))
return)))))
(pos-helper list nil)))
* (pos+ '(8 9 3 1 4))
(9 11 6 5 9)
*
:-)
--
Fred Gilham ······@csl.sri.com
I was storing data in every conceivable way, including keeping a chain
of sound waves running between the speaker and the microphone. There
was no more memory left to be had....
In article <··············@snapdragon.csl.sri.com>, Fred Gilham wrote:
>
>> I'm new to Lisp and I'm having some difficulty. I'm
>> doing an exercise that asks you to write a function
>> pos+ that takes a list and returns a list of each
>> element plus its position.
>
>I didn't see anyone use `labels' yet:
>
>
>(defun pos+ (list)
> (labels ((pos-helper (list return)
> (if (endp list)
> (reverse return)
> (pos-helper (cdr list)
> (cons (list (car list)
> (1+ (length return)))
> return)))))
> (pos-helper list nil)))
This can't die yet! I haven't anyone use a recursive macro to statically
expand the thing when possible, so here goes:
(defun pos+-fun (lst &optional (pos 0))
(if (null lst)
nil
(cons (+ pos (first lst)) (pos+-fun (rest lst) (1+ pos)))))
(defmacro pos+ (form)
(cond
;; Handle nil.
((null form) nil)
;; Handle atom, like variable name.
;; Simply generate the function call to handle this case.
((atom form) `(pos+-fun ,form))
;; Handle quote of atom like 'nil
;; Takes care of termination of recursion when ',tail below yields 'nil
((and (eql 'quote (first form)) (atom (second form))) (second form))
;; handle quote of list like '(0) or '(0 0 0)
((and (eql 'quote (first form)) (listp (second form)))
(let ((tail (mapcar #'1+ (rest (second form)))))
`(cons ,(first (second form)) (pos+ ',tail))))))
Test:
> (macroexpand '(pos+ nil))
NIL ;
T
> (macroexpand '(pos+ '(0)))
(CONS 0 (POS+ 'NIL)) ;
T
> (macroexpand '(pos+ x))
(POS+-FUN X) ;
T
> (macroexpand '(pos+ '( 0 0 0)))
(CONS 0 (POS+ '(1 1))) ;
T
In article <·······················@news1.rdc1.bc.home.com>,
Kaz Kylheku <···@ashi.footprints.net> wrote:
>In article <··············@snapdragon.csl.sri.com>, Fred Gilham wrote:
>>
>>> I'm new to Lisp and I'm having some difficulty. I'm
>>> doing an exercise that asks you to write a function
>>> pos+ that takes a list and returns a list of each
>>> element plus its position.
>>
>>I didn't see anyone use `labels' yet:
>>...
>
>This can't die yet! I haven't anyone use a recursive macro to statically
>expand the thing when possible, so here goes:
>...
I haven't seen anyone offer an elegant Scheme solution
with iteration via tail recursion, destructive
reverse, call/cc, and upward continuations -- a
situation that needs to be remedied forthwith:
(define pos+
(lambda (l)
(letrec ((pos (lambda (return)
(let loop ((i 0))
(call/cc
(lambda (next)
(set! pos
(lambda (new-return)
(set! return new-return)
(next #f)))
(return i)))
(loop (+ i 1))))))
(let loop ((l l) (r '()))
(if (null? l) (reverse! r)
(loop (cdr l)
(cons (+ (car l)
(call/cc pos))
r)))))))
--d
In article <············@news.gte.com>, Dorai Sitaram wrote:
>In article <·······················@news1.rdc1.bc.home.com>,
>Kaz Kylheku <···@ashi.footprints.net> wrote:
>>This can't die yet! I haven't anyone use a recursive macro to statically
>>expand the thing when possible, so here goes:
>>...
>
>I haven't seen anyone offer an elegant Scheme solution
>with iteration via tail recursion, destructive
>reverse, call/cc, and upward continuations -- a
Why only upward? I think that the task can be decomposed into N continuations,
each of which processes one element. Then the continuations can be
restarted in order. ;)
--
Refracturing: the technique of taking broken code, and breaking it some more.
In article <····························@posting.google.com>,
·················@hotmail.com (Charles K Johnson) wrote:
>I'm new to Lisp and I'm having some difficulty. I'm
>doing an exercise that asks you to write a function
>pos+ that takes a list and returns a list of each
>element plus its position.
>
>> (pos+ '(7 5 1 4))
>(7 6 3 7)
>
>I'm trying to write a RECURSIVE function that uses
>only PRIMITIVE operators.
? (defun pos+ (lst &optional (curr-pos 0))
(if lst
(cons (+ (first lst) curr-pos)
(pos+ (rest lst) (1+ curr-pos)))
lst))
POS+
? (pos+ '())
NIL
? (pos+ '(7))
(7)
? (pos+ '(7 5 1 4))
(7 6 3 7)
?
sashank
Charles K Johnson wrote:
> I'm new to Lisp and I'm having some difficulty. I'm
> doing an exercise that asks you to write a function
> pos+ that takes a list and returns a list of each
> element plus its position.
>
> > (pos+ '(7 5 1 4))
> (7 6 3 7)
>
> I'm trying to write a RECURSIVE function that uses
> only PRIMITIVE operators.
>
> So far I have:
>
> (defun pos+ (lst)
> (if (null lst)
> nil
> (cons (car lst) (add1 (pos+ (cdr lst))))))
>
> (defun add1 (lst)
> (if (null lst)
> nil
> (cons (+ (car lst) 1) (add1 (cdr lst)))))
>
> which is not correct (it uses two functions) - and it's
> pretty lame besides that :)
>
> I think that the point of this exercise is that I
> should figure how to send information forward through
> a recursive call and later collapse it into a list.
>
> Could anyone recommend a function template to do this
> using only simple expressions.
>
> Thanks,
> Chuck
(defun pos+ (l)
(cond ((null l) l)
(t (let ((l2 (mapcar #'1+ l)))
(cons (car l2) (pos+ (cdr l)))))))
rg
Robert Gonzalez wrote:
> Charles K Johnson wrote:
>
> > I'm new to Lisp and I'm having some difficulty. I'm
> > doing an exercise that asks you to write a function
> > pos+ that takes a list and returns a list of each
> > element plus its position.
> >
> > > (pos+ '(7 5 1 4))
> > (7 6 3 7)
> >
> > I'm trying to write a RECURSIVE function that uses
> > only PRIMITIVE operators.
> >
> > So far I have:
> >
> > (defun pos+ (lst)
> > (if (null lst)
> > nil
> > (cons (car lst) (add1 (pos+ (cdr lst))))))
> >
> > (defun add1 (lst)
> > (if (null lst)
> > nil
> > (cons (+ (car lst) 1) (add1 (cdr lst)))))
> >
> > which is not correct (it uses two functions) - and it's
> > pretty lame besides that :)
> >
> > I think that the point of this exercise is that I
> > should figure how to send information forward through
> > a recursive call and later collapse it into a list.
> >
> > Could anyone recommend a function template to do this
> > using only simple expressions.
> >
> > Thanks,
> > Chuck
>
> (defun pos+ (l)
> (cond ((null l) l)
> (t (let ((l2 (mapcar #'1+ l)))
> (cons (car l2) (pos+ (cdr l)))))))
>
Oops, I meant to post: (my cut and paste doesn't work well between unix
and windows with this stupid sunpci card, it pasted an older version)
(defun pos+ (l)
(cond ((null l) l)
(t (cons (car l) (pos+ (mapcar #'1+ (cdr l)))))))
rg
Robert Gonzalez <·······@austin.rr.com> writes:
> Charles K Johnson wrote:
>
> > I'm new to Lisp and I'm having some difficulty. I'm
> > doing an exercise that asks you to write a function
> > pos+ that takes a list and returns a list of each
> > element plus its position.
> >
> > > (pos+ '(7 5 1 4))
> > (7 6 3 7)
> >
> > I'm trying to write a RECURSIVE function that uses
> > only PRIMITIVE operators.
> >
> (defun pos+ (l)
> (cond ((null l) l)
> (t (let ((l2 (mapcar #'1+ l)))
> (cons (car l2) (pos+ (cdr l)))))))
Alright!
(defun pos+ (l)
(mapcar #'+ (iota (length l)) l))
(defun iota (n)
(if (zerop n)
()
(append (iota (1- n)) (list (1- n)))))
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.