연습문제 2.32

모든 부분집합을 가져오기위해서는

개별 부분집합과 나머지 요소의 결합을 만드는 것이 필요하다.

따라서 개별부분집합을 가져오는 (cdr list)로 구해지는 각각의 rest 요소를 (car list)와 결합하는 작업이 필요하다

그러므로 준 식의 빈 부분을 채우면

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest
                (map
                 (lambda (n) (cons (car s) n)) rest)))))

이 되어야한다.

연습문제 2.31

;; ex 2-31
(define (tree-map f tree)
  (map (lambda (subtree)
         (if (pair? subtree)
             (tree-map f subtree)
             (f subtree))) tree))

(define (square-tree-abstract tree)
  (tree-map square tree))

연습문제 2.30

;; ex 2-30
(define (square-tree tree)
  (cond ((null? tree) tree)
        ((not (pair? tree)) (square tree))
        (else
         (cons (square-tree (car tree))
               (square-tree (cdr tree))))))

(define (square-tree-map tree)
  (map (lambda (subtree)
         (if (pair? subtree)
             (square-tree-map subtree)
             (square subtree)))
       tree))

연습문제 2.29

; a
(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (car (cdr mobile)))
 
(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (car (cdr branch)))

;b
(define (is-weight? structure)
  (not (pair? structure)))

(define (weight-of-mobile mobile)
  (+ (weight-of-branch (left-branch mobile))
     (weight-of-branch (right-branch mobile))))

(define (weight-of-branch branch)
  (let ((struct (branch-structure branch)))
    (cond ((is-weight? struct) struct)
          (else
           (weight-of-mobile branch)))))

;c
(define (balanced-mobile? mobile)
  (= (weight-of-mobile (left-branch mobile))
     (weight-of-mobile (right-branch mobile))))

;d
주요한 접근자로 left-branch, right-branch, branch-length, branch-structure, is-weight? 를 변경해야한다.

연습문제 2.28

(define (fringe lst)
  (cond ((null? lst) lst)
        ((not (pair? lst)) (list lst))
        (else
         (append (fringe (car lst)) (fringe (cdr lst))))))

연습문제 2.27

(define (my-deep-reverse lst)
  (cond ((null? lst) lst)
        ((not (pair? lst)) lst)
        (else
         (append (my-deep-reverse (cdr lst))
                 (list (my-deep-reverse (car lst)))))))

Append 뒤에는 리스트가 와야하니 결과를 일단 list로 감쌌다

연습문제 2.26

(define x (list 1 2 3))
(define y (list 4 5 6))

(append x y) 는

(1 2 3 4 5 6)

(cons x y) 는

((1 2 3) 4 5 6)

(list x y)는

((1 2 3) (4 5 6))

연습문제 2.25

(1 3 (5 7) 9)
에서 7을 빼내려면

(car (cdr (car (cdr (cdr '(1 3 (5 7) 9) )))))

((7)) 에서 7을 빼내려면

(car (car '((7)) ))

(1 (2 (3 (4 (5 (6 7)))))) 에서 7을 빼내려면

(define x '(1 (2 (3 (4 (5 (6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x))))))))))))

연습문제 2.24

> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))

그림은 생략.. 귀찮..

연습문제 2.23

for-each의 리턴값은 임의의 값일 수 있다고 했으므로 여기서는 newline을 그냥 호출한다.
이후에 해당하는 함수를 호출하고 다시 재귀를 해야하므로 편법이기는 하지만 여기서는 begin을 써서 복수 문장을 동시에 수행하도록 했다.

(define (my-for-each proc lst)
  (if (null? lst)
      (newline)
      (begin
        (proc (car lst))
        (my-for-each proc (cdr lst)))))

연습문제 2.22

(define (square-list-iter items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

이 결과는 다음과 같다.

(16 9 4 1)

문제는 cons를 하는 부분에 있다. 가장 마지막에 결과가 cons되므로 역순으로 출력된다. map의 정의를 다시 생각해볼것

(define (square-list-iter2 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons answer
                    (square (car things))))))
  (iter items nil))

의 결과는 다음과 같다.

((((() . 1) . 4) . 9) . 16)

역시 cons부분에서 문제를 찾아야한다.
(cdr things)와 cons부분의 변화를 살펴보자면.... (리스트는 (1 2 3 4)였다고 가정...

1) (2 3 4) (cons nil 1) -> ((). 1)
2) (3 4) (cons ((). 1) 4) -> ((() . 1) . 4)

...
식이 됨을 알 수 있다.

정확한 답을 원한다면 cons는 append로 바꾸고 이후에 나오는 square식을 list화 해야한다.

(define (square-list-iter3 items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (append answer
                    (list (square (car things)))))))
  (iter items nil))

연습문제 2.21

;; 일반 버전

(define (square x) (* x x))

(define nil (list))
(define (square-list items)
  (if (null? items)
      nil
      (cons (square (car items)) (square-list (cdr items)))))

;; 아래는 map을 이용한 버전

(define (square-list-map items)
  (map square items))

연습문제 2.19

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount
                (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(define (no-more? coin-values)
  (null? coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (first-denomination coin-values)
  (car coin-values))

연습문제 2.20

두수의 차이가 even이라면 같은 parity임을 이용해서 문제를 풀 수 있다.

따라서 기점이 되는 수와 나머지 리스트를 비교하면 해당하는 parity에 맞는 수를 모두 가져올 수 있다.

(define (same-parity . arg)
  (define (inner-same-parity n lst)
    (if (null? lst)
        lst
        (if (even? (- n (car lst)))
            (cons (car lst) (inner-same-parity n (cdr lst)))
            (inner-same-parity n (cdr lst)))))
  (if (null? arg)
      (list)
      (inner-same-parity (car arg) arg)))

연습문제 2.18

(define (my-reverse lst)
  (if (null? lst)
      lst
      (append (my-reverse (cdr lst)) (list (car lst)))))

연습문제 2.17

last-pair는 가장 마지막의 항목 값을 가져오는 함수이다.
따라서 전체길이에서 1을 뺀 순서의 값을 리스트로 변환하면 된다.

(define (last-pair lst)
  (let ((len (length lst)))
    (cond ((= len 0) 0)
          (else (list (list-ref lst (- len 1)))))))

연습문제 2.16 (무지 어려움)

수식의 많은 규칙이 구간에서는 적용되지 않는 경우가 많다. 예를 들어 보수의 합을 알아보자.

A의 보수를 A'이라고 하면 보통 다음의 수식이 인정된다.

A + A' = 0

하지만 구간에서는 다르다.

A를 [1,2]라 하면 A'은 [-2, -1]이 된다.

따라서 A + A' != [0,0] 이 된다.

또한 결합법칙이나 분배법칙등이 제대로 적용되지않는 사례또한 비일비재하다. 결국 구간문제를 해결하는데 있어서 일반적인 수리식을 제대로 적용할 수 없게 된다.

연습문제 2.15

수리적으로는 동일한 두 식의 계산값이 다를 수 있는 경우는 2.14를 풀면서 이미 알아본바있다.

이제 par1과 par2의 값을 비교해보자..

> (par1 (make-interval 0.9 1.1) (make-interval 1.9 2.1))
(0.534375 . 0.8250000000000002)
/> (par2 (make-interval 0.9 1.1) (make-interval 1.9 2.1))
(0.6107142857142858 . 0.721875)
/>

위에서 볼 수 있는 것처럼 par2로 계산한 값이 더 타이트한 값을 얻는다.
따라서 Eva의 견해는 옳다.

인생을 100점으로 만드는 비법..

진대제 정보통신부 장관이 9일 오전 7시30분부터 개최된 대한상의 초청 조찬 간담회를 시작하며 참석자들에게 던진 `조크성` 질문이다. 진 장관은 "제가 재미있는 얘기하나 하겠습니다"고 말하고, 파워포인트를 열었다.

파워포인트에는 진 장관이 외국인에게 들었다는 `인생을 100점짜리로 만들기 위한 조건`을 찾는 법이 소개돼 있었다.

방법은 이렇다. 일단 알파벳 순서대로 숫자를 붙여준다. A에 1을 붙여주고 B에 2, C에 3, D에 4..이런식으로Z(26)까지 붙이면 된다. 그런 다음 어떤 단어 알파벳에 붙여진 숫자를 모두 더해 100을 되는 단어를 찾는다.

방법을 소개한 뒤 진장관의 문답은 계속됐다.

"열심히 일하면 될까요? hard work, 98점입니다. 일만 열심히 한다고 100점짜리 인생이 되는건 아닙니다".

"그렇다면 지식이 많으면? knowledge는 96점입니다.

사랑을 하면? love 54점입니다.

운으로 될까요? luck 47점입니다.

돈이 많으면? money는 72점입니다.

리더십은요? leadership 89점입니다. 그럼 뭘까요?"

 

"답은 attitude입니다. 인생은 `마음먹기`에 따라 100점짜리가 될 수 있습니다".

연습문제 2.14

병렬저항에 관한 문제이다.

문제는 1/r1 + 1/r2 를 풀면서 생긴다.
1/r1 은 수학적으로 r2/(r1*r2)와 같다.  왜냐하면 r2/r2는 1과 같기때문인데..

하지만 계산식에서는 그렇지못하다...

동일한 수를 (div-interval)로 나누어보자.

/> (div-interval (make-interval 1 1.1) (make-interval 1 1.1))
(0.9090909090909091 . 1.1)
/> (div-interval (make-interval 1 1) (make-interval 1 1))
(1.0 . 1.0)
/>

결국 일정오차가 있는 수는 컴퓨터식에서 정확한 값을 내어놓지못하는 것을 알 수 있다.
따라서 분수의 덧셈을 표현하기위해 분모/분자에 일정한 값을 곱하는 방식은 이러한 오류를 만들게된다.

연습문제 2.13

두 값 x, y의 tolerance를 각각 dx, dy라고 하고 x,y 의 곱을 z라고 하자.
이때 dz를 z의 tolerance라고 하자

z + dz = (x + dx)(y + dy)
= xy + x.dy + y.dx + dx.dy

가 된다.

따라서

z = xy
dz = x.dy + y.dx + dx.dy

가 된다.

문제에서 x, y의 tolerance가 매우 작다고 했으므로 dx.dy를 0로 놓을 수 있다.

따라서 dz는 x.dy + y.dx 가 된다.

백분율을 나타내는 공식에 따라

dz/z = (x.dy + y.dx)/xy = dy/y + dx/x

가 되어 x, y의 오차 백분율의 합이 z의 오차 백분율임을 알 수 있다.

연습문제 2.12

(define (make-center-percent c p)
  (let ((diff (/ ( * c p) 100.0)))
    (make-center-width c diff)))

(define (percent i)
  (*  (/ (width i) (center i)) 100.0))

연습문제 2.11

interval의 각각의 부호에 따르면 총 16가지가 나온다.
하지만 interval의 lower보다 upper가 작은 가지수를 제외하면 총 9가지가 나온다.

각각을 양수 음수로 놓고 표를 만들면 다음과 같다.

(lower x)  (upper x)  (lower y)  (upper y)
    +               +             +              +    : lx.ly . ux.uy
    +               +             +              -    : 불가
    +               +             -              +    : ux.ly . ux,uy
    +               +             -              -    : ux,ly . lx,uy
    +               -             +              +    : 불가
    +               -             +              -    : 불가
    +               -             -              +    : 불가
    +               -             -              -    : 불가
    -               +             +              +    : lx,ly . ux,uy
    -               +             +              -    : 불가
    -               +             -              +    : ??
    -               +             -              -    : ux,ly . lx,ly
    -               -             +              +    : lx,uy . ux,ly
    -               -             +              -    : 불가
    -               -             -              +    : lx,uy . ux,ly
    -               -             -              -    : lx,ly  . ux,uy

따라서 이를 다시 함수로 정의하면 다음과 같다.

(define (sub-interval x y)
  (let ((lx (lower-bound x))
        (ly (lower-bound y))
        (ux (upper-bound x))
        (uy (upper-bound y)))
    (cond ((and (> lx 0) (> ux 0) (> ly 0) (> uy 0)) (make-interval (* lx ly) (* ux uy)))
          ((and (> lx 0) (> ux 0) (< ly 0) (> uy 0)) (make-interval (* ux ly) (* ux uy)))
          ((and (> lx 0) (> ux 0) (< ly 0) (< uy 0)) (make-interval (* ux ly) (* lx uy)))
          ((and (< lx 0) (> ux 0) (> ly 0) (> uy 0)) (make-interval (* lx ly) (* ux uy)))
          ((and (< lx 0) (> ux 0) (< ly 0) (< uy 0)) (make-interval (* ux ly) (* lx ly)))
          ((and (< lx 0) (< ux 0) (> ly 0) (> uy 0)) (make-interval (* lx uy) (* ux ly)))
          ((and (< lx 0) (< ux 0) (> ly 0) (< uy 0)) (make-interval (* lx uy) (* ux ly)))
          ((and (< lx 0) (< ux 0) (< ly 0) (< uy 0)) (make-interval (* lx ly) (* ux uy)))
          (else
           (let
               ((p1 (* lx ly))
                (p2 (* lx uy))
                (p3 (* ux ly))
                (p4 (* ux uy)))
             (make-interval
              (min p1 p2 p3 p4)
              (max p1 p2 p3 p4)))))))

연습문제 2.10

(define (div-interval x y)
  (cond ((= (upper-bound y) 0) (error "Divided by Zero!"))
        ((= (lower-bound y) 0) (error "Divided by Zero!"))
        (else
         (mul-interval x
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))))

연습문제 2.9

Interval A의 width를 Aw라 하고 Interval B의 width를 Bw라고 하자.
A의 Lower를 Al이라 하고 B의 Lower를 Bl이라고 하자.
그렇다면 두 Interval은 다음과 같이 나타내어진다.

Interval A = (Al, Al + 2Aw)
Interval B = (Bl, Bl + 2Bw)

이제 합을 구하면 다음과 같다.

Interval A +  Interval B = (Al + Bl, Al + Bl + 2Aw + 2Bw)

구한 합의 Width는

Aw + Bw

이므로 width는 interval의 덧셈을 따른다고 할 수 있다.

뺄셈의 경우

Interval A - Interval B = Interval A + ( Interval B의 보수) = (Al , Al + 2Aw) + (-Bl-2Bw, -Bl) = (Al - Bl - 2Bw, Al + 2Aw - Bl)

가 된다.

구한 차의 width는

Aw + Bw

이므로 width는 interval의 뺄셈에 대해서는 동일하게 따르지 않는다.

곱셈의 경우 각각의 Interval을 (1,2 ) (2,4)라고 하면 해당하는 width는 각각 1/2, 1 이다

두 interval곱은 정의에 따라 (2,8)이며 width는 3이다.

따라서 width는 interval의 곱셈에 대해서는 따르지 않는다.

나눗셈의 경우 각각의 Interval을 (1,2) (2,4)라고 하면 해당하는 width는 각각 1/2, 1이다.

이제 나눗셈을 해보면 (0.25, 1)이 되며 width는 0.375가 된다.

따라서 width는 interval의 나눗셈에 대해서는 따르지 않는다

연습문제 2.8

; ex 2.8
; 두 값의 차이중 작은 쪽은 한쪽 작은 값과 다른 쪽 큰 값의 차이를 구하고
; 반대로 한쪽 큰 값과 다른쪽 작은 값의 차이를 구하면 된다.

(define (sub-interval x y)
  (make-interval
   (- (lower x) (upper y))
   (- (upper x) (lower y))))

연습문제 2.7

(define (make-interval a b) (cons a b))
(define (lower-bound interval) (car interval))
(define (upper-bound interval) (cdr interval))

연습문제 2.6

힌트대로 one을 (add-1 zero)) 을 이용해서 풀어보면

(lambda (f) (lambda (x) (f ((zero f) x))))

여기서 zero는 인자하나를 받는 lambda식이므로

(lambda (f) (lambda(x) (f ((lambda (x) x) x))))

가 되므로

(lambda (f) (lambda (x) (f x)))

가 된다..

이제 two는 (add-1 one)이므로

(lambda (f) (lambda (x) (f ((one f) x))))

은 위의 식을 풀되 인자를 다른 것으로 변경하면..

one을

(lambda (g) (lambda (a) (g a)))

이라면 two는

(lambda (f) (lambda (x) (f (((lambda (g) (lambda (a) (g a))) f) x))))

이고

((lambda (g) (lambda (a) (g a))) f)

는

(lambda (a) (f a))

가 되므로 준식은

(lambda (f) (lambda (x) (f ((lambda (a) (f a)) x))))

가 된다.

다시
        

((lambda (a) (f a)) x)

는

(f x)

이므로 준식은

(lambda (f) (lambda (x) (f (f x))))

이 된다.

따라서 one과 two는

(define one (lambda (f) (lambda (x) (f x)))
(define two (lambda (f) (lambda (x) (f (f x))))

가 된다.

연습문제 2.5

일단 2^a * 3^b을 표현하기위해 cons를 만듬

;; ex 2.5
(define (pd-cons x y)
  (* (expt 2 x)
     (expt 3 y)))

car는 2^a를 cdr은 3^b를 내놓도록 car과 cdr을 만듬

(define (pd-car x)
  (define (iter n)
    (cond ((= (remainder n 3) 0) (iter (/ n 3)))
          (else n)))
  (iter x))

(define (pd-cdr x)
  (define (iter n)
    (cond ((= (remainder n 2) 0) (iter (/ n 2)))
          (else n)))
  (iter x))

중복되는 내용을 밖으로 빼서 최종 버전완성

(define (pd-iter n z)
  (cond ((= (remainder n z) 0) (pd-iter (/ n z) z))
        (else n)))

(define (pd-car x)
  (pd-iter x 3))

(define (pd-cdr x)
  (pd-iter x 2))

마지막으로 최종 결과의 지수부만 빼내는 부분을 만든다.

(define (exp base n)
  (define (iter n result)
    (cond
      ((= n 1) 0)
      ((= (/ n base) 1) result)
      (else (iter (/ n base) (+ result 1)))))
  (iter n 1))

최종버전은 아래와 같다..
(define (pd-cons x y)
  (* (expt 2 x)
     (expt 3 y)))

(define (exp base n)
  (define (iter n result)
    (cond
      ((= n 1) 0)
      ((= (/ n base) 1) result)
      (else (iter (/ n base) (+ result 1)))))
  (iter n 1))

(define (pd-iter n z)
  (cond ((= (remainder n z) 0) (pd-iter (/ n z) z))
        (else n)))

(define (pd-car x)
  (exp 2 (pd-iter x 3)))

(define (pd-cdr x)
  (exp 3 (pd-iter x 2)))

연습문제 2.4

(define (ld-cons x y)
  (lambda (m) (m x y)))

(define (ld-car z)
  (z (lambda (p q) p)))

(define (ld-cdr z)
  (z (lambda (p q) q)))

연습문제 2.3

먼저 기본적인 함수를 구성한다.

(define (make-rectangle p1 p2)
(cons p1 p2))

(define (rect-perimeter rect)
( * 2 (+ (rect-width rect)
(rect-height rect))))

(define (rect-area rect)
(* (rect-width rect)
(rect-height rect)))

이제 rect-width와 rect-height를 구성한다.

(define (rect-width rect)
(abs (- (point-x (start-rect rect))
(point-x (end-rect rect)))))

(define (rect-height rect)
(abs (- (point-y (start-rect rect))
(point-y (end-rect rect)))))

실행결과는 아래와 같다

> (define p1 (make-point 1 1))
> (define p2 (make-point 3 3))
> (define rect1 (make-rectangle p1 p2))
> (rect-perimeter rect1)
8
> (rect-area rect1)
4
>

연습문제 2.2

(define (make-segment start end)
  (cons start end))

(define (start-segment line)
  (car line))

(define (end-segment line)
  (cdr line))

(define (make-point x y)
  (cons x y))

(define (point-x point)
  (car point))

(define (point-y point)
  (cdr point))

(define (mid-point segment)
  (let ((seg1 (start-segment segment))
        (seg2 (end-segment segment)))
    (make-point (average (point-x seg1)
                         (point-x seg2))
                (average (point-y seg1)
                         (point-y seg2)))))

(define (print-point p)
  (newline)
  (display "(")
  (display (point-x p))
  (display ",")
  (display (point-y p))
  (display ")"))

(define (average x y)
  (/ (+ x y) 2.))

연습문제 2.1

먼저 부호를 가져오는 방법은 절대값을 구한 후 해당 값을 나누어서 얻도록 했다.

해당 부호값은 다음과 같이 얻을 수 있다.

(* (/ (abs n) n)
  (/ (abs d) d))

따라서 준 식은 다음과 같이 표현할 수 있다.

(define (make-rat n d)
  (let ((abs-n (abs n))
        (abs-d (abs d)))
    (let ((g (gcd abs-n abs-d))
          (sign (* (/ abs-n n) (/ abs-d d))))
      (cons (* (/ abs-n g) sign)
            (/ abs-d g)))))

let이 좀 많이 들어갔는데.. 일단 답이 나오는데 만족함..