SICP exercise 2.16 interval arithmetic (long)

Hi group

I'm a newbie working through SICP, a little less green than when you
kind people helped me with The Little Schemer.

I can't see any decent commentary on the web about exercise 2.16 (devise
an interval arithmetic package which isn't fooled by repeated instances of
the same quantity):

http://mitpress.mit.edu/sicp/full-t...tml#%_sec_2.1.4

I don't see how you are supposed to do this with the techniques
introduced in the book so far.  I have some working (inefficient) code
but it relies on material from later sections of chapter 2, and the use
of 'eq?' to decide object identity (which I got from R5RS online).  This
clearly isn't what the authors intended, so I don't think I'm spoiling
anyone's homework by posting it here.

The idea is to do what Alyssa did in the original mul-interval:
calculate the arithmetic operation for all possible combinations of the
endpoints of the argument intervals and choose the lowest and highest
answers.  I _think_ this method generalizes to all expressions you can
make by combining arithmetic operations.  (In the case of /, we've
disallowed division by intervals spanning zero, and 1/x is monotonic
on x < 0 and x > 0).

Then it's 'simply' a matter of remembering every interval which
participated in building up an expression and eliminating any
duplicates.

OK here goes.  I'd appreciate any criticism, and any hints about how I
was supposed to go about solving it.  Thank you.



;; An interval expression is an operator and an argument list. Operator
;; is a procedure with 1 argument - a list of N real numbers.  Args is a
;; list of N pairs of real numbers representing corresponding intervals.
(define (make-interval-exp operator args)
(cons operator args))

(define (operator-of interval-exp)
(car interval-exp))

(define (args-of interval-exp)
(cdr interval-exp))

(define (arity-of interval-exp)
(length (args-of interval-exp)))

