Zapiski in vaje #6 srečanja programerskega bralnega krožka SICP

Teme

Grajenje abstrakcij s podatki

Prvo poglavje, v katerem smo operirali s preprostimi števili, drugo poglavje nadgrajuje s podatkovnimi struktura oz. kombiniranjem podatkovnih objektov v sestavljene podatkovne modele.

Torej ustvarili bomo podatkovne abstrakcije in definirali funkcije ki lahko operirajo nad njimi. Preprost primer je recimo racionalno število, ki ga sestavlja par števca in imenovalca.

(define (ustvari-rac s i)
  (cons s i))

(define (stevec x) (car x))
(define (imenovalec x) (cdr x))
(define (izpisi-rac x)
  (newline)
  (display (stevec x))
  (display "/")
  (display (imenovalec x)))

(define polovica (ustvari-rac 1 2))
(izpisi-rac polovica)

(izpisi-rac (ustvari-rac 6 3))

Uporabimo funkcijo za najvecji skupni imenovlec, da poenostavimo recimo 6/3 v 2/1.

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

(define (ustvari-rac s i)
  (let ((g (gcd s i)))
    (cons (/ s g) (/ i g))))


(izpisi-rac (ustvari-rac 6 3))

vaje

2.1 bolji ustvari-rac

(define (ustvari-rac s i)
  (cons
   (if (< i 0)
       (* -1 s)
       s)
   (abs i)))

2.2 polovica daljice

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

(define make-segment cons)

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

(define (avg a b) (/ (+ a b) 2))

(define start-segment car)
(define end-segment cdr)

(define (midpoint-segment s)
  (let ((start (start-segment s))
        (end (end-segment s)))
    (make-point (avg (x-point start) (x-point end))
                (avg (y-point start) (y-point end)))))

2.3 obseg in ploščina pravokotnik

Najprej super simpl imeplemntacija - imamo samo dolžino in širino, ni res v koordinatnem sistemu. Plod lenobe, na katerega in na katero sem ponosen.

;; Dolzina in sirina
(define (ploscina-kvadra k)
  (* (car k) (cdr k)))

(define (obseg-kvadra k)
  (* 2 (+ car k) (cdr k)))

(define make-kvader cons)

Pa še primer v koordinatnem sistemu. Dejmo reč da je kvader vektor s širino; točka od in točka do daljice dolžine ter širina, ki se zgodi desno od daljice dolžine.

(define make-point cons)
(define make-segment cons)

(define x-point car)
(define y-point cdr)

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

(define (daljica pravokotnik) (car pravokotnik))
(define (sirina pravokotnik) (cdr pravokotnik))

(define (make-pravokotnik daljica sirina)
  (cons daljica sirina))

(define (tocke-pravokotnika pravokotnik)
  (print-point (start-segment (daljica pravokotnik)))
  (print-point (end-segment pravokotnik (daljica pravokotnik)))
  (print-point (+ (x-point (daljica pravokotnik))))
  ;; TODO cetrta tocka
  )

2.4 Proceduralna reprezantacija parov

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

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

;; kaksen je cdr?
(define (cdr z)
  (z (lambda (p q) q)))

(list
  (cons 10 12)
  (car (cons 10 12))
  (cdr (cons 10 12)))

2.5 aritmeticni par v stevilu

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

(define (car p)
  (if (= 0 (modulo p 2))
      (+ 1 (car (/ p 2)))
      0))

(define (cdr p)
  (if (= 0 (modulo p 3))
      (+ 1 (cdr (/ p 3)))
      0))

(list
 (cons 12 41)
 (car (cons 12 41))
 (cdr (cons 12 41)))

2.6 churchova števila

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

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

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

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

;; pokrajsano
(define one
  (lambda (f) (lambda (x) (f x))))

(define two
  (lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) (f x))) f) x)))))
;; @TODO hmm kaj se zgodi tu vmes koristnega za razumevanje?
(define two
  (lambda (f) (lambda (x) (f (f x)))))

2.7 Racunanje z intervali (z napako)

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

(define (div-interval x y)
  (mul-interval x
                (make-interval (/ 1.0 (upper-bound y))
                               (/ 1.0 (lower-bound y)))))

(define (make-interval a b) (cons a b))

(define upper-bound cdr)

(define lower-bound car)

(define (izpisi-interval a)
  (string-append (lower-bound a) "—" (upper-bound a)))


(list
  "3—4 + 5—8"
  (izpisi-interval
    (add-interval
      (make-interval 3 4)
      (make-interval 5 8)))

  "5—6 × 8—10"
  (izpisi-interval
    (mul-interval
      (make-interval 5 6)
      (make-interval 8 10))))

2.8 odstevanje intervala

Pri odštevanju intervala moramo pazit, da od zgornje meje prvega intervala odštejemo spodnjo mejo drugega!

(define (make-interval a b) (cons a b))

(define upper-bound cdr)

(define lower-bound car)

(define (sub-interval a b)
  (make-interval (- (lower-bound a) (upper-bound b))
                 (- (upper-bound a) (lower-bound b))))


(list
 (sub-interval (make-interval 10 12)
               (make-interval 3 7)))

2.9 srednja vrednost in napaka

Seštevanje je isto pri intervalu od-do kot srednja-vrednost in napaka. Odštevanje je podobno, le da napaki preprosto seštejemo (kar je malo bolj "intuitivno" kot pri intervalu, vsaj meni).

;; "napaka" je "width" intervala
(define (make-priblizek vrednost napaka) (cons vrednost napaka))

(define vrednost car)

(define napaka cdr)

(define (add-priblizek a b)
  (make-priblizek (+ (vrednost a) (vrednost b))
                  (+ (napaka a) (napaka b))))

(define (sub-priblizek a b)
  (make-priblizek (- (vrednost a) (vrednost b))
                  (+ (napaka a) (napaka b))))

(define (mul-priblizek a b)
  (make-priblizek (* (vrednost a) (vrednost b))
                  (+ (* (vrednost a) (napaka b))
                     (* (vrednost b) (napaka a)))))

(define (div-priblizek a b)
  (make-priblizek (* (vrednost a) (vrednost b))
                  (+ (* (vrednost a) (napaka b))
                     (* (vrednost b) (napaka a)))))

(list
 "vsota in razlika sta preprosti"
 "8±3 + 4±1 = 12±4 (8—16)"
 (add-priblizek (make-priblizek 8 3)
                (make-priblizek 4 1))
 "8±3 - 4±1 = 4±4 (6—8)"
 (sub-priblizek (make-priblizek 8 3)
                (make-priblizek 4 1))
 "pri mnozenju in deljenju pa je \"sirina\" (napaka) odvisna tudi od vrednosti")
 "8±3 × 4±1 = 35±20 (8×4 + 3×1) ± (1×8 + 3×4) (15—55)"
 (mul-priblizek (make-priblizek 8 3)
                (make-priblizek 4 1))
 "8±3 ÷ 4±1 = ?"
 ;; TODO
 ;(div-priblizek (make-priblizek 8 3)
 ;               (make-priblizek 4 1))
 ;; TODO napisi funkcije za deljenje