pos+ function from Paul Graham's "ANSI Common Lisp"

Discussion of Common Lisp

pos+ function from Paul Graham's "ANSI Common Lisp"

Postby Ajschylos » Fri Jan 23, 2009 2:56 pm

Hi, I've tried to solve an exercise 5 from page 57
that is:
"Suppose the function pos+ takes a list and returns a list of each element plus it's position:
> (pos+ '(7 5 1 4))
(7 6 3 7)
Define this function using (a) recursion, (b) iteration, (c) mapcar."

(a) and (b) are straightforward, but (c) I solved following way:
Code: Select all
(defun pos+ (l)

  (let ((i -1)) (mapcar #'(lambda (x) (incf i) (+ x i) )
           l )))


I don't like this code, can anybody suggest more elegant solution?

Moreover, I don't understand why

Code: Select all
   (let ((i -1)) (mapcar #'(lambda (x) (+ x i) (incf i) )
           l )))


doesn't work. Please help because I'm stuck with learning.
Ajschylos
 
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

Re: pos+ function from Paul Graham's "ANSI Common Lisp"

Postby implausibleusername » Fri Jan 23, 2009 4:19 pm

So
Code: Select all
 (let ((i -1)) (mapcar #'(lambda (x) (+ x i) (incf i) )
           l )))


should be

Code: Select all
 (let ((i 0)) (mapcar #'(lambda (x) (+ x i) (incf i) )
           l )))


Alternatives are:
Code: Select all
 (mapcar (let ((i 0)) (lambda (x) (+ x i) (incf i) ))
      l ))


or
Code: Select all
(mapcar #'+ list (loop for k in list
                for i from 0 collect i))


I don't think either of them are more elegant, and your solution is most likely to be efficient.
implausibleusername
 
Posts: 6
Joined: Sun Aug 24, 2008 2:11 pm

Re: pos+ function from Paul Graham's "ANSI Common Lisp"

Postby Ajschylos » Sat Jan 24, 2009 1:22 am

Hi,
unfortunately none of your solutions works properly except the last one.
I mean the print the list of successive numbers starting from one ending on the length of the list.

The last one I treat as iterative solution.
Ajschylos
 
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

Re: pos+ function from Paul Graham's "ANSI Common Lisp"

Postby AlexPaes » Sat Jan 24, 2009 6:03 am

The problem with 'implausibleusername' functions is the order of the forms, since the functions return the last evaluated form the functions will return the value of (incf i), you can either wrap a PROG1 form around these, like:

Code: Select all
(let ((i 0)) (mapcar #'(lambda (x) (prog1 (+ x i)(incf i))) l))


or have the forms order switched like:
Code: Select all
(let ((i -1)) (mapcar #'(lambda (x) (incf i)(+ x i)) l))


Note that the variable i must have different starting values in each approach because the variable is increased before the sum in the last example while it is increased after the sum in first one.

EDIT:
You can even chain the variable increase with the sum:
Code: Select all
(let ((i -1)) (mapcar #'(lambda (x) (+ x (incf i))) l))
CL-USER> (setf *boss* (make-instance 'smart-person))
NIL
CL-USER>
User avatar
AlexPaes
 
Posts: 21
Joined: Sat Jun 28, 2008 3:38 am
Location: Lisbon, Portugal

Re: pos+ function from Paul Graham's "ANSI Common Lisp"

Postby Ajschylos » Sat Jan 24, 2009 7:24 am

Great thanks for your comment. Now I understand better.
Ajschylos
 
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

Re: pos+ function from Paul Graham's "ANSI Common Lisp"

Postby implausibleusername » Sat Jan 24, 2009 10:02 am

AlexPaes wrote:The problem with 'implausibleusername' functions is the order of the forms, since the functions return the last evaluated form the functions will return the value of (incf i), you can either wrap a PROG1 form around these, like:

That'll teach me not to use '(1 1 1) as a test case.
implausibleusername
 
Posts: 6
Joined: Sun Aug 24, 2008 2:11 pm

Re: pos+ function from Paul Graham's "ANSI Common Lisp"

Postby danb » Sun Jan 25, 2009 2:13 am

Ajschylos wrote:
Code: Select all
(defun pos+ (l)
  (let ((i -1)) (mapcar #'(lambda (x) (incf i) (+ x i) )
           l )))

I don't like this code, can anybody suggest more elegant solution?

If you're going to use MAPCAR, you might as well write a functional solution.
That means no INCF, at least not in the toplevel function. Instead, write another function that returns a list of integers to be added to the elements of your list, and map #'+ onto the two lists.

Code: Select all
> (defun range0 (max)
    (loop for x below max
          collect x))
RANGE0
> (range0 10)
(0 1 2 3 4 5 6 7 8 9)
> (defun pos+ (list)
    (mapcar #'+ list (range0 (length list))))
POS+
> (pos+ (list 1 5 2 9 12))
(1 6 4 12 16)
danb
 
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US

Re: pos+ function from Paul Graham's "ANSI Common Lisp"

Postby Ajschylos » Sun Jan 25, 2009 2:23 am

Thank you, that's really piece of beautiful code.
A.
Ajschylos
 
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

FP

Postby danb » Sun Jan 25, 2009 11:34 am

Ajschylos wrote:that's really piece of beautiful code.

That's functional programming :P You can write code like that for lots of applications. It tends to be a little slower and more memory-intensive than imperative code, but once you get used to FP, hard programs can actually be both fun and easy.
danb
 
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US

Re: FP

Postby Ramarren » Sun Jan 25, 2009 12:01 pm

danb wrote:That's functional programming :P You can write code like that for lots of applications. It tends to be a little slower and more memory-intensive than imperative code, but once you get used to FP, hard programs can actually be both fun and easy.


Note that using a package like SERIES you can write the code functionally, and yet have in many cases efficiency equal to iterative solution, because the system will optimize many common cases, in particular using delayed evaluation to avoid having to keep intermediary mapping results in memory. For example in this code equivalent to the above:

Code: Select all
(defun pos+ (list)
  (collect (map-fn 'number #'+ (scan list) (scan-range :below (length list)))))


the SCAN-RANGE function doesn't create all numbers at once, but only as they are needed. Not that this really matters for this particular example, but for larger functions it can.
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Next

Return to Common Lisp

Who is online

Users browsing this forum: Google [Bot], Yahoo [Bot] and 1 guest