listrecursionschemeracketsubtotal

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


Trying to do this '(3 2 1) -> '(6 3 1) with accumulative recursion I can get the result (sort of) that I desire, what I mean is that my firsts and rests seem to be in the right order but my (cons expects a list and I give it a number. Any help is appreciated.

If I replace (cons with (list in the helper and I (reverse the li variable in the function I get the '(6 3 1) that I would like but with (list (list (list '() in front. I would just like '(6 3 1)

This is what I have

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

Running (subtotal li) produces '(((() 6) 3) 1), and with cons is produces '(((() . 6) . 3) . 1). I need just '(6 3 1).


Solution

  • You should use cons to build an output list, not list. Your code is close to being correct, we just need to shuffle things around and add one extra reverse at the end:

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

    But if you really want a tail-recursive solution, then it takes a bit more of work:

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

    Either way, it works as expected:

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