Poza nawiasem

Synthroid Without Prescription Inderal No Prescription Nexium For Sale Prevacid Generic Buy Elimite Online Prevacid Without Prescription Ultram No Prescription Prevacid For Sale Ultram Generic Buy Prednisone Online Dzisiaj skupimy siÄ? na rozwiÄ?zaniu Ä?wicze?? z drugiego rozdzia??u Wizard Booka. Na poczÄ?tku zajmiemy siÄ? tworzeniem struktur danych, a p????niej tym, w czym podobno Lisp jest najlepszy: przetwarzaniem list.

2.2

Wprawka do dalszych Ä?wicze??, nie wymaga szczeg??lnego komentarza.

(define make-segment cons)
(define start-segment car)
(define end-segment cdr)
 
(define make-point cons)
(define x-point car)
(define y-point cdr)
 
(define (midpoint-segment segment)
  (make-point (average (x-point (start-segment segment))
                       (x-point (end-segment segment)))
              (average (y-point (start-segment segment))
                       (y-point (end-segment segment)))))
 
(define (average x y)
  (/ (+ x y) 2))

2.3

Poni??sza implementacja zak??ada, ??e prostokÄ?t tworzymy podajÄ?c wsp????rzÄ?dne przeciwleg??ych wierzcho??k??w (punkt??w, utworzonych przy pomocy make-point). Warto zwr??ciÄ? uwagÄ? na kolejno??Ä? definicji poszczeg??lnych funkcji. Na poczÄ?tku zdefiniowa??em funkcje obliczajÄ?ce obw??d (circumference) i powierzchniÄ? (area), korzystajÄ?c z jeszcze nie istniejÄ?cych definicji wysoko??ci (height) i szeroko??ci (width) prostokÄ?ta. Po tym przeszed??em do definicji tych dw??ch brakujÄ?cych funkcji, korzystajÄ?c z nieistniejÄ?cych jeszcze selektor??w prostokÄ?ta (rectangle-p1 i rectangle-p2) i selektor??w punktu (x-point i y-point). Wreszcie cztery selektory uda??o siÄ? zdefiniowaÄ? korzystajÄ?c wy??Ä?cznie z funkcji wbudowanych w jÄ?zyk (cons, car i cdr). Wishful thinking to potÄ???na technika, u??ywajcie jej jednak z rozwagÄ?.

Obw??d prostokÄ?ta.

(define (circumference rectangle)
  (+ (* 2 (height rectangle))
     (* 2 (width rectangle))))

Powierzchnia prostokÄ?ta.

(define (area rectangle)
  (* (height rectangle)
     (width rectangle)))

D??ugo??Ä? boku u??o??onego wzd??u?? osi X.

(define (height rectangle)
  (abs (- (y-point (rectangle-p1 rectangle))
          (y-point (rectangle-p2 rectangle)))))

D??ugo??Ä? boku u??o??onego wzd??u?? osi Y.

(define (width rectangle)
  (abs (- (x-point (rectangle-p1 rectangle))
          (x-point (rectangle-p2 rectangle)))))

Konstruktory i selektory dla prostokÄ?ta.

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

Konstruktory i selektory dla punktu.

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

2.4

Proste zadanie, kt??re zaciera r????nicÄ? miÄ?dzy kodem, a danymi.

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

2.5

Kolejna zabawna implementacja funkcji cons, car i cdr.

(define (dividable? a b)
  (= (remainder a b) 0))
 
(define (logn a b)
  (/ (log b) (log a)))
 
(define (cons x y)
  (* (expt 2 x)
     (expt 3 y)))
 
(define (car x)
  (if (dividable? x 3)
      (car (quotient x 3))
      (logn 2 x)))
 
(define (cdr x)
  (if (dividable? x 2)
      (cdr (quotient x 2))
      (logn 3 x)))

2.17

