LISP: how to get running sum of a list? (without a global variable)

Question

I am a LISP newbie.

To get the running sum of a list, I am writing like --

(setf sum 0.0)
(mapcar #'(lambda(x)
    (setf sum (+ sum x)) sum) values))

For example, if you give '(1 2 3 4) as input, the above code returns '(1 3 6 10) as output and so forth.

Is it possible to do the same thing (in a more elegant way) without using the global variable sum ?

Answer 1

(loop for x in '(1 2 3 4) sum x into y collect y)

scanl is a oneliner:

(defun scanl (f init xs)
  (loop for x in xs collect (setf init (funcall f init x))))

Answer 2

You could use loop, like this:

(defun running-sum (xs)
  (loop with sum = 0
        for x in xs
        collect (setf sum (+ sum x))))

(running-sum '(1 2 3 4))

It's fundamentally the same thing, but it uses a local variable instead of a global one, and might be more clear.

Alternatively, you could define a recursive function, and a wrapper function:

(defun running-sum-recursive (xs)
  (running-sum-recursive2 0 xs))

(defun running-sum-recursive2 (sum xs)
  (if (eq xs nil)
    nil
    (let ((new-sum (+ sum (car xs))))
      (cons new-sum (running-sum-recursive2 new-sum (cdr xs))))))

(running-sum-recursive '(1 2 3 4))

However this seems needlessly complicated to me when loop is available.

Note that in Haskell, you could do a running sum like this:

runningSum xs = scanl1 (+) xs

runningSum [1, 2, 3, 4]

The key here is the scanl1 function. It's possible that something similar exists in Lisp (and we've very nearly written it twice now), but I haven't used Lisp in a while.

Edit: After some searching, I don't think Common Lisp includes anything quite like scanl or scanl1, so here they are:

(defun scanl (f val xs)
  (loop for x in xs
        collect (setf val (funcall f val x))))

(defun scanl1 (f xs)
  (cons (car xs)
        (scanl f (car xs) (cdr xs))))

(scanl1 #'+ '(1 2 3 4))

Edit: Thanks to huaiyuan's answer for a suggestion about how the loops could be shortened.

Answer 3

Or you could use higher-order functions

(define (running-sum ls)
     (cdr (reverse (foldl (lambda (y xs) (cons (+ (car xs) y) xs)) '(0) ls))))

Answer 4

Haskell does have a rich inventory of functions for list recursion, but we've got reduce at least. Here is an elementary (i. e. without the loop magic) functional solution:

(defun running-sum (lst)
  (reverse (reduce (lambda (acc x)
                     (cons (+ (first acc) x) acc))
                   (rest lst)
                   :initial-value (list (first lst)))))

I'm using the head of the original list as the initial value and walk through the rest of the list adding sums at the head (because it's natural to add at the head), finally reversing the list thus obtained.

One can use reduce in most cases when there's a need to traverse a sequence accumulating a value.

Here is an elementary iterative solution using the push-nreverse idiom:

(defun running-sum (lst)
  (let ((sums (list (first lst))))
    (dolist (x (rest lst))
      (push (+ x (first sums)) sums))
    (nreverse sums)))

Answer 5

In Scheme I would calculate the sum of the list recursively using an accumulator. Like so:

; Computes a list of intermediary results of list summation
(define list-sum
  (lambda (l)
    (letrec ((recsum (lambda (lst acc acclst)
      (if (pair? lst)
        (recsum (cdr lst) (+ acc (car lst)) (cons acc acclst))
        (cons acc acclst)))))
    (recsum (cdr l) (car l) '()))))

Output:

> (list-sum '(1 2 3 4))   
(10 6 3 1)
> (list-sum '(2 4 6 8 10))
(30 20 12 6 2)
> 

The trick to recurse over a list is to take the first element/car off each time and pass the rest/cdr. You can keep intermediary results by using an extra parameter (called an accumulator) and pass the sum in that. I've used two accumulators above: one for the last sum and one for a list of all previous sums.

I've never done anything in LISP, so I can't tell if this translates directly to your dialect(?), but it's conceptually simple and I'm sure it's doable in LISP as well.

Do ask if something is not immediately clear. It's been a while since I've used this family of languages :)