带有所有中间值的列表的总和

Question

我正试图计算列表中所有中间值的总和。我的代码如下，但它不起作用。

(: sums : (Listof Integer) -> (Listof Integer)) 
;; compute the sum of a list, 
;; produce all the intermediate sums along the way 
;; start with 0 
;; (sums (list 1 2 3 4)) ==> (list 0 1 3 6 10) 
(define (sums x) 
    (match x 
    ('() (list 0)) 
    ((cons hd '()) (append (list 0) (list (+ 0 hd)))) 
    ((cons hd (cons a b)) 
    (append (list 0) (list (+ 0 hd)) (list (+ 0 hd a))) (sums (cons a b))))) 

我从我自己的家里学习球拍，所以任何和所有的帮助将不胜感激！

Answer 1

所以你要编写一个函数，使得

(sums (list))  = (list 0) ;; Your implementation has this right 
(sums (list x))  = (list 0 x)     = (list      0    (+ x 0)) 
(sums (list y x)) = (list 0 y (+ y x))   = (list  0  (+ y 0)  (+ y (+ x 0))) 
(sums (list z y x)) = (list 0 z (+ z y) (+ z y x)) = (list 0 (+ z 0) (+ z (+ y 0)) (+ z (+ y (+ x 0)))) 

等（我用非常暗示的名称，加括号和布局在这里，你会看到为什么）。

请注意，所有结果列表都以0开头，其余与前一行的结果相同，除了第一个输入项添加到每个后续项目中。

换句话说，我们有

(sums (car x items)) = (cons 0 (add-to-each x (sums items))) 

所以首先你需要实现

(: add-to-each : Integer -> (Listof Integer)) 
(define (add-to-each x items) 
    ...) 

，然后使用在sums实施。为了实现add-to-each，我们需要注意的是

(add-to-each x     ()) =        () 
(add-to-each x (cons y1   ())) =    (cons (+ x y1)()) 
(add-to-each x (cons y2 (cons y1())) = (cons (+ x y2) (cons (+ x y1)())) 

等等。

因为你说你正在做这件事来学习球拍，我会在这里停下来，看看你能否从这里弄明白。

Answer 2

下面是一个简单尾递归溶液与成本线性与列表的大小：

(define (sums l) 
    (define (subsums prefix l) 
    (if (null? l) 
     (reverse prefix) 
     (subsums (cons (+ (car prefix) (car l)) prefix) (cdr l)))) 
    (subsums '(0) l)) 

(sums '(2 5 3)) ; => (0 2 7 10) 

辅助功能subsums给出部分和列表迄今与列表中仍然要被处理。它将第一个参数的第一个元素和列表的第一个元素相加，并且遍历它和列表的其余部分。最后，颠倒的第一个参数是预期的结果。

Answer 3

这是另一种使用延续传球风格的解决方案。它还使用尾递归并使用线性迭代过程在恒定时间内运行。它使用lambda作为代表不完整答案的累加器来构建结果列表。一旦所有xs已迭代通过，我们将累加器应用到最后的总和s - 当然，同时还要留意与empty终止列表。这个解决方案特别好，因为我们完成后不需要扭转答案。

(define (sums xs) 
    (let loop ((s 0) (xs xs) (k identity)) 
    (if (empty? xs) 
     (k (cons s empty)) 
     (loop (+ s (car xs)) (cdr xs) (λ (rest) (k (cons s rest))))))) 

(sums '(1 2 3 4)) 
; => '(0 1 3 6 10) 

---

我们是聪明的芹苴，我们看到，我们的λ表达只是k和cons功能组成。我们可以把它改写这样

(define (sums xs) 
    (let loop ((s 0) (xs xs) (k identity)) 
    (if (empty? xs) 
     (k (cons s empty)) 
     (loop (+ s (car xs)) (cdr xs) (compose k (curry cons s)))))) 

(sums '(1 2 3 4)) 
; => '(0 1 3 6 10) 

Answer 4

以下是另一种：

(define (sums l) 
    (let loop ((l l) 
      (sl '(0))) 
    (if (empty? l) (reverse sl) 
     (loop (rest l) 
       (cons 
       (+ (first l) 
        (first sl)) 
       sl) 
      )))) 

测试：

(sums (list 1 2 3 4)) 

输出：

'(0 1 3 6 10) 

Answer 5

通常更容易解决更广泛的问题：概括，解决mor e一般，然后专门回到你原来的问题。

在伪代码中，

partial-sums (x . xs) = [ 0 x ... ] 
         = (0 . [x ...]) 
         = (0 . partial-sums-from (0 + x) xs) 
         = partial-sums-from 0 (x . xs) 

因此partial-sums-from可以被实现为一个递归函数。

结果列表，也可重复建，在top-down manner（参见this），由副作用的左折叠执行cons之前递归调用，因为每tail-recursion-modulo-cons学科（另见tailrecursion-modulo-cons），使它不仅在线性时间运行，而且在恒定空间运行，不像其他所有变体。