newbie: can this be done better (and how)?

[Josip Krapac]

pos+ takes a list and returns a list of each element plus its position:

(pos+ '(7 5 4 1))
(7 6 3 7)

;; recursive version

(defun pos+ (lst)
(if (null lst)
nil
(h-pos+ lst 0 nil)))

(defun h-pos+ (lst pos new-lst)
(if (null lst)
(reverse new-lst)
(progn
(setf new-lst (cons (+ (car lst) pos) new-lst))
(h-pos+ (cdr lst) (+ pos 1) new-lst))))

;; iterative version

(defun pos+ (lst)
(if (null lst)
nil
(let ((pos 0) (new-lst nil))
(dolist (obj lst)
(setf new-lst (cons (+ obj pos) new-lst))
(setf pos (+ pos 1)))
(reverse new-lst))))

My versions look too complicated to me, and I think this can be done
better.

What is better (faster) to use in this case: iteration or recursion?

Thanks,

Josip

[Vladimir Zolotykh]

Vladimir Zolotykh wrote:
>
> (mapcar #'(lambda (i) (print j) (prog1 (+ i j) (incf j))) list)))
Ignore (print j) there please.

--
Vladimir Zolotykh

[Vladimir Zolotykh]

Josip Krapac wrote:
>
> pos+ takes a list and returns a list of each element plus its position:

(defun pos+ (list)
(let ((j 0))

(mapcar #'(lambda (i) (print j) (prog1 (+ i j) (incf j))) list)))

(defun pos+ (list)
(loop
for i in list
for j from 0
collecting (+ i j)))

--
Vladimir Zolotykh

[Wolfgang Goerigk]

;; Here is a version I'd prefer. It takes atoms as NIL, i.e.
;; (pos+ '(a b c)) = ((a . 0) (b . 1) (c . 2)) = (pos+ '(a b c . d))

(defun hpos+ (lst n)
(if (not (consp lst))
nil
(cons (cons (car lst) n) (hpos+ (cdr lst) (1+ n)))))

(defun pos+ (lst) (hpos+ lst 0))

Iteration might sometimes be a bit more efficient, but is definitely
less transparent.

Regards,

-- Wolfgang

[Erik Naggum]

* Josip Krapac

| What is better (faster) to use in this case: iteration or recursion?

Since you ask in a Common Lisp question, here is a non-Scheme answer:

(loop for pos upfrom 0 for elt in <list> collect (+ pos elt))

You can call a variable "list" in Common Lisp, although Scheme forces you
to use stupid, unreadable things like "lst" because it used up "list".

In general, you should pretend you never learned, never even saw Scheme
if you want to succeed in learning Common Lisp. What you have learned of
Scheme is actually harmful to your ability to learn Common Lisp.

For instance, (setf pos (+ pos 1)) is written (incf pos) in Common Lisp.
(setf new-list (cons (+ obj pos) new-list)) is written (push (+ obj pos)
new-list).

///
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.

[David Sletten]

Josip Krapac wrote:

Here's a recursive version similar to yours (note that this only does
partial input validation--it doesn't check that all elements are numbers):

(defun pos+ (list)
(if (null list)
nil
(pos-aux list 0)) )

(defun pos-aux (list pos)
(cond ((null list) ())
(t (cons (+ pos (car list))
(pos-aux (cdr list)
(1+ pos)))) ) )

Here's a tail-recursive version. You can encapsulate the auxiliary

function using LABELS (this version validates the input before ever

calling the recursive function):

(defun pos+ (list)
(labels ((pos-aux (list pos result)
(cond ((null list) (reverse result))
(t (pos-aux (cdr list)
(1+ pos)
(cons (+ (car list) pos)
result)))) ) )
(if (and list (every #'numberp list))
(pos-aux list 0 ())
nil)) )

Note:
You can avoid the PROGN in your IF form by switching to COND, which
establishes an implicit PROGN for each clause:

(cond ((null lst) (reverse new-lst))
(t (setf new-lst (cons (+ (car lst) pos) new-lst))

(h-pos+ (cdr lst) (+ pos 1) new-lst)))

Or using some of Erik's suggestions for more natural Common Lisp:

(cond ((null list) (reverse new-list))
(t (push (+ (car list) pos) new-list)
(h-pos+ (cdr list) (1+ pos) new-list)))

However, notice in my second example that you don't need to assign any
values to NEW-LIST. Just pass the expression representing the updated
version as an arg to the recursive call.

David Sletten

P.S. You copied the example incorrectly from Graham's book. It should be:
(pos+ '(7 5 1 4))
(7 6 3 7)

vs. (pos+ '(7 5 4 1)) => (7 6 6 4)

[Thomas A. Russ]

Josip Krapac <josip....@fsb.hr> writes:

> pos+ takes a list and returns a list of each element plus its position:
>
> (pos+ '(7 5 4 1))
> (7 6 3 7)

;; Huh?? Is this supposed to be an example of the output?

> ;; recursive version
>
> (defun pos+ (lst)
> (if (null lst)
> nil
> (h-pos+ lst 0 nil)))
>
> (defun h-pos+ (lst pos new-lst)
> (if (null lst)
> (reverse new-lst)
> (progn
> (setf new-lst (cons (+ (car lst) pos) new-lst))
> (h-pos+ (cdr lst) (+ pos 1) new-lst))))

For starters, you don't need to use the SETF form. A more lisp-ish way
of writing this function would be:

(defun h-pos+ (lst pos new-lst)
(if (null lst)
(reverse new-lst)

(h-pos+ (cdr lst)
(+ pos 1)

(cons (+ (car lst) pos) new-lst))))

If you want to do it in just one function, you can use labels to define
the helper function inside:

(defun pos+ (lst)
(labels ((h-pos+ (lst pos new-lst)
(if (null lst)
(nreverse new-lst) ;; Destructive version!

(h-pos+ (cdr lst)
(+ pos 1)

(cons (+ (car lst) pos) new-lst)))))
(h-pos+ lst 0 nil)))

> ;; iterative version
>
> (defun pos+ (lst)
> (if (null lst)
> nil
> (let ((pos 0) (new-lst nil))
> (dolist (obj lst)
> (setf new-lst (cons (+ obj pos) new-lst))
> (setf pos (+ pos 1)))
> (reverse new-lst))))

I, personally, am a Loop fan:

(defun pos+ (lst)
(loop for obj in lst
as pos upfrom 0
collect (+ pos obj)))

> My versions look too complicated to me, and I think this can be done
> better.

> What is better (faster) to use in this case: iteration or recursion?

I depends. Some compilers will optimize tail recursive calls (like in
h-pos+) to be essentially the same as iteration.

> Thanks,
>
> Josip
>

Of course, there are some silly versions as well:

(defun integers-below (n)
(loop for i from 0 below n collect i))

(defun pos+ (lst)
(mapcar #'+ lst (integers-below (length lst))))

;; or an alternate versions for integers-below:

(defun integers-below (n)
(let ((v (- n 1))
(result nil))
(dotimes (i n)
(declare (ignore i))
(push (decf v) result))
result))

--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu