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 ?

Levantine

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

Regenerative

Ah, you're right that the loop can be tightened up a bit. +1 vote. I would suggest, however, that since init is no longer being used as merely the initial value, but also the current value, that the name be changed to reflect that. value, val, or v perhaps? – Impi

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.

Impi

thanks, the scanl1 looks very interesting, I was wondering if something similar is available in LISP as well. – Levantine

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

Anaerobic

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

Bruns

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 :)

Odds

You might want to reverse the list before returning. – Anaerobic

@Anaerobic to be honest I thought it was obvious enough to leave out and save a line in the example code :) but yeah, the result is reversed – Odds

Sorry, that's just natural programmer pedanticism :) – Anaerobic