累积递归函数以生成从最后到第一的小计列表

Question

尝试使用累积递归来做到这一点 '(3 2 1) -> '(6 3 1) 我可以得到我想要的结果（某种程度上），我的意思是我的第一次和休息似乎顺序正确，但我的 (cons 需要一个列表，我给它一个数字。感谢任何帮助。

如果我在助手中用 (list 替换 (cons 并且我 (reverse 函数中的 li 变量我得到 '(6 3 1) 我会喜欢，但前面有 (list (list (list '()。我只想 '(6 3 1)

这就是我的

(define (subtotal li)
  (subtotal-help (reverse li) 0))

(define (subtotal-help li acc)
  (cond
    [(empty? li) empty]
    [else  (list (subtotal-help (rest li)
                    (+ (first li) acc))
             (+ (first li) acc))]))

Answer 1

您应该使用 cons 来构建输出列表，而不是 list。您的代码接近正确，我们只需要打乱顺序并在末尾添加一个额外的 reverse：

(define (subtotal li)
  (reverse
   (subtotal-help (reverse li) 0)))

(define (subtotal-help li acc)
  (cond
    [(empty? li) empty]
    [else (cons (+ (first li) acc)
                (subtotal-help (rest li) (+ (first li) acc)))]))

但是如果你真的想要一个尾递归解决方案，那么它需要更多的工作：

(define (subtotal li)
  (cond
    [(empty? li) empty]
    [else (let ((lst (reverse li)))
            (subtotal-help (rest lst) (list (first lst))))]))

(define (subtotal-help li acc)
  (cond
    [(empty? li) acc]
    [else (subtotal-help (rest li)
                         (cons (+ (first li) (first acc))
                               acc))]))

无论哪种方式，它都按预期工作：

(subtotal '(3 2 1))
=> '(6 3 1)

Answer 2

@ÓscarLópez 的精彩回答回答了 OP 的直接问题，但还有其他方法可以解决问题，这可能不是 OP 的教授正在寻找的。

可以 map 遍历输入列表以及列表中的一系列索引，使用 drop 减少每个 apply 的列表，从而对剩余列表求和。这里 _x 是 map 从输入列表中取出的（忽略的）值， n 是 drop 的元素数， xs 是输入名单：

(define (subtotal-list xs)
  (map (lambda (_x n)
         (apply + (drop xs n)))
       xs
       (range (length xs))))

scratch.rkt> (subtotal-list '(3 2 1))
'(6 3 1)
scratch.rkt> (subtotal-list '())
'()

顺便说一下，Common Lisp 有一个很好的惯用语来处理这种事情，它使用 LOOP 宏来类似地工作。这里 x 不是列表 xs 中的元素，而是整个列表，并且在每次迭代中 x 通过使用 cdr （默认情况下）减少：

(defun subtotal-list-cl (xs)
  (loop
     :for x :on xs
     :collect (apply #'+ x)))

SCRATCH> (subtotal-list-cl '(3 2 1))
(6 3 1)
SCRATCH> (subtotal-list-cl '())
NIL

回到手头的任务，如果需要迭代辅助程序，并且允许 apply，则可以定义尾递归程序的更简洁版本。这里，由于中间结果被consed到累加器的前面，所以最后累加器必须反转：

(define (subtotal-list-iter xs)
  (subtotal-list-helper xs '()))

(define (subtotal-list-helper xs acc)
  (if (null? xs) (reverse acc)
      (subtotal-list-helper (rest xs)
                            (cons (apply + xs) acc))))

scratch.rkt> (subtotal-list-iter '(3 2 1))
'(6 3 1)
scratch.rkt> (subtotal-list-iter '())
'()

累积递归函数以生成从最后到第一的小计列表

accumulative recursive function to produce a list of subtotals from last to first

scheme

racket