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

Discussion of Common Lisp
Ajschylos
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

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

Post by 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.

implausibleusername
Posts: 6
Joined: Sun Aug 24, 2008 2:11 pm

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

Post by 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.

Ajschylos
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

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

Post by 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.

AlexPaes
Posts: 21
Joined: Sat Jun 28, 2008 3:38 am
Location: Lisbon, Portugal

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

Post by 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>

Ajschylos
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

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

Post by Ajschylos » Sat Jan 24, 2009 7:24 am

Great thanks for your comment. Now I understand better.

implausibleusername
Posts: 6
Joined: Sun Aug 24, 2008 2:11 pm

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

Post by 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.

danb
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US
Contact:

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

Post by 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)

Ajschylos
Posts: 18
Joined: Wed Jan 07, 2009 12:44 pm

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

Post by Ajschylos » Sun Jan 25, 2009 2:23 am

Thank you, that's really piece of beautiful code.
A.

danb
Posts: 35
Joined: Sat Jun 28, 2008 1:05 pm
Location: Urbana, Illinois, US
Contact:

FP

Post by 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.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: FP

Post by 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.

Post Reply