Implementing "Accumulate" Function in Scheme

Show Details

Solution 1: [1]

You want to implement a folding procedure that works for a list, you don't need to use map, simply process each element in turn. This is more like it:

(define accumulate
  (lambda (op base func ls)
    (if (null? ls)
        base
        (op (func (car ls))
            (accumulate op base func (cdr ls))))))

For example:

(accumulate + 0 sqr '(1 2 3))
=> 14

(accumulate * 1 sqr '(1 2 3))
=> 36

Solution 2: [2]

You can implement your accumulate with map,(1) for fun and no profit:

(define (accumulate op base func ls)
  (define (butlast xs) 
      (reverse (cdr (reverse xs))))
  (let ((xs (map list ls)))       ; box'em up
    (for-each
       (lambda (a1 x)
         (let ((a2  (op (car a1) (func (car x))) ))
            (set-car! x a2)))
       (butlast (cons (list base) xs))
       xs)
    (caar (reverse xs))))         ; last

(display (accumulate + 0 (lambda (x) (* x x)) (list 1 2 3 4)))

;   0 1 5 14
;   1 2 3 4   => 30
; 0 1 5 14

(1)(well, for-each, which is largely similar to map but ensures the left-to-right order of function application across the argument lists, which is essential here... or we could use map-in-order from SRFI-1 which has the additional advantage that calling butlast becomes unnecessary).

This emulates (with the obvious twist), in R5RS Scheme, the old-time lazy stream programming definition of

accumulate op base ls  =  last xs
  where
      xs = [base, ...map op xs ls]

~> accumulate (+) 0 (map (^2) [1,2,3,4])
30
  
;;   0 a b c d   +
;;   1 4 9 16    =    d
;; 0 a b c d

(in pseudocode) which also "writes" the accumulated result at one-past-current list node, as it moves along the lists. This is actually known as scanl in e.g. Haskell, and taking the last result from that list makes it foldl (the left fold).



Credits

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Credit
Solution 1 Óscar López
Solution 2 Will Ness