带有所有中间值的列表的总和
我正试图计算列表中所有中间值的总和。我的代码如下,但它不起作用。带有所有中间值的列表的总和
(: 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)))))
我从我自己的家里学习球拍,所以任何和所有的帮助将不胜感激!
所以你要编写一个函数,使得
(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)()))
等等。
因为你说你正在做这件事来学习球拍,我会在这里停下来,看看你能否从这里弄明白。
谢谢!这解决了它!我很困惑,因为每个人都应该这样做。但现在我已经开始工作了!非常感谢你! – testomg
请注意,在实际代码中,您可以使用['map']编写'add-to-each'(https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib ._racket%2Fprivate%2Fmap..rkt%29._map%29%29)而不是自己为教育目的重写它;即你会写'(cons 0(map(lambda(y)(+ x y)))(summs items))'。 – Cactus
在这一点上,你会使用['foldl'](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket)来编写'sums' %2Fprivate%2Flist..rkt%29._foldl%29%29)或['foldr'](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib。 _racket%2Fprivate%2Flist..rkt%29._foldr%29%29)而不是直接递归。 – Cactus
下面是一个简单尾递归溶液与成本线性与列表的大小:
(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
给出部分和列表迄今与列表中仍然要被处理。它将第一个参数的第一个元素和列表的第一个元素相加,并且遍历它和列表的其余部分。最后,颠倒的第一个参数是预期的结果。
这是另一种使用延续传球风格的解决方案。它还使用尾递归并使用线性迭代过程在恒定时间内运行。它使用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)
这会在沿着列表向前的路上构建一个* n *嵌套lambda表达式链,然后应用最后一个lambda表达式将导致结果列表从结尾(即,* backward * direction)以正确的顺序构建,就像嵌套'cons'电话会这样做。所以它是线性空间和时间(当然,不包括结果列表的* n * cons单元格)。但是,TRMC解决方案实际上是从顶部以* forward *方向,即从其头部以O(1)空间开销构建结果列表。 –
以下是另一种:
(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)
通常更容易解决更广泛的问题:概括,解决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),使它不仅在线性时间运行,而且在恒定空间运行,不像其他所有变体。
而不是'(append(list 0)..)',使用'(cons 0 ...)'。 – Cactus
你在最后一行中有错误的括号。最后一个表达式是'(summs(cons a b))','append'表达式不起作用。 (和btw'(追加(列表a)(列表b)(列表c))'与(列表abc)'相同。) –
但是,你的方法不可能工作,因为你总是从0开始,但递归调用应该从更新的中间和值开始。这种计算称为*部分和*(并且在例如Haskell中被抽象为高阶函数'scanl')。 –