PAPR2:pp2a2 [Ci.bule]

KATEDR� INFORMATIKY� PÍRODOVDECK� FAKULT� UNIVERZIT� PALACKÉHO� OLOMOU�

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�

mutátor� pár·� procedur� set-car� � set-cdr� destruktivn� zm¥n� pár� vrac� nedenovano� hodnot�

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°: ¹⁾, 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=) ²⁾ (set-car! (car (reverse s)) 'blah) s Z=) ³⁾ (set-car! (cadr (reverse s)) 100) s Z=) ⁴⁾ 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) '⁵⁾ (let ⁶⁾)) (cons (cons (caar rest) (car rest)) rest))))) (define s (f-list 4)) s Z=) ⁷⁾ ROZDÍL OPROTI PEDCHOZÍMU: (set-car! (car (reverse s)) 'blah) s Z=) ⁸⁾ (set-car! (cadr (reverse s)) 100) s Z=) ⁹⁾ 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() 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� set-x� (lambd� (value� (set� � value))� (defin� set-y� (lambd� (value� (set� � value))�

Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5�

(defin� ca� (lambd� (pair� (pai� 'car))� (defin� cd� (lambd� (pair� (pai� 'cdr))�

Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5�

123() 1blah Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5�

(defin� list-set� (lambd� (� inde� value� (le� ite� ¹⁴⁾)� l)�

abc Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5�

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�

a bc() d Ja� Kone£n� (KI� U� Olomouc� P� 2A� Lekc� � Mutac� 1� � 5�

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é