lisp - LISP：如何获得列表的运行总和？（没有全局变量）

Question

我是 LISP 新手。

为了得到一个列表的总和，我写的是——

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

例如，如果您'(1 2 3 4)作为输入给出，上面的代码将'(1 3 6 10)作为输出返回，依此类推。

是否可以在不使用全局变量的情况下（以更优雅的方式）做同样的事情sum？

Answer 1

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

scanl是单线：

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

Answer 2

你可以loop像这样使用：

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

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

它本质上是一样的，但它使用局部变量而不是全局变量，并且可能更清楚。

或者，您可以定义一个递归函数和一个包装函数：

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

loop然而，当可用时，这对我来说似乎是不必要的复杂。

请注意，在 Haskell 中，您可以像这样进行运行总和：

runningSum xs = scanl1 (+) xs

runningSum [1, 2, 3, 4]

这里的关键是scanl1函数。Lisp 中可能存在类似的东西（我们现在几乎写了两次），但我有一段时间没有使用 Lisp。

编辑：经过一番搜索，我不认为 Common Lisp 包含任何类似scanlor的东西scanl1，所以它们是：

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

编辑：感谢怀远关于如何缩短循环的建议的回答。

Answer 3

或者你可以使用高阶函数

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

Answer 4

Haskell 确实有丰富的列表递归函数清单，但我们reduce至少有。这是一个基本的（即没有loop魔法的）功能解决方案：

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

我使用原始列表的头部作为初始值并遍历列表的其余部分，在头部添加总和（因为在头部添加是很自然的），最后反转由此获得的列表。

reduce在大多数情况下，当需要遍历一个累积值的序列时，可以使用它。

这是使用push-nreverse成语的基本迭代解决方案：

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

Answer 5

在方案中，我将使用累加器递归地计算列表的总和。像这样：

; 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) '()))))

输出：

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

递归列表的诀窍是每次取出第一个元素/汽车并传递其余/cdr。您可以通过使用额外的参数（称为累加器）来保留中间结果并在其中传递总和。我在上面使用了两个累加器：一个用于最后一个总和，一个用于所有先前总和的列表。

我从来没有在 LISP 中做过任何事情，所以我不知道这是否直接转化为你的方言（？），但它在概念上很简单，我相信它在 LISP 中也是可行的。

一定要问是否有什么事情不是很清楚。自从我使用这一系列语言以来已经有一段时间了:)