KATEDR� INFORMATIKY� PÍRODOV…DECK� FAKULT� UNIVERZIT� PALACKÉHO� OLOMOU� PARADIGMAT� PROGRAMOVÁN� 2� MUTAC� Slajd� vytvo°il� Vilé� Vychodi� � Ja� Kone£n� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� � � 5� � následující� nedojd� k� zm¥n� seznamu� al� � vytvo°en� novéh� seznam� (defin� � '(� � 3)� (set� � '(� bla� 3)� 123() s1blah3() Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� � � 5� mutátor� pár·� procedur� set-car� � set-cdr� destruktivn� zm¥n� pár� vrac� nedenovano� hodnot� (defin� � (con� � 2)� � � � � (set-car� � 'ahoj� � � aho� � (set-cdr� � 'svete� pahojsvete Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� � � 5� P°íklad: (define s '(1 2 3))  1  2  3 () (set-car! (cdr s) 'blah) s Z=) (1 blah 3)  1  blah  3 () Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 4 / 55 vznikají vzájemn¥ provázané seznamy, nutno dbát zvý²ené obez°etnosti! zvý²ené riziko vzniku chyb: necht¥ná mutace seznam· (define s '(1 2 3)) (define r (list 10 s 20)) r Z=) (10 (1 2 3) 20) s  1  2  3 () r  10    20 () (set-car! (cadr r) 'neco) s  neco  2  3 () r  10    20 () r Z=) (10 (neco 2 3) 20) s Z=) (neco 2 3) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 5 / 55 ;; pro n = 3 vytvo°: ((#f #f #f) (#f #f) (#f)), a podobn¥ ;; asymptotická £asová sloºitost: O(n(1 + n)=2) (define f-list (lambda (n) (build-list n (lambda (i) (build-list (- n i) (lambda (x) #f)))))) (define s (f-list 4)) s Z=) ((#f #f #f #f) (#f #f #f) (#f #f) (#f)) (set-car! (car (reverse s)) 'blah) s Z=) ((#f #f #f #f) (#f #f #f) (#f #f) (blah)) (set-car! (cadr (reverse s)) 100) s Z=) ((#f #f #f #f) (#f #f #f) (100 #f) (blah)) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 6 / 55 ;; ta samá procedura, ale efektivn¥j²í ;; asymptotická £asová sloºitost: O(n) (define f-list (lambda (n) (if (= n 1) '((#f)) (let ((rest (f-list (- n 1)))) (cons (cons (caar rest) (car rest)) rest))))) (define s (f-list 4)) s Z=) ((#f #f #f #f) (#f #f #f) (#f #f) (#f)) ROZDÍL OPROTI PEDCHOZÍMU: (set-car! (car (reverse s)) 'blah) s Z=) ((#f #f #f blah) (#f #f blah) (#f blah) (blah)) (set-car! (cadr (reverse s)) 100) s Z=) ((#f #f 100 blah) (#f 100 blah) (100 blah) (blah)) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 7 / 55 (f-lis� 3� ::� prvn� verz� pouºívajíc� build-lis�  #f #f#f #f() � (� #� (� #� (� (f-lis� 3� ::� druh� verz� (rekurzivní� () #f#f#f() Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� � � 5� program = data = mutovatelný seznam je moºné destruktivn¥ modikovat samotný program (!!) (define proc (lambda (x) (display (list "Input parameter: " x)) (newline) (set-car! x (+ (car x) 1)) x)) (define test (lambda () (proc '(0)))) (test) Z=) (1) vyti²t¥no: (Input parameter: (0)) (test) Z=) (2) vyti²t¥no: (Input parameter: (1)) ... Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 9 / 55 ;� konstrukc� mutovatelnéh� pár� (defin� con� (lambd� (� y� ;� modikátor� vazb� symbol� � � � (defin� set-x� (lambd� (value� (set� � value))� (defin� set-y� (lambd� (value� (set� � value))� ;� dispatc� (lambd� (signal� (con� ((equal� signa� 'car� x� ((equal� signa� 'cdr� y� ((equal� signa� 'set-car!� set-x!� ((equal� signa� 'set-cdr!� set-y!� (els� 'unknown-signal))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� ;� selektor� ca� � cd� (defin� ca� (lambd� (pair� (pai� 'car))� (defin� cd� (lambd� (pair� (pai� 'cdr))� ;� mutac� prvníh� prvk� (defin� set-car� (lambd� (pai� value� ((pai� 'set-car!� value))� ;� mutac� druhéh� prvk� (defin� set-cdr� (lambd� (pai� value� ((pai� 'set-cdr!� value))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� list-se� � klasick� nedestruktivn� (funkcionální� verz� (defin� list-se� (lambd� (� inde� value� (le� au� ((� l� (� 0)� (i� (� � index� (con� valu� (cd� l)� (con� (ca� l� (au� (cd� l� (� � 1))))))�  123() 1blah Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� list-set� destruktivn� modikac� prvk� (defin� list-set� (lambd� (� inde� value� (le� ite� ((� l� (� 0)� (i� (� � index� (set-car� � value� (ite� (cd� l� (� � 1)))� l)� 1blah3() Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� klasick� nedestruktivn� (funkcionální� append� (defin� append� (lambd� (l� l2� (i� (null� l1� l� (con� (ca� l1� (append� (cd� l1� l2))))� ab 10 � (� 2� (� abc Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� destruktivn� spojen� dvo� seznam� ab � () (defin� append2� (lambd� (l� l2� (i� (null� l1� � 10 2� (� l� (le� ite� ((� l1)� (i� (null� (cd� l)� (begi� (set-cdr� � l2� l1� (ite� (cd� l))))))� ab 10 c 2� (� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� p°i spojení seznam· dochází k mutaci prvního argumentu: (define x '(a b c)) (define y '(10 20)) (append2! x y) Z=) (a b c 10 20) x Z=) (a b c 10 20) y Z=) (10 20) neplatí v p°ípad¥ prázdného seznamu (není to pár) (define x '()) (define y '(10 20)) (append2! x y) Z=) (10 20) x Z=) () y Z=) (10 20) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 16 / 55 m·ºeme roz²í°it na libovolné argumenty: (define append! (lambda lists (foldr append2! '() lists))) dochází k destrukci v²ech krom¥ posledního v²echny neprázdné seznamy se postupn¥ prováºou (define a '(a b c)) (define b '(#t #f)) (define c '(2 4 6 8)) (define d '(foo bar baz)) (append! a b c d) Z=) (a b c #t #f 2 4 6 8 foo bar baz) a Z=) (a b c #t #f 2 4 6 8 foo bar baz) b Z=) (#t #f 2 4 6 8 foo bar baz) c Z=) (2 4 6 8 foo bar baz) d Z=) (foo bar baz) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 17 / 55 destruktivn� p°idáván� prvk� d� seznam� (defin� � '(� � c)� ab � (� (list-insert� � � 'd� d b a � (� (list-insert� � � 'd� � a bc() d Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� (list-insert� � � 'd� � a � � � (� � � (list-insert� � � 'd� � a bc � (� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5� destruktivn� p°idáván� prvk� d� NEPRÁZDNÉH� seznam� pr� prázdn� sezna� nelz� (nejso� mutovatelné� (defin� list-insert� (lambd� (� inde� value� (i� (� inde� 0� � vkládán� n� za£áte� (begi� (set-cdr� � (con� (ca� l� (cd� l))� (set-car� � value)� (le� ite� ((� l� (inde� index)� � vkládán� doprost°e� (i� (� inde� 1� (set-cdr� � (con� valu� (cd� l))� (ite� (cd� l� (� inde� 1))))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� destruktivn� odebírán� prvk� z� seznam� (defin� � '(� � c)� (list-delete� � 0� bbc() (list-delete� � 1� abc() (list-delete� � 2� a � (� c() Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� destruktivn� mazán� prvk� � aspo� DVOUPRVKOVÉH� seznam� jednoprvkov� seznam� nelz� zmutova� n� prázdn� (defin� list-delete� (lambd� (� index� (i� (� inde� 0� (begi� (set-car� � (cad� s)� � mazán� � prvn� pozic� (set-cdr� � (cdd� s))� (le� ite� ((� l� � mazán� z� zbytk� seznam� (inde� index)� (i� (� inde� 1� (set-cdr� � (cdd� l)� (ite� (cd� l� (� inde� 1))))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� destruktivn� mazán� prvk� � aspo� DVOUPRVKOVÉH� seznam� jednoprvkov� seznam� nelz� zmutova� n� prázdn� (defin� list-delete� (lambd� (� index� (i� (� inde� 0� (begi� (set-car� � (cad� s)� � mazán� � prvn� pozic� (set-cdr� � (cdd� s))� (le� ite� ((� l� � mazán� z� zbytk� seznam� (inde� index)� (i� (� inde� 1� (set-cdr� � (cdd� l)� (ite� (cd� l� (� inde� 1))))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� Efektivn� implementac� FRONTY� vkládán� � mazán� � O(1� ;� vytvo� prázdno� front� (defin� make-queu� (lambd� (� (con� '(� '()))� � ;� testuj� zdal� j� dan� front� prázdn� (defin� empty-queue� (lambd� (queue� (an� (null� (ca� queue)� (null� (cd� queue))))� ;� vra� prve� n� vrchol� front� (defin� queue-ge� caar�  abc() Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� Princi� vkládán� prvk� n� kone� front� � (� (� � �  ab() � � a()  abc() Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� Princi� smazán� prvk� z� za£átk� front� � � �  ab b () c()  c() () � (� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� ;� vlo� prve� n� kone� front� (defin� queue-insert� (lambd� (queu� elem� (i� (empty-queue� queue� (begi� (set-car� queu� (con� ele� (ca� queue))� (set-cdr� queu� (ca� queue))� (begi� (set-cdr� (cd� queue� (lis� elem)� (set-cdr� queu� (cdd� queue)))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� ;� sma� prve� z� za£átk� front� (defin� queue-delete� (lambd� (queue� (i� (no� (empty-queue� queue)� (begi� (set-car� queu� (cda� queue)� (i� (null� (ca� queue)� (set-cdr� queu� '())))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 2� � 5� (define q (make-queue)) q Z=) (()) (queue-insert! q 10) (queue-insert! q 20) (queue-insert! q 30) q Z=) ((10 20 30) 30) (queue-get q) Z=) 10 (queue-delete! q) (queue-insert! q 40) q Z=) ((20 30 40) 40) (queue-delete! q) (queue-delete! q) q Z=) ((20 30 40) 40) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 29 / 55 Cyklické seznamy (define a '(ahoj)) (set-cdr! a a) a Z=) (ahoj ahoj ahoj    Z=) DrScheme vypí²e: #0=(ahoj . #0#)  ahoj ()  ahoj  tradi£n¥ napsaný length selhává (define length (lambda (l) (if (null? l) 0 (+ 1 (length (cdr l)))))) (length a) Z=) 1 (length a) Z=) length: exp. arg. of type ; given #0=(ahoj . #0#) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 30 / 55 (define a '(1 2 3))  1  2  3 () (set-cdr! (cddr a) a) a Z=) (1 2 3 1 2 3 1 2 3    Z=) #0=(1 2 3 . #0#)  1  2  3  Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 31 / 55 (define a '(10 20 30)) (set-car! (cdr a) a) a Z=) (10 (10 (10 (10    30) 30) 30) 30) Z=) #0=(10 #0# 30) (length a) Z=) 3  10    30 () Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 32 / 55 (define a '(#f))  #f () (set-car! a a) a Z=) ((((    )))) Z=) #0=(#0#) (length a) Z=) 1   () Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 33 / 55 zacyklení lineárního seznamu (vrací nedenovanou hodnotu) do posledního páru místo () vloºí ukazatel na první pár (define cycle! (lambda (l) (let iter ((aux l)) (if (null? (cdr aux)) (set-cdr! aux l) (iter (cdr aux)))))) (define s '(a b c d e)) (cycle! s) s Z=) #0=(a b c d e . #0#) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 34 / 55 OTÁZKA: jek detekovat cyklus v seznamu? naivní (nefunk£ní) °e²ení (define cycle? (lambda (l) (if (null? l) #f (cycle? (cdr l))))) pot°ebujeme porovnávat fyzické umíst¥ní pár· v pam¥ti predikát equal? nám NIJAK NEPOM—šE, protoºe: (define a (cons 1 2)) (define b (cons 1 2)) (equal? a b) Z=) #t : : : problém (set-car! a 10) a Z=) (10 . 2) b Z=) (1 . 2) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 35 / 55 Predikát eq? je #t na £íslech, práv¥ kdyº mají shodnou reprezentaci na symbolech, práv¥ kdyº se jmenují stejn¥ na párech, práv¥ kdyº mají stejné uloºení v pam¥ti (eq? 1.2 1.2) Z=) #f (eq? 2 2) Z=) #t (eq? 'ahoj 'ahoj) Z=) #t (eq? (cons 1 2) (cons 1 2)) Z=) #f Predikát eqv? je #t na £íslech, práv¥ kdyº jsou numerická stejná na symbolech, práv¥ kdyº se jmenují stejn¥ na párech, práv¥ kdyº mají stejné uloºení v pam¥ti (eqv? 1.2 1.2) Z=) #t (eqv? 2 2) Z=) #t (eqv? 'ahoj 'ahoj) Z=) #t (eqv? (cons 1 2) (cons 1 2)) Z=) #f Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 36 / 55 (defin� bot� (lambd� (type� � y� (an� (type� x� (type� y)))� (defin� eqv� (lambd� (� y� (i� (an� (bot� number� � y� (o� (bot� exact� � y� (bot� inexact� � y))� (� � y� (eq� � y)))� (defin� equal� (lambd� (� y� (o� (eqv� � y� (an� (bot� pair� � y� (equal� (ca� x� (ca� y)� (equal� (cd� x� (cd� y)))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 3� � 5� test zacyklenosti lineárního seznamu (define cyclic? (lambda (l) (let test ((rest (if (null? l) '() (cdr l)))) (cond ((null? rest) #f) ((eq? rest l) #t) (else (test (cdr rest))))))) p°íklad pouºití (cyclic? '()) Z=) #f (cyclic? '(a b c)) Z=) #f (define s '(a b c)) (cycle! s) (cyclic? s) Z=) #t Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 38 / 55 odcyklení lineárního seznamu rozetnutí cyklu vloºením () místo ukazatele na po£átek (define uncycle! (lambda (l) (let iter ((aux l)) (if (eq? (cdr aux) l) (set-cdr! aux '()) (iter (cdr aux)))))) zacyklením a odcyklením nemusíme získat výchozí seznam (define s '(a b c)) (cycle! s) (set! s (cdr s)) s Z=) #0=(b c a . #0#) (uncycle! s) s Z=) (b c a) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 39 / 55 Analogicky jako existují eq?, eqv? a equal? mají své varianty i member a assoc member : : : pouºívá k porovnání prvk· equal? memv : : : pouºívá k porovnání prvk· eqv? memq : : : pouºívá k porovnání prvk· eq? (member '(a) '(1 2 (a) 3 4)) Z=) ((a) 3 4) (memq '(a) '(1 2 (a) 3 4)) Z=) #f assoc : : : pouºívá k porovnání klí£· equal? assv : : : pouºívá k porovnání klí£· eqv? assq : : : pouºívá k porovnání klí£· eq? (assoc '(2) '((1 . a) ((2) . b) (3 . c))) Z=) ((2) . b) (assq '(2) '((1 . a) ((2) . b) (3 . c))) Z=) #f Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 40 / 55 Test cyklu do hloubky cyclic? testuje pouze jeden typ zacykleni selhává na mnoha cyklických strukturách P°íklad: (define s '(a b c d e f)) (set-car! (cdddr s) (cdr s)) s Z=) (a . #0=(b c #0# e f)) (length s) Z=) 6 (cyclic? s) Z=) #f Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 41 / 55 Tes� cykl� d� hloubk� b¥he� sestup� sezname� s� udrºujem� sezna� ji� nav²tívenýc� pár� procedur� vyuºív� mem� (defin� depth-cyclic� (lambd� (l� (le� ((foun� '())� (le� tes� ((� l)� (i� (pair� l� (i� (mem� � found� #� (begi� (set� foun� (con� � found)� (o� (tes� (ca� l)� (tes� (cd� l))))� #f))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 4� � 5� Obousm¥rn� seznamy� speciáln� cyklick� struktur� jednotliv� bu¬k� budo� v� tvar� (ele� � (ptr� � ptr2))� kd� ele� j� libovoln� elemen� uloºen� � bu¬c� ptr� j� ukazate� n� p°edchoz� bu¬k� ptr� j� ukazate� n� následujíc� bu¬k� (m� stejno� rol� jak� cdr� ;� konstrukto� obousm¥rnéh� seznam� (defin� cons-dlis� (lambd� (ele� dlist� (le� ((new-cel� (con� ele� (con� '(� dlist)))� (i� (no� (null� dlist)� (set-car� (cd� dlist� new-cell)� new-cell))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 4� � 5� Princi� konstrukc� obousm¥rnéh� seznam� (cons-dlis� zna£en� consd� (defin� � (cons� '� (cons� '� (cons� '� '())))� b() c d  () Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 4� � 5� (defin� � (cons� '� s)� b c a d  () () Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 4� � 5� ;; selektory car, cdr a cir (define dlist-car (lambda (dlist) (car dlist))) (define dlist-cdr (lambda (dlist) (cddr dlist))) (define dlist-cir (lambda (dlist) (cadr dlist))) P°íklad: (zkracujeme jména na consd, dcar, dcdr a dcir) (define s (consd 'a (consd 'b (consd 'c (consd 'd '()))))) Z=) #0=(a () . #1=(b #0# . #2=(c #1# d #2#))) (dcar s) Z=) a (dcir s) Z=) () (dcdr s) Z=) #0=(b (a () . #0#) . #1=(c #0# d #1#)) (dcar (dcdr s)) Z=) b (dcir (dcdr s)) Z=) #0=(a () . #1=(b #0# . #2=(c #1# d #2#))) (dcdr (dcdr s)) Z=) #1=(c #0=(b (a () . #0#) . #1#) d #1#) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 46 / 55 P°edávání argument· procedurám (define add2 (lambda (x) (set! x (+ x 2)) x)) (define val 10) (add2 val) Z=) 12 val Z=) 10 Chceme umoºnit p°edávat argumenty odkazem Vytvo°íme: BOX = mutovatelný kontainer na hodnotu Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 47 / 55 Metod� p°edáván� argument� procedurá� P°edáván� parametr� � metod� navázán� parametr� n� formáln� argument� souvis� � p°íkaze� p°i°azení� � :� � � ..� L-hodnot� � � � pam¥´ov� místo� n� kter� ukládám� � ..� R-hodnot� � � � obsah� kter� ukládám� Volán� hodnoto� (Cal� b� Value� � volan� procedu°� jso� p°edán� � -hodnot� argument� � hodnot� jso� uchováván� (vázány� � lokální� prost°ed� � volan� procedur� nem·º� p°i°azova� hodnot� p°e� argument� � jazyky� Scheme� LISP� � Volán� odkaze� (Cal� b� Reference� � volan� procedu°� jso� p°edán� L-hodnot� argument� � volan� procedur� m� � dispozic� odkaz� n� úloºi²t� hodno� � p°i°azen� d� prom¥nn� � t¥l� procedur� m¥n� hodnot� argument� � prost°ed� z� kteréh� byl� procedur� volán� � jazyky� C+� (referenc� &)� PL� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 4� � 5� Metod� p°edáván� argument� procedurá� (pokr.� Volán� hodnotou-výsledke� (Cal� b� Value-Result� � n¥kd� s� princip� °ík� Copy-restor� Linkage� � volan� procedu°� jso� p°edán� L-hodnot� � hodnot� jso� uchováván� (vázány� � lokální� prost°ed� � p� dokon£en� výpo£t� s� proved� kopi� lokáln� uloºenýc� hodno� n� pam¥´ov� míst� p°edanýc� argument� � zdánliv� toté� jak� volán� odkazem� � rozdí� j� nap°íkla� p°� paralelní� vyhodnocován� � jazyky� FORTRAN� MP� Volán� jméne� (Cal� b� Name� � volan� procedu°� jso� p°edán� jmén� argument� � pokaºdé� kdy� j� b¥he� vyhodnocován� t¥l� procedur� naraºen� n� argumen� zastupovan� jménem� j� tot� jmén� vyhodnocen� � jazyky� Algo� 60� makr� � jazyk� � (p°ísn� vzat� nejso� procedury� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 4� � 5� BOX (mutovatelný kontainer na hodnotu) následující procedura vytvo°í box: nový objekt reagující na dva signály signál SET : : : zapi² hodnotu do boxu, signál GET : : : vra´ hodnotu z boxu (define make-box (lambda (value) (lambda (signal . new-value) (cond ((equal? signal 'get) value) ((equal? signal 'set) (set! value (car new-value))) (else "neznamy signal"))))) P°íklad: (define val (make-box 10)) (val 'get) Z=) 10 (val 'set 100) (val 'get) Z=) 100 Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 50 / 55 P°íklad: vypo£ti faktoriál a zapi² výsledek do argumentu procedura vºdy vrací symbol hotovo (define proc (lambda (box n) (letrec ((f (lambda (n) (if (= n 1) 1 (* n (f (- n 1))))))) (box 'set (f n)) 'hotovo))) pouºití: (proc val 20) Z=) hotovo (val 'get) Z=) 2432902008176640000 Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 51 / 55 Dal²í mutovatelná element: vektory (analogie pole) vytvá°ení vektor· pomocí hodnot (vector) Z=) #0() (vector 10 20 30) Z=) #2(10 20 30) (vector 10 10 10) Z=) #3(10) (vector 'ahoj 'svete) Z=) #2(ahoj svete) (vector 1 #f 'blah) Z=) #3(1 #f blah) vra´ délku vektoru (vector-length (vector)) Z=) 0 (vector-length (vector 'a 'b 'c)) Z=) 3 vytvá°ení vektoru o dané délce (hodnoty jsou nespecikované) (make-vector 10) Z=) #10(0) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 52 / 55 napln¥ní vektoru jednou hodnotou (define v (make-vector 10)) (vector-fill! v 'blah) v Z=) #10(blah) vytvá°ení vektoru o dané délce s po£áte£ním napln¥ním (make-vector 10 'blah) Z=) #10(blah) získání hodnoty podle indexu / mutace hodnoty (define v (vector 'a 'b 'c 'd 'e 'f)) (vector-ref v 2) Z=) c (vector-set! v 2 'blah) (vector-ref v 2) Z=) blah v Z=) #6(a b blah d e f) Jan Kone£ný (KI, UP Olomouc) PP 2A, Lekce 2 Mutace 53 / 55 m·ºem� denova� dal²� procedury� t°eba� ;� build-vecto� (analogick� jak� build-list� (defin� build-vecto� (lambd� (le� f� (le� ((new-vecto� (make-vecto� len))� (le� ite� ((� 0)� (i� (>� � len� new-vecto� (begi� (vector-set� new-vecto� � (� i)� (ite� (� � 1)))))))� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 5� � 5� ƒasov� sloºitos� prác� s� seznam� � vektory� stejn� operace� maj� jino� sloºitos� build-lis� O(n� build-vecto� O(n� ca� O(1� vector-ca� O(1� cd� O(1� vector-cd� O(n� con� O(1� cons-vecto� O(n� lengt� O(n� vector-lengt� O(1� list-re� O(n� vector-re� O(1� list-set� O(n� vector-set� O(1� ma� O(n� vector-ma� O(n� Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 5� � 5