;; Scheme assignment solutions ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Problem 1 ;; Add complex numbers, represented as pairs. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define (complex-add a b) (cond ((and (number? a) (number? b)) (+ a b)) ((and (number? a) (pair? b)) (cons (+ a (car b)) (cdr b))) ((and (pair? a) (number? b)) (cons (+ (car a) b) (cdr a))) ((and (pair? a) (pair? b)) ;; if imaginary cancels, return real (if (= 0 (+ (cdr a) (cdr b))) (+ (car a) (car b)) ;; otherwise return both parts (cons (+ (car a) (car b)) (+ (cdr a) (cdr b))))) (else 'error))) ;; cleaner version (define (real-to-complex x) (cons x 0)) (define (simplify-complex x) (if (= 0 (cdr x)) (car x) x)) (define (complex-add2 x y) (let ((new-x (if (pair? x) x (real-to-complex x))) (new-y (if (pair? y) y (real-to-complex y))) ) (simplify-complex (cons (+ (car new-x) (car new-y)) (+ (cdr new-x) (cdr new-y)))) )) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Problem 2 ;; Polynomial addition (dense rep -- list all coeffs) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define (dense-poly-add x y) (cond ;; no more x terms ((null? x) y) ;; no more y terms ((null? y) x) ;; more terms in both, so add and recurse (else (cons (complex-add (car x) (car y)) (dense-poly-add (cdr x) (cdr y)))) )) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Problem 3 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; add complex/exponent pairs (define (complex-add-exp x y) (cond ((= (cdr x) (cdr y)) (cons (complex-add (car x) (car y)) (cdr x))) (else 'exponent-mismatch) )) ;; Polynomial addition (sparse rep -- coeff/exponent pairs) ;; I'll assume the lists are sorted by exp, starting with smallest (define (sparse-poly-add x y) (cond ;; one list is empty ((null? x) y) ((null? y) x) ;; x's next term precedes y's next term ((< (cdr (first x)) (cdr (first y))) (cons (first x) (sparse-poly-add (cdr x) y))) ;; y's next term precedes x's ((< (cdr (first y)) (cdr (first x))) (cons (first y) (sparse-poly-add x (cdr y)))) ;; exponents are equal, so add and recurse (else (cons (complex-add-exp (first x) (first y)) (sparse-poly-add (cdr x) (cdr y)))) )) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Problem 4 ;; list filter -- keep things that pass predicate P ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (define (filter P L) (cond ;; empty list ((null? L) L) ;; passes test ((P (car L)) (cons (car L) (filter P (cdr L)))) ;; fails test (else (filter P (cdr L))) )) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Problem 5 -- wine filtering ;; structure is (Year Variety Winery Price) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; sample wine list (define wines '((1996 Chardonnay Gallo 6.95) (1997 PinotNoir Gallo 5.95) (1995 Burgundy Ripple 3.95) (1996 CabernetSauvignon Gallo 4.95) (1997 PinotNoir MadDog 3.95) (1997 Chardonnay NightTrain 4.99) (1996 Bordeaux Ripple 2.99) (1997 Bordeaux Ripple 2.95) (1997 Chardonnay Gallo 5.95) (1994 Chardonnay Gallo 16.99) (1997 PinotNoir OldTavern 2.95) (1996 Burgundy MadDog 3.95))) ;; helper functions for wines (define (get-vintage wine) (first wine)) (define (get-variety wine) (second wine)) (define (get-winery wine) (third wine)) (define (get-price wine) (fourth wine)) ;; find wines with certain year (define (has-vintage year wines) (filter (lambda (w) (= year (get-vintage w))) wines)) ;; fine wines with a certain variety and winery (define (wine-type variety winery wines) (filter (lambda (w) (and (equal? variety (get-variety w)) (equal? winery (get-winery w)))) wines)) ;; find price of cheapest wine (define (cheapest-price wines) (if (null? wines) 'error (apply min (map get-price wines)))) ;; find cheapest wine ;; This works by filtering against cheapest price and just ;; returning one that matches it. (define (cheapest-wine wines) (if (null? wines) 'error (let ((price (cheapest-price wines))) (first (filter (lambda (w) (= price (get-price w))) wines)))))