Cannot do sum in lisp with do loop

问题:

(defun suma (L)
  (setq var 0)
  (do 
      ((i 0 (+ i 1)))
      ((= i (length L)))
    (+ var (nth i L)))
  var)

Why does it always returns 0?

Shouldn't it return sum of list L?

回答1:

+ does not modify its arguments, so, since you never modify var, its initial value of 0 is returned.

You need to replace (+ var (nth i L)) with (incf var (nth i L)), of, equivalently, (setq var (+ var (nth i L))).

See incf.

Note that you should bind var with let instead of making it global with setq.

Most importantly, note that your algorithm is quadratic in the length of the list argument (because nth scans your list every time from the start).

Here are some better implementations:

(defun sum-1 (l)
  (reduce #'+ l))

(defun sum-2 (l)
  (loop for x in l sum x))

(defun sum-3 (l)
  (let ((sum 0))
    (dolist (x l sum)
      (incf sum x))))

Here is a bad implementation:

(defun sum-4 (l)
  (apply #'+ l))

The problem with sum-4 is that it will fail if the length of the supplied list is larger than call-arguments-limit.

回答2:

I thought this would be a comment for the full learning experience, but I was not able to put code in the comment.

There is a way to do sums without modifying any argument, and that is by doing it recursively:

(defun recsum (list)
  (if list
      (+ (first list) (recsum (rest list)))
      0))

This version can be tail call optimized by the compiler, and as fast as a loop:

(defun recsum2 (list &optional (accumulator 0))
  (if list
      (recsum2 (rest list) (+ accumulator (first list)))
      accumulator))

What you are trying to do could be done with do like this:

(defun suma (l)
  (do 
   ((var 0)
    (i 0 (+ i 1)))
   ((= i (length l)) var)
    (incf var (nth i l))))

But we don't usually do anything in dos body, so it's like this then:

(defun suma (l)
  (do
   ((i 0 (+ i 1))
    (var 0 (+ var (nth i l))))
   ((= i (length l)) var)))

But nth and length are slow, so better do it this way:

(defun suma (l)
  (do* 
   ((var (first l) (+ var (first list)))
    (list (rest l) (rest list)))
   ((null list) var)))

This one is without the * in do, and returns 0 on empty list:

(defun suma (l)
  (do 
   ((acc 0 (+ acc (first list)))
    (list l (rest list)))
   ((null list) acc)))

But my favorite is the reduce version from @sds which also can return 0 on empty list with :initial-value 0

EDIT: recsum2 did not return anything, so it needed a fix.