my attempt to do the exercises in sicp.

Thursday, July 17, 2008

sicp exercise 2.35

;  Exercise 2.35. Redefine count-leaves from section 2.2.2 as an accumulation:
;  (define (count-leaves t)
;    (accumulate <??> <??> (map <??> <??>)))

; this requires tree to be enumerated as a list and then applied in accumulate with the same operation as used in length

(define (map1 oper seq)
  (if (null? seq) (list)
      (cons (oper (car seq)) (map oper (cdr seq)))))

(define (accumulate oper init seq)
  (cond ((null? seq) init)
        (else (oper (car seq) (accumulate oper init (cdr seq))))))

(define (count-leaves1 t)
  (cond ((null? t) 0)
        ((pair? t) (+ (count-leaves1 (car t)) (count-leaves1 (cdr t))))
        (else 1)))

(define (enumerate1  tree )
  (define (enumerate1-impl subtree result)
    (cond ((null? subtree) result)
  ((pair? subtree) (enumerate1-impl (car subtree) (enumerate1-impl (cdr subtree) result)))
  (else (cons subtree result))))
  (enumerate1-impl tree (list)))

(define (enumerate2 tree)
  (cond ((null? tree) (list))
        ((pair? tree) (append (enumerate2 (car tree)) (enumerate2 (cdr tree))))
        (else (list tree))))

(define x (list (list 1 2 (list 3 (list 10)) 4 9) 20))
(display x)(newline)

(display (count-leaves1 x)) (newline)
(display (enumerate1 x )) (newline)
(display (enumerate2 x )) (newline)

(define (count-leaves2 tree)
  (accumulate (lambda(x y)(+ 1 y)) 0 (enumerate1 tree)))

(display (count-leaves2 x)) (newline)

No comments: