Better way to convert weights to range using map or fold?

Question

Is there a shorter ⁄ better way of writing the following? There's probably some library that does the conversion but I am wondering if some kind of map or fold could work?

(define (weights-to-range lw)
  ; '(1 4 6 6 6 6 6) -> (1 5 11 17 23 29 35)
    (define (f x lw acc)
    (if (null? lw)
        acc
        (let ([y (+ x (car lw))])
          (f y (cdr lw) (append acc (list y))))))
  (f (car lw) (cdr lw) (list (car lw))))

Answer 1

In Racket I would probably write it using the for/fold list comprehension:

(define (weights-to-range weights)
  (define-values (xs _)
    (for/fold ([xs '()] [prev 0])
              ([weight (in-list weights)])
      (define this (+ prev weight))
      (values (cons this xs) this)))
  (reverse xs))

(require rackunit)
(check-equal? (weights-to-range '(1 4 6 6 6 6 6))
              '(1 5 11 17 23 29 35))

It would be even simpler except that, since this supplies two accumulation values to the fold/fold -- xs and prev -- the for/fold form is going to return two values. So we need to tuck both into temporary vars using define-values, before passing the one we care about -- from xs -- to reverse. (The var for prev is named _. That's just a convention meaning "ignored", because we don't need it.)

---

Of course, the general idea here is to "fold" a list using a "sliding window" of pairs, with the cumulative result so far available to each step. In your case, the function is +, but it could be generalized:

(define (fold-slide f vs)
  (define-values (xs _)
    (for/fold ([xs '()] [prev 0])
              ([v (in-list vs)])
      (define this (f prev v))
      (values (cons this xs) this)))
  (reverse xs))

With such a fold-slide (for lack of a better name) function, you could have written simply:

(fold-slide + '(1 4 6 6 6 6 6)

Such a fold-slide might be even more useful if it could handle "windows" of any size, not just 2.

p.s. It's entirely possible there is some SRFI that does something like this, or a more-elegant way to do it in Racket, that I don't know.

Answer 2

It's perfectly fine to have an accumulator while still building your answer directly (that is, instead of accumulating a reversed answer and then reversing it at the end).

;; weights-to-range : (listof number) -> (listof number)
;; Returns list of partial sums of input list.
(define (weights-to-range lw0)

  ;; helper : (listof number) number -> (listof number)
  ;; acc is the sum of elements seen so far
  (define (helper lw acc)
    (cond [(null? lw)
           null]
          [else
           (let ([new-acc (+ acc (car lw))])
             (cons new-acc (helper (cdr lw) new-acc)))]))

  (helper lw0 0))