CSE 413 Winter 2002

Assignment 2 Sample Solution

Part I.

1.  
   1. 6
   2. 3
   3. -5
2.   
   (mystery 4)
((make-scaled 3 add-one) 4)
(((lambda (scale f) (lambda (x) (* scale (f x)))) 3 (lambda (x) (+ 1 x))) 4)
(lambda (x) (* 3 (lambda (x) (+ 1 x)) x)) 4
(* 3 ((lambda (x) (+ 1 x)) 4))
(* 3 (+ 1 4))
(* 3 5)
(15)
   
   

Part II.

1. ;; using map
   (define (apply-all lst num)
           (map (lambda (func) (func num)) lst))
   
   ;; without using map
   (define (apply-all lst num)
           (if (null? lst) '() (cons ((car lst) num) (apply-all (cdr lst) num))))
   

2. (define (all-are pred?)
           (lambda (alist) (all-are-helper pred? alist)))
   
   (define (all-are-helper pred? alist)
           (cond   ((null? alist) #t)
                   ((pred? (car alist)) (all-are-helper pred? (cdr alist)))
                   (else #f)))

Part III.

1. (define (make-expr left-op operator right-op)
           (list left-op operator right-op))
   
   (define (operator expr-tree)
           (car (cdr expr-tree)))
   
   (define (left-op expr-tree)
           (car expr-tree))
   
   (define (right-op expr-tree)
           (car (cdr (cdr expr-tree))))
   

2. (define (preorder expr-tree)
           (cond   ((pair? expr-tree) (append (list (operator expr-tree)) (preorder
    (left-op expr-tree)) (preorder (right-op expr-tree))))
                   (else (list expr-tree))))
   
   (define (postorder expr-tree)
           (cond   ((pair? expr-tree) (append (postorder (left-op expr-tree)) (post
   order (right-op expr-tree)) (list (operator expr-tree))))
                   (else (list expr-tree))))
                   
   (define (inorder expr-tree)
           (cond   ((pair? expr-tree) (append (inorder (left-op expr-tree)) (list (
   operator expr-tree)) (inorder (right-op expr-tree))))
                   (else (list expr-tree))))
                   

3. ;; without using a helper function
   (define (eval-expr expr-tree)
           (cond 	((pair? expr-tree)
                   	((cond ((equal? (operator expr-tree) '+) +)
                           	((equal? (operator expr-tree) '-) -)
                           	((equal? (operator expr-tree) '*) *)
                           	((equal? (operator expr-tree) '/) /)) (eval-expr (left-op expr-tree)) (eval-expr (right-op expr-tree))))
                 	(else expr-tree)))
   
   
   ;; using a helper function for getting the operator
   (define (eval-expr expr-tree)
           (cond 	((pair? expr-tree)
                   	((look-up-op (operator expr-tree)) (eval-expr (left-op expr-tree)) (eval-expr (right-op expr-tree))))
                 	(else expr-tree)))
   
   (define (look-up-op op)
           (cond 	((equal? op '+) +)
                 	((equal? op '-) -)
                 	((equal? op '*) *)
                 	((equal? op '/) /)))