;; Generate all combinations of arguments from the list of intervals
;; (resembles Cartesian product).
;;     (cart '((1 . 2) (3 . 4)))
;;     -> ((1 3) (1 4) (2 3) (2 4))
(define (cart lp)
(define (prepend-each elt product)
(map (lambda (p) (cons elt p)) product))
(if (null? lp)
'(())
(let ((front (car lp))
(cart-rest (cart (cdr lp))))
(append (prepend-each (car front) cart-rest)
(prepend-each (cdr front) cart-rest)))))

;; this is enough to define the 'interval' interface
(define (make-interval l u)
(make-interval-exp (lambda (x) (car x)) ; identity operator
(list (cons l u))))  ; applied to one interval

(define (lower-bound x)
(apply min (map (operator-of x) (cart (args-of x)))))

(define (upper-bound x)
(apply max (map (operator-of x) (cart (args-of x)))))

;; Combine interval expressions by combining the operators and lists
;; of intervals separately.
(define (leftmost lst n)
(if (zero? n)
'()
(cons (car lst) (leftmost (cdr lst) (- n 1)))))

(define (rightmost lst n)
(list-tail lst (- (length lst) n)))

(define (simple-combine exp1 exp2 bin-op)
(make-interval-exp
(lambda (x)
(bin-op ((operator-of exp1) (leftmost x (arity-of exp1)))
((operator-of exp2) (rightmost x (arity-of exp2)))))
(append (args-of exp1) (args-of exp2))))

;; Remove duplicated quantities with normalize. Normalize takes an
;; interval expression possibly with duplicated intervals and returns an
;; equivalent interval expression with the duplicates eliminated.

;; Return the index of the first occurrence of a in lst, else #f if not
;; found
(define (index-of a lst)
(define (iter a lst n)
(cond ((null? lst) #f)
((eq? a (car lst)) n)
(else (iter a (cdr lst) (+ 1 n)))))
(iter a lst 0))

;; Remove nth element from a list, 0 <= n < (length lst)
(define (remove lst n)
(define (iter lst n accum)
(if (zero? n)
(append (reverse accum) (cdr lst))
(iter (cdr lst) (- n 1) (cons (car lst) accum))))
(iter lst n '()))

;; Insert element at position n, 0 <= n <= (length list)
(define (insert x lst n)
(define (iter lst n accum)
(if (zero? n)
(append (reverse accum) (list x) lst)
(iter (cdr lst) (- n 1) (cons (car lst) accum))))
(iter lst n '()))

;; Remove duplicate intervals from an interval expression.  Do this any
;; time we combine expressions.
(define (normalize interval-exp)
(define (iter interval-exp n)
;; Test the nth interval to see if it is duplicated later on.
(let ((f (operator-of interval-exp))
(args (args-of interval-exp))
(arity (arity-of interval-exp)))
(if (= n arity)
interval-exp ; finished
(let* ((target (list-ref args n))
(found (index-of target (list-tail args (+ 1 n)))))
(if found
;; This is a duplicate & will be eliminated from both
;; the operator and the list of intervals.
(iter (make-interval-exp
;; The new operator takes one less argument than f.
;; When it is called with a list of N real numbers,
;; it calls f with a list of [N+1] real numbers formed
;; by copying the duplicate argument to the correct
;; position.
(lambda (x)
(f (insert (list-ref x (+ n found)) x n)))
;; Remove the corresponding interval
(remove args n))
n)
;; This argument is unique - move on to next
(iter interval-exp (+ 1 n)))))))
(iter interval-exp 0))

;; Define the arithmetic operations
(define (combine-interval-exps e1 e2 bin-op)
(normalize (simple-combine e1 e2 bin-op)))

(define (sub-interval x y)
(combine-interval-exps x y -))

(define (add-interval x y)
(combine-interval-exps x y +))

(define (mul-interval x y)
(combine-interval-exps x y *))

(define (spans-zero? x)
(and (<= (lower-bound x) 0)
(>= (upper-bound x) 0)))

(define (div-interval x y)
(if (spans-zero? y)
(error "zero divide")
(combine-interval-exps x y /)))

;; try it out
(define r1 (make-interval 12 13))
(define r2 (make-interval 7 8))
(define zero (sub-interval r1 r1))
(define one (div-interval r2 r2))

;; (upper-bound zero)
;; -> 0
;; (lower-bound zero)
;; -> 0
;; (upper-bound one)
;; -> 1
;; (lower-bound one)
;; -> 1

;; the resistors in parallel example
(define (par1 r1 r2)
(div-interval (mul-interval r1 r2)
(add-interval r1 r2)))

(define (par2 r1 r2)
(let ((one (make-interval 1 1)))
(div-interval one
(add-interval (div-interval one r1)
(div-interval one r2)))))

;; (upper-bound (par1 r1 r2))
;; -> 104/21
;; (lower-bound (par1 r1 r2))
;; -> 84/19
;; (upper-bound (par2 r1 r2))
;; -> 104/21
;; (lower-bound (par2 r1 r2))
;; -> 84/19

Alyson Hannigan Showing Pussy & Tits!
http://www.CheapVideoBlog.com/player.wmv?clip=726071

Hilary Swank sex parties - coed parties as you never saw them!
http://www.CheapVideoBlog.com/watch?q=726071

Carmen Electra stripping down in the garden!
http://www.CheapVideoBlog.com/watch?vid=726071

Pamela Anderson Nude Posing Home Made!
http://www.CheapVideoBlog.com/Watch?q=726071

Jessica Simpson changing her dirty panties!
http://www.CheapVideoBlog.com/player.mpeg?clip=726071

what about x*x-4*x+4 if x between 1 to 3.

the lower bound of x*x-4*x+4=3D(x-2)*(x-2) is 0 (when x is 2).

On 3=D4=C28=C8=D5, =CF=C2=CE=E77=CA=B149=B7=D6, seanf <cppthrowa...@blueyond
=
er.co.uk> wrote:
> Hi group
>
> I'm a newbie working through SICP, a little less green than when you
> kind people helped me with The Little Schemer.
>
> I can't see any decent commentary on the web about exercise 2.16 (devise
> an interval arithmetic package which isn't fooled by repeated instances of=[/color
]

> the same quantity):
>
> http://mitpress.mit.edu/sicp/full-t...tml#%_sec_2.1.4
>
> I don't see how you are supposed to do this with the techniques
> introduced in the book so far.  I have some working (inefficient) code
> but it relies on material from later sections of chapter 2, and the use
> of 'eq?' to decide object identity (which I got from R5RS online).  This
> clearly isn't what the authors intended, so I don't think I'm spoiling
> anyone's homework by posting it here.
>
> The idea is to do what Alyssa did in the original mul-interval:
> calculate the arithmetic operation for all possible combinations of the
> endpoints of the argument intervals and choose the lowest and highest
> answers.  I _think_ this method generalizes to all expressions you can
> make by combining arithmetic operations.  (In the case of /, we've
> disallowed division by intervals spanning zero, and 1/x is monotonic
> on x < 0 and x > 0).
>
> Then it's 'simply' a matter of remembering every interval which
> participated in building up an expression and eliminating any
> duplicates.
>
> OK here goes.  I'd appreciate any criticism, and any hints about how I
> was supposed to go about solving it.  Thank you.
>
> ;; An interval expression is an operator and an argument list. Operator
> ;; is a procedure with 1 argument - a list of N real numbers.  Args is a
> ;; list of N pairs of real numbers representing corresponding intervals.
> (define (make-interval-exp operator args)
>   (cons operator args))
>
> (define (operator-of interval-exp)
>   (car interval-exp))
>
> (define (args-of interval-exp)
>   (cdr interval-exp))
>
> (define (arity-of interval-exp)
>   (length (args-of interval-exp)))
>
> ;; Generate all combinations of arguments from the list of intervals
> ;; (resembles Cartesian product).
> ;;     (cart '((1 . 2) (3 . 4)))
> ;;     -> ((1 3) (1 4) (2 3) (2 4))
> (define (cart lp)
>   (define (prepend-each elt product)
>     (map (lambda (p) (cons elt p)) product))
>   (if (null? lp)
>       '(())
>       (let ((front (car lp))
>             (cart-rest (cart (cdr lp))))
>         (append (prepend-each (car front) cart-rest)
>                 (prepend-each (cdr front) cart-rest)))))
>
> ;; this is enough to define the 'interval' interface
> (define (make-interval l u)
>   (make-interval-exp (lambda (x) (car x)) ; identity operator
>                      (list (cons l u))))  ; applied to one interval
>
> (define (lower-bound x)
>   (apply min (map (operator-of x) (cart (args-of x)))))
>
> (define (upper-bound x)
>   (apply max (map (operator-of x) (cart (args-of x)))))
>
> ;; Combine interval expressions by combining the operators and lists
> ;; of intervals separately.
> (define (leftmost lst n)
>   (if (zero? n)
>       '()
>       (cons (car lst) (leftmost (cdr lst) (- n 1)))))
>
> (define (rightmost lst n)
>   (list-tail lst (- (length lst) n)))
>
> (define (simple-combine exp1 exp2 bin-op)
>   (make-interval-exp
>    (lambda (x)
>      (bin-op ((operator-of exp1) (leftmost x (arity-of exp1)))
>              ((operator-of exp2) (rightmost x (arity-of exp2)))))
>    (append (args-of exp1) (args-of exp2))))
>
> ;; Remove duplicated quantities with normalize. Normalize takes an
> ;; interval expression possibly with duplicated intervals and returns an
> ;; equivalent interval expression with the duplicates eliminated.
>
> ;; Return the index of the first occurrence of a in lst, else #f if not
> ;; found
> (define (index-of a lst)
>   (define (iter a lst n)
>     (cond ((null? lst) #f)
>           ((eq? a (car lst)) n)
>           (else (iter a (cdr lst) (+ 1 n)))))
>   (iter a lst 0))
>
> ;; Remove nth element from a list, 0 <=3D n < (length lst)
> (define (remove lst n)
>   (define (iter lst n accum)
>     (if (zero? n)
>         (append (reverse accum) (cdr lst))
>         (iter (cdr lst) (- n 1) (cons (car lst) accum))))
>   (iter lst n '()))
>
> ;; Insert element at position n, 0 <=3D n <=3D (length list)
> (define (insert x lst n)
>   (define (iter lst n accum)
>     (if (zero? n)
>         (append (reverse accum) (list x) lst)
>         (iter (cdr lst) (- n 1) (cons (car lst) accum))))
>   (iter lst n '()))
>
> ;; Remove duplicate intervals from an interval expression.  Do this any
> ;; time we combine expressions.
> (define (normalize interval-exp)
>   (define (iter interval-exp n)
>     ;; Test the nth interval to see if it is duplicated later on.
>     (let ((f (operator-of interval-exp))
>           (args (args-of interval-exp))
>           (arity (arity-of interval-exp)))
>       (if (=3D n arity)
>           interval-exp ; finished
>           (let* ((target (list-ref args n))
>                  (found (index-of target (list-tail args (+ 1 n)))))
>             (if found
>                 ;; This is a duplicate & will be eliminated from both
>                 ;; the operator and the list of intervals.
>                 (iter (make-interval-exp
>                        ;; The new operator takes one less argument than f.=[/color
]

>                        ;; When it is called with a list of N real numbers,=[/color
]

>                        ;; it calls f with a list of [N+1] real numbers for=[/color
]
med
>                        ;; by copying the duplicate argument to the correct=[/color
]

>                        ;; position.
>                        (lambda (x)
>                          (f (insert (list-ref x (+ n found)) x n)))
>                        ;; Remove the corresponding interval
>                        (remove args n))
>                       n)
>                 ;; This argument is unique - move on to next
>                 (iter interval-exp (+ 1 n)))))))
>   (iter interval-exp 0))
>
> ;; Define the arithmetic operations
> (define (combine-interval-exps e1 e2 bin-op)
>   (normalize (simple-combine e1 e2 bin-op)))
>
> (define (sub-interval x y)
>   (combine-interval-exps x y -))
>
> (define (add-interval x y)
>   (combine-interval-exps x y +))
>
> (define (mul-interval x y)
>   (combine-interval-exps x y *))
>
> (define (spans-zero? x)
>   (and (<=3D (lower-bound x) 0)
>        (>=3D (upper-bound x) 0)))
>
> (define (div-interval x y)
>   (if (spans-zero? y)
>       (error "zero divide")
>       (combine-interval-exps x y /)))
>
> ;; try it out
> (define r1 (make-interval 12 13))
> (define r2 (make-interval 7 8))
> (define zero (sub-interval r1 r1))
> (define one (div-interval r2 r2))
>
> ;; (upper-bound zero)
> ;; -> 0
> ;; (lower-bound zero)
> ;; -> 0
> ;; (upper-bound one)
> ;; -> 1
> ;; (lower-bound one)
> ;; -> 1
>
> ;; the resistors in parallel example
> (define (par1 r1 r2)
>   (div-interval (mul-interval r1 r2)
>                 (add-interval r1 r2)))
>
> (define (par2 r1 r2)
>   (let ((one (make-interval 1 1)))
>     (div-interval one
>                   (add-interval (div-interval one r1)
>                                 (div-interval one r2)))))
>
> ;; (upper-bound (par1 r1 r2))
> ;; -> 104/21
> ;; (lower-bound (par1 r1 r2))
> ;; -> 84/19
> ;; (upper-bound (par2 r1 r2))
> ;; -> 104/21
> ;; (lower-bound (par2 r1 r2))
> ;; -> 84/19

Simply try (div-interval r1 r1).

;-)

On Apr 1, 3:08 pm, yifei <mac...@gmail.com> wrote:
> what about x*x-4*x+4 if x between 1 to 3.
>
> the lower bound of x*x-4*x+4=3D(x-2)*(x-2) is 0 (when x is 2).
>
> On 3=D4=C28=C8=D5, =CF=C2=CE=E77=CA=B149=B7=D6, seanf <cppthrowa...@blueyo=[/color
]
nder.co.uk> wrote:
> 
> 
> 
 
of 
> 
> 
 
> 
> 
> 
> 
 
 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
 
> 
> 
> 
> 
f. 
s, 
ormed 
ct 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 
> 

On Tue, 1 Apr 2008 00:08:22 -0700 (PDT), yifei <macsyz@gmail.com> wrote:
> what about x*x-4*x+4 if x between 1 to 3.
>
> the lower bound of x*x-4*x+4=(x-2)*(x-2) is 0 (when x is 2).
>

That's a good question.  Back to the drawing board.