Mamy zdefiniowaÄ? funkcjÄ? zwracajÄ?cÄ? listÄ? z ostatnim elementem danej listy. Niezliczone ilo??ci napisanych do tej pory funkcji przeglÄ?dajÄ?cych listy powodujÄ?, ??e nie musimy siÄ? nawet zastanawiaÄ? nad rozwiÄ?zaniem.

(define (last-pair seq)
  (if (null? (cdr seq))
    seq
    (last-pair (cdr seq))))

2.18

Odwr??cenie listy? Nic prostszego.

(define (reverse sequence)
  (define (iter sequence result)
    (if (null? sequence)
        result
        (iter (cdr sequence)
              (cons (car sequence) result))))
  (iter sequence ‘()))

U??ywajÄ?c funkcji fold z SRFI 1 sprawa staje siÄ? jeszcze prostsza:

(require (only (lib “1.ss” “srfi”) fold))
(define (reverse sequence)
  (fold cons ‘() sequence))

2.20

Zadanie zn??w proste, ale pokazuje jak definiowaÄ? funkcje o dowolnej liczbie argument??w, co warto zapamiÄ?taÄ? na przysz??o??Ä?.

(require (only (lib “1.ss” “srfi”) filter))
 
(define (same-parity first . rest)
  (let ((parity (remainder first 2)))
    (cons first
          (filter (lambda (x) (= (remainder x 2) parity))
                  rest))))

2.23

(define (for-each proc seq)
  (if (null? seq)
      #t
      (let ((result (proc (car seq))))
        (for-each proc (cdr seq)))))

ByÄ? mo??e znajÄ?c ju?? procedurÄ? map kusi??o by nas, by napisaÄ?:

