sicp-ex-2.36

Accumulate-n.

Given a sequence of sequences, applies accumulate to the first item from each, then the next item of each, etc.

Subproblem: define a proc that returns the first item from each nested sequence, and another that returns the remaining parts (accumulate-n will accumulate the former, and call itself with the latter):

  
 (define (select-cars sequence) 
   (map car sequence)) 
  
 (define (select-cdrs sequence) 
   (map cdr sequence)) 
  
 ;; Test 
 (define t (list (list 1 2 3) (list 40 50 60) (list 700 800 900))) 
 (select-cars t) 
 (select-cdrs t) 
  
  
 ;; Accumulates the result of the first and the already-accumulated 
 ;; rest. 
 (define (accumulate op initial sequence) 
   (if (null? sequence) 
       initial 
       (op (car sequence) 
           (accumulate op initial (cdr sequence))))) 
  
  
 ;; accumulate-n 
 (define (accumulate-n op init sequence) 
   (define nil '()) 
   (if (null? (car sequence)) 
       nil 
       (cons (accumulate op init (map car sequence)) 
             (accumulate-n op init (map cdr sequence))))) 
  
 ;; Usage: 
 (accumulate-n + 0 t) 
  

Originally I had (map (lambda (s) (car s)) sequence), but (lambda (s) (car s)) is just a function that returns car ...

But (lambda (s) (car s)) does not return car (the procedure) but the car of a pair. The notation (lambda (s) (car s)) shows the used operation in the mapping process more explicit.

  
 (define (accumulate-n op init seqs) 
   (if (null? (car seqs)) 
       nil 
       (cons (accumulate op   init (map (lambda (s) (car s)) seqs)) 
             (accumulate-n op init (map (lambda (s) (cdr s)) seqs))))) 
  
  
 ;Maybe a helpful stepping stone. 
 ;Example in Mit-Scheme: 
 ;(user) => (map (lambda (s) (cdr s)) '((1 2 3) (4 5 6))) 
 ;Value: ((2 3) (5 6)) 

I would first like to set the record straight: (lambda (s) (car s)) is just a substitute for car (the procedure), it is not an expression in and of itself which is evaluated otherwise this would violate the requirement of the map function, the first argument of which has to be proc (a procedure).

Anyway, using a map was not intuitive to me in this case while writing the solution (though it is in retrospect), hence the following solution:

  
 (define (accumulate-n op init seqs) 
   (if (null? (car seqs)) '() 
       (cons (accumulate op init (append-first seqs)) (accumulate-n op init (append-rest seqs))))) 
  
 ;auxiliary functions 
  
 ;append the first element of each sub-list in seqs 
 (define (append-first seqs) 
   (define (iter items res) 
     (if (null? items) 
         res 
         (iter (cdr items) (cons (car (car items)) res)))) 
   (reverse (iter seqs '()))) 
  
 ;append the cdr of each sub-list in seqs 
 (define (append-rest seqs) 
   (define (iter items res) 
     (if (null? items) 
         res 
         (iter (cdr items) (cons (cdr (car items)) res))) 
   )  
   (reverse (iter seqs '()))) 
  
 (define (reverse items) 
   (define (iter z res) 
     (if (null? z) 
         res 
         (iter (cdr z) (cons (car z) res)))) 
   (iter items '()))