Сумма списка со всеми промежуточными значениями

Итак, вы хотите написать функцию, которая

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

и так далее.

Поскольку вы говорите, что делаете это, чтобы выучить Racket, я остановлюсь здесь и посмотрю, сможете ли вы понять это отсюда.

Вот простое хвост-рекурсивное решение со стоимостью, линейной по размеру списка:

(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 получает список частичных сумм на данный момент и список, который еще предстоит обработать. Он объединяет первый аргумент с суммой своего первого элемента и первого элемента списка и повторяется по нему и остальной части списка. В конце перевернутый первый аргумент является ожидаемым результатом.

Вот еще одно решение, в котором используется стиль передачи продолжения. Он также использует хвостовую рекурсию и работает за постоянное время с использованием линейного итеративного процесса. Он строит результирующий список в прямом направлении, используя лямбду в качестве аккумулятора, представляющего неполный ответ. После того, как все 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)

Ниже приводится альтернатива:

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

Часто проще решить более широкую проблему: обобщить, решить более общую, а затем вернуться к исходной проблеме.

В псевдокоде,

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

Таким образом, partial-sums-from можно реализовать как рекурсивную функцию.

Результирующий список также может быть построен итеративно, в сверху вниз (см. это), путем побочного действия левого сгиба, выполняющего cons перед рекурсивным вызовом согласно хвостовой рекурсии -modulo-cons дисциплина (см. также tailrecursion-modulo-cons), так что он работает не только в линейном времени, но и в постоянном пространстве, в отличие от всех остальных вариантов.