Page 1 of 2

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

Posted: Fri Jan 23, 2009 2:56 pm
by Ajschylos
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.

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

Posted: Fri Jan 23, 2009 4:19 pm
by implausibleusername
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.

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

Posted: Sat Jan 24, 2009 1:22 am
by Ajschylos
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.

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

Posted: Sat Jan 24, 2009 6:03 am
by AlexPaes
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))

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

Posted: Sat Jan 24, 2009 7:24 am
by Ajschylos
Great thanks for your comment. Now I understand better.

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

Posted: Sat Jan 24, 2009 10:02 am
by implausibleusername
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.

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

Posted: Sun Jan 25, 2009 2:13 am
by danb
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)

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

Posted: Sun Jan 25, 2009 2:23 am
by Ajschylos
Thank you, that's really piece of beautiful code.
A.

FP

Posted: Sun Jan 25, 2009 11:34 am
by danb
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.

Re: FP

Posted: Sun Jan 25, 2009 12:01 pm
by ramarren
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.