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

Question

尝试执行此'(3 2 1)->具有累积递归的'(6 3 1)我可以得到我想要的结果(有点(，我的意思是，我的第一次和休息似乎顺序正确，但我的(cons需要一个列表，我给它一个数字。感谢您的帮助。

如果我在助手中将(cons替换为(list，并将(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))]))

运行(subtotal li)产生'(((() 6) 3) 1)，使用cons产生'(((() . 6) . 3) . 1)。我只需要'(6 3 1)。

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

奥斯卡·洛佩斯的好答案回答了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，那么可以定义尾部递归过程的更简洁版本。这里，由于中间结果是cons，所以累加器必须在末尾反转：

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

Answer 3

放松显式递归位，以从右到左的顺序遍历列表(并以相同的顺序构建新列表(的一种自然方法是使用右折叠(通常使用递归实现，尽管这对调用方是隐藏的(。

使用for/foldr:的示例

(define (subtotal lst)
(for/foldr ([total 0]
[totals '()]
#:result totals)
([n (in-list lst)])
(let ([new-total (+ total n)])
(values new-total (cons new-total totals)))))

或者如果您更喜欢foldr而不是for宏：

(define (subtotal lst)
; Use the first element of the accumulated list to hold the current running total
; And discard it at the end
(cdr (foldr (lambda (n totals)
(let ([new-total (+ (car totals) n)])
(list* new-total new-total (cdr totals))))
'(0) 
lst)))