CODEWITHSUNDEEP
listschememap-functionaccumulate
Christopher Kelly
Christopher Kelly

Reputation: 117

Implementing "Accumulate" Function in Scheme

I've been hung on trying to implement an Accumulate function for a couple weeks, now. I have properly implemented a "Map" function, that iterates across a list and runs a function on each element.

I am using this function to implement "Accumulate"

   (define accumulate
  (lambda (op base func ls)
    (if(null? ls)
       ls
   (cond (not (null? (cdr ls)) (op base (map func ls) (accumulate op base func (cdr ls))))
       (op base (map func ls) (op base (func(car ls))))
   )
     )))
    ;It gets to a point (the last element) after applying the map function to each element,
    ;where it is '(number) instead of an expected "number" (outside of () ). I cannot figure out
    ;how to circumvent this.

I'm stuck on how to get this right. What is the right way to do this?

The intended result is:

; accumulate: combines using OP the values of a list LS after mapping a function FUNC on it
;    (accumulate + 0 sqr '(1 2 3)) => 14
;    (accumulate * 1 sqr '(1 2 3)) => 36
;

Upvotes: 0

Views: 3868

Answers (2)

Will Ness
Will Ness

Reputation: 71075

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

Upvotes: 1

Óscar López
Óscar López

Reputation: 236034

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

Upvotes: 3

Related Questions