sicp-ex-2.33

  
 ;; Ex 2.33 
  
 ;; 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))))) 
  
  
 (define nil '())  ;; stupid environment ... 
  
 ;; a. map 
  
 (define (my-map proc sequence) 
   (accumulate (lambda (first already-accumulated) 
                 (cons (proc first) already-accumulated)) 
               nil 
               sequence)) 
  
 ;; Test: 
  
 (my-map square (list)) 
 (my-map square (list 1 2 3 4)) 
  
  
 ;; b. append 
  
 (define (my-append list1 list2) 
   (accumulate cons 
               list2 
               list1)) 
  
 ;; Test: 
  
 (append (list 1 2 3) (list 4 5 6))  ;; checking order. 
 (my-append (list 1 2 3) (list 4 5 6)) 
  
  
 ;; c. length 
  
 (define (my-length sequence) 
   (accumulate (lambda (first already-acc) 
                 (+ 1 already-acc)) 
               0 
               sequence)) 
  
 ;; Test: 
 (length (list 1 2 3 (list 4 5))) 
 (my-length (list 1 2 3 (list 4 5))) 
  
  

  
 (define (map p sequence) 
   (accumulate (lambda (x y) (cons (p x) y)) '() sequence)) 
  
 (define (append seq1 seq2) 
   (accumulate cons seq2 seq1)) 
  
 (define (length sequence) 
   (accumulate (lambda (x y) (+ 1 y)) 0 sequence)) 
  

This map can also used in tree.

  
 (define (map p sequence) 
   (accumulate (lambda (x y) 
                 (cons (if (not (pair? x)) 
                           (p x) 
                           (map p x)) 
                       y)) 
               nil 
               sequence)) 
  
 ;;Test: 
  
 (define a (list 1 (list 9 8) 3)) 
 (map (lambda (x) (* x x)) a) 
  
  
  

IMO the trickiest thing about these accumulate problems is how accumulates works. To that end I like to remind myself by starting each problem with an expaanded evaluation of accumulate, for a 2 item sequence:

  
 ;; accumulate for 2 item seq: (op (car seq) (op (car (cdr seq)) initial)) 
  
 (define (append list1 list2) 
   (accumulate cons list2 list1)) 
  
 ;; expands to: 
 ;; (cons (car list1) (cons (car (cdr list1)) list2)) 
  
  

It helped me to realize what accumulate translates to:

  
 ;; (accumulate op init (list 1 2 3) 
  
 ;; (op 1 (op 2 (op 3 init))) 
  

vs. what map translates to:

  
 ;; (map op (list 1 2 3)) 
  
 ;; (cons (op 1) (cons (op 2) (cons (op 3)))) 
  

and hence map in terms of accumulate would be:

  
 (define (map op seq) 
   (accumulate (lambda (next-ele mapped-seq) 
                 (cons (op next-ele) mapped-seq)) 
               '() 
               seq))