(define (for-each proc seq)
  (begin
    (map proc seq)
    #t))

Jednak wed??ug standardu R5RS procedura map nie specyfikuje kolejno??ci wykonania mapowa?? poszczeg??lnych element??w. Przy ewaluacji wyra??enia (map 1+ '(1 2 3)) mog??o by siÄ? okazaÄ?, ??e najpierw wykonywane jest wyra??enie (1+ 2), potem (1+ 3) i na ko??cu dopiero (1+ 1). Wbrew pozorom w??a??ciwo??Ä? ta jest bardzo przydatna. Nietrudno sobie bowiem wyobraziÄ? implementacjÄ? map przeznaczonÄ? dla komputer??w wieloprocesorowych wykonujÄ?ca obliczenia r??wnolegle. Dop??ki wiÄ?c unikamy efekt??w ubocznych (ang. side-effects) przy mapowaniu, mo??emy w przysz??o??ci przenie??Ä? nasze obliczenia na wiele procesor??w, wymieniajÄ?c jedynie definicjÄ? funkcji map.

2.24

Mamy pokazaÄ? trzy reprezentacje wyniku ewaluacji wyra??enia (list 1 (list 2 (list 3 4))) przez interpreter. Zacznijmy od tego, co wypisze sam interpreter:

(1 (2 (3 4)))

Teraz wynik ewaluacji w postaci drzewa:

I wreszcie postaÄ? pude??kowo-wska??nikowa:

2.25

Musimy tylko przy pomocy car i cdr wydobyÄ? z podanych list liczbÄ? 7. Tak pewnie wyglÄ?da kod spagetti w Scheme.

• (car (cdr (car (cdr (cdr ‘(1 3 (5 7) 9))))))

• (caar ‘((7)))

• (cadr (cadr (cadr (cadr (cadr (cadr ‘(1 (2 (3 (4 (5 (6 7))))))))))))

TrochÄ? oszuka??em i u??y??em funkcji caar, kt??ra jest tym samym co (car (car ...)), jak i funkcji cadr, kt??ra odpowiada kombinacji (car (cdr ...)).

2.27

Przy rozwiÄ?zaniu tego Ä?wiczenia pozwoli??em sobie znowu skorzystaÄ? z funkcji fold.

(require (only (lib “1.ss” “srfi”) fold))
 
(define (deep-reverse seq)
  (fold (lambda (element result)
           (cons (if (pair? element)
                     (deep-reverse element)
                     element)
                 result))
         ‘()
         seq))

2.28

Tak przywyk??em ju?? do przydatnych funkcji z SRFI-1, ??e i tym razem nie mog??em siÄ? powstrzymaÄ? przed u??yciem jednej z nich. Bohaterem tego zadania jest append-map.

(require (only (lib “1.ss” “srfi”) append-map))
 
(define (fringe tree)
  (if (pair? tree)
      (append-map fringe tree)
      (list tree)))

2.30 i 2.31

Najpierw rozwiÄ???emy problem podnoszenia li??ci drzewa do kwadratu przy pomocy map, a potem wyodrÄ?bnimy z tej procedury og??lny schemat mapowania li??ci drzewa.

(define (square x) (* x x))
 
;; square-tree przy pomocy map
(define (square-tree seq)
  (if (pair? seq)
      (map square-tree seq)
      (square seq)))
 
;; tree-map do mapowania lisci drzewa
(define (tree-map proc tree)
  (if (pair? tree)
      (map (lambda (t) (tree-map proc t)) tree)
      (proc tree)))
 
;; square-tree przy pomocy tree-map
(define (square-tree seq)
  (tree-map square seq))

2.32

Odrobina teorii mnogo??ci jeszcze nikomu nie zaszkodzi??a.

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

Dzia??anie algorytmu naj??atwiej wyja??niÄ? na przyk??adach. Jest tylko jeden zbi??r zbioru pustego:

> (subsets ‘())
(())

Zbi??r jednoelementowy ma dwa podzbiory:

> (subsets ‘(1))
(() (1))

Podzbiory zbioru dwuelementowego osiÄ?gamy poprzez zebranie wszystkich podzbior??w zbioru o jednoelementowego (odpowiada za to wyra??enie (rest (subsets (cdr s)))) i nastÄ?pnie dodanie do ka??dego z tych podzbior??w elementu pierwszego (wyra??enie (map (lambda (el) (cons (car s) el)) rest)).

> (subsets ‘(2 1))
(() (1) (2) (2 1))

Jak widaÄ?, wziÄ?li??my wszystkie podzbiory zbioru (1), czyli () i (1), a nastÄ?pnie utworzyli??my nowe podzbiory dodajÄ?c do tych poprzednich nowy element 2, osiÄ?gajÄ?c (2) i (2 1). Podobnie rzecz wyglÄ?da dla zbior??w o wiÄ?kszej ilo??ci element??w:

> (subsets ‘(3 2 1))
(() (1) (2) (2 1) (3) (3 1) (3 2) (3 2 1))

Bierzemy wszystkie podzbiory zbioru (2 1) (czyli () (1) (2) (2 1) z kroku poprzedniego) i wrzucamy na poczÄ?tek ka??dego z nich tr??jkÄ?. Po??Ä?czenie tych dw??ch zbior??w daje nam wynik.

2.33

Ciekawe jest, ??e odwzorowanie (map) mo??na wyraziÄ? przy pomocy kumulacji. Podobnie zdefiniowaÄ? mo??na funkcje append i length.

(define (map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) ‘() sequence))
 
(define (append seq1 seq2)
  (accumulate cons seq2 seq1))
 
(define (length sequence)
  (accumulate (lambda (x y) (+ y 1)) 0 sequence))

2.34

Tym razem uzupe??niamy funkcjÄ? obliczajÄ?cÄ? warto??Ä? wielomianu za pomocÄ? schematu Hornera.

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ (* x higher-terms) this-coeff))
              0
              coefficient-sequence))

2.35

Zliczanie li??ci w drzewie - prosta sprawa.

(define (sum seq)
  (accumulate + 0 seq))
 
(define (count-leaves t)
  (sum (map (lambda (x)
              (if (pair? x)
                  (count-leaves x)
                  1))
            t)))

2.36

Uzupe??niÄ? brakujÄ?cy kod? ??miesznie proste.

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      ‘()
      (cons (accumulate op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

2.37

W tym zadaniu korzystamy ze standardowego map i z funkcji accumulate-n zdefiniowanej w poprzednim zadaniu.

(define (matrix-*-vector m v)
  (map (lambda (x) (sum (map * x v))) m))
 
(define (transpose mat)
  (accumulate-n cons ‘() mat))
 
(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (lambda (x) (matrix-*-vector cols x)) m)))

2.38

Znamy ju?? prawostronne sk??adanie (fold-right), teraz poznamy sk??adanie lewostronne (fold-left). Wyniki wyra??e?? sÄ? nastÄ?pujÄ?ce:

• (fold-right / 1 (list 1 2 3)) ; => 3/2 
   

• (fold-left / 1 (list 1 2 3)) ; => 1/6 
   

• (fold-right list ‘() (list 1 2 3)) ; => (1 (2 (3 ()))) 
   

• (fold-left list ‘() (list 1 2 3)) ; => (((() 1) 2) 3) 
   

W tym momencie warto jednak zatrzymaÄ? siÄ? na chwilÄ? i por??wnaÄ? sobie funkcje sk??adania przedstawione w Wizard Booku i te z SRFI 1. Na poczÄ?tek warto zauwa??yÄ?, ??e funkcje fold i fold-right z SRFI 1 potrafiÄ? obs??u??yÄ? kilka list, podczas gdy proste wersje zwijania z Wizard Booka przyjmujÄ? jako ostatni argument dok??adnie jednÄ? listÄ?. Po za tym fold-right wed??ug SRFI i wed??ug pan??w z MIT dzia??a identycznie. Wywo??any jako:

(fold-right op initial list)

zwr??ci wynik ewaluacji

(op e1 (op e2 … (op en initial)))

gdzie e1, e2, …, en to kolejne elementy listy list. Inaczej rzecz siÄ? ma ze zwijaniem lewostronnym. fold SRFI-owe rozwinie siÄ? w :

(op en … (op e2 (op e1 initial)) … )

podczas, gdy to z Wizard Booka rozwinie siÄ? do postaci zgo??a odmiennej:

(op (op (op initial e1) e2) … en)

R????nica powstaje z odmiennej kolejno??ci przekazanych argument??w do funkcji op. Jak widaÄ? powy??ej Wizard Bookowa wersja jako pierwszy argument stawia dotychczasowy wynik (w szczeg??lno??ci initial), za?? w przypadku SRFI na pierwszym miejscu stoi aktualny element iteracji. DziÄ?ki temu, ??e ta r????nica jest tak niewielka, z ??atwo??ciÄ? wyraziÄ? mo??na SICP-owe fold-left przy pomocy fold z SRFI 1:

(define (sicp-fold-left op initial sequence)
  (fold (lambda (x y) (op y x)) initial sequence))

2.41

Ostatnie Ä?wiczenie, kt??rego rozwiÄ?zanie chcia??bym dzisiaj przedstawiÄ?, dotyczy generowania permutacji i wybierania z nich podzbioru spe??niajÄ?cego pewny warunek. Zadanie 2.41 polega na znalezieniu zbioru takich uporzÄ?dkowanych tr??jek liczb naturalnych (bez zera), kt??rych suma ma okre??lonÄ? warto??Ä?. Zadanie to mo??na jednak uog??lniÄ?, co postaram siÄ? poni??ej uczyniÄ?. Na poczÄ?tek kilka pomocniczych definicji, kt??re znane sÄ? wam z poprzednich wpis??w:

(define nil ‘())
 
(define (accumulate op initial seq)
  (if (null? seq)
      initial
      (op (car seq)
          (accumulate op initial (cdr seq)))))
 
(define (sum seq)
  (accumulate + 0 seq))
 
(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

BÄ?dziemy r??wnie?? potrzebowaÄ? funkcji remove i filter z SRFI-1:

(require (only (lib “1.ss” “srfi”) remove filter))

Przyda nam siÄ? r??wnie?? oparta na remove funkcja remove-= usuwajÄ?ca z listy liczby r??wne danej liczbie:

(define (remove-= num l)
  (remove (lambda (x) (= x num)) l))

Przejd??my nareszcie do definicji naszego problemu. Musimy znale??Ä? tr??jki niepowtarzajÄ?cych siÄ? dodatnich liczb ca??kowitych nie wiÄ?kszych od N, kt??rych suma jest r??wna zadanej liczbie S. Znamy ju?? wiÄ?c sygnaturÄ? naszej funkcji:

(define (uniq-triples-with-sum s n) …)

Graficznie:

Zak??adajÄ?c, ??e potrafimy wygenerowaÄ? odpowiednie tr??jki liczb nie wiÄ?kszych od N, mo??emy zdefiniowaÄ? szukanÄ? funkcjÄ? nastÄ?pujÄ?co:

(define (uniq-triples-with-sum s n)
  (filter (lambda (triple) (sum-is? s triple))
          (uniq-triples n)))

co na schemacie mo??emy przedstawiÄ? jako:

Definicja predykatu sum-is? jest prosta:

(define (sum-is? n seq)
  (= (sum seq) n))

uniq-triples to twardsza sztuka. PatrzÄ?c jednak na problem z odpowiedniej perspektywy mo??na spostrzec, ??e zbi??r unikalnych uporzÄ?dkowanych tr??jek nie wiÄ?kszych ni?? liczba N mo??na otrzymaÄ? generujÄ?c wszystkie mo??liwe wariacje bez powt??rze?? zbioru liczb od 1 do N. ZapisujÄ?c to w Scheme:

(define (uniq-triples n)
  (if (< n 3)
      (error “n must be greater than 3, otherwise we won’t be able to generate a triple”)
      (permutations (enumerate n) 3)))

Schemat za?? przedstawia siÄ? nastÄ?pujÄ?co:

Zredukowali??my problem do implementacji dw??ch funkcji: enumerate i permutations. Nie trzymam was wiÄ?cej w niepewno??ci - poni??ej ich definicje, kt??re ko??czÄ? rozwiÄ?zanie naszego zadania.

(define (enumerate n)
  (define (iter n result)
    (if (zero? n)
        result
        (iter (- n 1) (cons n result))))
  (iter n nil))

(define (permutations s k)
  (if (zero? k)
      (list nil)
      (flatmap (lambda (x)
                 (map (lambda (p) (cons x p))
                      (permutations (remove-= x s) (- k 1))))
               s)))

Skoro jednak zahaczyli??my o kombinatorykÄ?, szkoda by??oby nie zg??Ä?biÄ? tematu trochÄ? bardziej. Poni??ej znajdziecie definicjÄ? permutacji:

(define (permutations-for-k=n s)
  (permutations s (length s)))

Skorzysta??em tutaj z powiÄ?zania permutacji i wariacji bez powt??rze??. Definicja wariacji z powt??rzeniami wymaga jednak trochÄ? wiÄ?cej zachodu:

(define (permutations-with-repetition n k)
  (if (zero? k)
      (list nil)
      (flatmap (lambda (perm-part) (map (lambda (element)
                                     (cons element perm-part))
                                   (enumerate n)))
               (permutations-with-repetition n (- k 1)))))

Przyk??adowo, by wygenerowaÄ? zbi??r wszystkich tr??jek (tym razem nie unikalnych) nie wiÄ?kszych od N, wystarczy napisaÄ?:

(define (triples n)
  (permutations-with-repetition n 3))