IDZ DO
IDZ DO
Projektowanie
PRZYKŁADOWY ROZDZIAŁ
PRZYKŁADOWY ROZDZIAŁ
oprogramowania.
SPIS TRE CI
SPIS TRE CI
Wstęp do programowania
i techniki komputerowej
KATALOG KSIĄŻEK
KATALOG KSIĄŻEK
Autorzy: Matthias Felleisen, Robert Bruce Findler,
KATALOG ONLINE
KATALOG ONLINE
Matthew Flatt, Shriram Krishnamurthi
Tłumaczenie: Bartosz Grabski, Mikołaj Szczepaniak
ZAMÓW DRUKOWANY KATALOG
ZAMÓW DRUKOWANY KATALOG
ISBN: 83-7197-922-3
Tytuł oryginału: How to Design Programs
Format: B5, stron: 644
TWÓJ KOSZYK
TWÓJ KOSZYK
Przykłady na ftp: 32 kB
Umiejętno ć programowania nie ma już charakteru czysto zawodowego. Księgowi
DODAJ DO KOSZYKA
DODAJ DO KOSZYKA
muszą się posługiwać arkuszami kalkulacyjnymi i edytorami tekstu, fotografowie
korzystają z edytorów zdjęć, muzycy programują syntezatory, za profesjonalni
programi ci tworzą skomplikowane aplikacje. Programowanie jest więc bardzo
CENNIK I INFORMACJE
CENNIK I INFORMACJE
pożądaną umiejętno cią, potrzebną nie tylko informatykom. Projektowanie
oprogramowania wymaga takich samych zdolno ci analitycznych, jak matematyka.
ZAMÓW INFORMACJE
ZAMÓW INFORMACJE
Jednak, w przeciwieństwie do matematyki, praca z programami jest aktywnym
O NOWO CIACH
O NOWO CIACH
sposobem zdobywania wiedzy. Obcowanie z oprogramowaniem daje możliwo ć stałej
interakcji, co pozwala na zgłębianie wiedzy, eksperymentowanie z nią oraz na stałą
ZAMÓW CENNIK
ZAMÓW CENNIK
samoocenę.
Autorzy tej klasycznej publikacji stawiają tezę, iż  każdy powinien nauczyć się, jak
projektować oprogramowanie i wła nie nauka podstaw projektowania jest jej tematem
CZYTELNIA
CZYTELNIA
głównym. W książce znajdziesz wiele podstawowych algorytmów, wyja nienia takich
FRAGMENTY KSIĄŻEK ONLINE
FRAGMENTY KSIĄŻEK ONLINE
pojęć, jak akumulacja wiedzy czy równo ć ekstensjonalna i intensjonalna, słowem
wszystko to, co stanowi teoretyczną podstawę wiedzy programistycznej.
Poznasz między innymi:
" Podstawowe struktury, z których składają się programy komputerowe
" Proste i złożony typy danych
" Metody przetwarzania danych
" Programowanie z użyciem rekurencji, algorytmy z nawracaniem
" Projektowanie abstrakcyjne
" Sposoby gromadzenia wiedzy
" Wykorzystanie wektorów
Z lektury książki  Projektowanie oprogramowania. Wstęp do programowania i techniki
Wydawnictwo Helion
komputerowej skorzystają zarówno studenci informatyki, jak też i słuchacze innych
ul. Chopina 6
kierunków oraz wszystkie osoby, które chcą podbudować swoją wiedzę praktyczną
44-100 Gliwice
solidnymi i przydatnymi podstawami teoretycznymi.
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treści
Przedm>wa ............................................................................................................9
Dlaczegż każdy pżwinien uczyć się prżgramżwać? .................................................................... 11
Metżdy prżjektżwania....................................................................................................................... 12
Wybór Scheme i DrScheme............................................................................................................... 14
Pżdzial książki..................................................................................................................................... 15
Pżdziękżwania .................................................................................................................................... 18
Część I Przetwarzanie prostych typO
w danych 19
1. Studenci, nauczyciele i k>mputery..........................................................21
2. Liczby, wyrażenia i pr>ste pr>gramy .....................................................23
Liczby i arytmetyka............................................................................................................................ 23
Zmienne i prżgramy .......................................................................................................................... 26
Prżblemy ze zrżzumieniem treści zadań........................................................................................ 29
Blędy...................................................................................................................................................... 30
Prżjektżwanie prżgramów................................................................................................................ 33
3. Pr>gram sklada się z funkcji i definicji zmiennych ..............................39
Skladanie funkcji................................................................................................................................. 40
Definicje zmiennych ........................................................................................................................... 43
Prżste ćwiczenia w twżrzeniu funkcji............................................................................................. 44
4. Instrukcje warunk>we i funkcje...............................................................47
Wartżści lżgiczne i relacje ................................................................................................................. 47
�unkcje testujące warunki ................................................................................................................. 50
Warunki i funkcje warunkżwe......................................................................................................... 54
Prżjektżwanie funkcji warunkżwych.............................................................................................. 57
5. Inf>rmacje symb>liczne.............................................................................63
Prżste ćwiczenia z symbżlami.......................................................................................................... 65
6. Dane zl>ż>ne. Część 1.: Struktury ...........................................................69
Struktury .............................................................................................................................................. 69
Ćwiczenie rżzszerzżne: rysżwanie prżstych żbrazów.................................................................... 72
4 SPIS TREŚCI
Definicje struktur ................................................................................................................................ 75
Definicje danych.................................................................................................................................. 79
Prżjektżwanie funkcji przetwarzających dane zlżżżne .................................................................... 82
Rżzszerzżne ćwiczenie: przemieszczanie żkręgów i prżstżkątów ............................................ 87
Rżzszerzżne ćwiczenie: gra w szubienicę ...................................................................................... 91
7. R>dzaje danych...........................................................................................95
Mieszanie i rżzróżnianie danych ..................................................................................................... 95
Prżjektżwanie funkcji przetwarzających dane mieszane........................................................... 100
Skladanie funkcji  pżwtórka ....................................................................................................... 104
Rżzszerzżne ćwiczenie: przesuwanie figur.................................................................................. 107
Blędne dane wejściżwe .................................................................................................................... 108
W1. Skladnia i semantyka...............................................................................111
Slżwnictwż języka Scheme ............................................................................................................. 112
Gramatyka języka Scheme .............................................................................................................. 112
Znaczenie w języku Scheme ........................................................................................................... 114
Blędy ........................................................ ...........................................................................................118
Wyrażenia lżgiczne .......................................................................................................................... 121
Definicje zmiennych ......................................................................................................................... 122
Definicje struktur .............................................................................................................................. 124
Część II Przetwarzanie danych dowolnej wielkości 127
9. Dane zl>ż>ne. Część 2.: Listy .................................................................129
Listy .....................................................................................................................................................129
Definicje danych dla list ż dżwżlnej dlugżści ............................................................................. 133
Przetwarzanie list ż dżwżlnej dlugżści ........................................................................................ 135
Prżjektżwanie funkcji dla rekursywnych definicji danych........................................................ 139
Więcej na temat przetwarzania prżstych list ............................................................................... 142
10. Więcej na temat przetwarzania list........................................................147
�unkcje zwracające listy................................................................................................................... 147
Listy zawierające struktury ............................................................................................................. 152
Rżzszerzżne ćwiczenie: przemieszczanie żbrazów .................................................................... 158
11. Liczby naturalne.......................................................................................161
Definiżwanie liczb naturalnych...................................................................................................... 161
Przetwarzanie liczb naturalnych dżwżlnej wielkżści................................................................. 163
Rżzszerzżne ćwiczenie: twżrzenie list, testżwanie funkcji........................................................ 166
ęlternatywne definicje danych dla liczb naturalnych .................................................................. 168
Więcej ż naturze liczb naturalnych................................................................................................ 173
12. Lączenie funkcji. P>wtórka.....................................................................177
Prżjektżwanie skżmplikżwanych prżgramów............................................................................ 177
Rekursywne funkcje zewnętrzne ................................................................................................... 178
Użgólnianie prżblemów i funkcji................................................................................................... 183
Rżzszerzżne ćwiczenie: przestawianie slów ................................................................................ 187
W2. Skracanie list .............................................................................................191
SPIS TREŚCI 5
Część III Więcej o przetwarzaniu danych
dowolnej wielkości 197
14. Więcej rekurencyjnych definicji danych ...............................................199
Struktury w strukturach .................................................................................................................. 199
Rżzszerzżne ćwiczenie: drzewa pższukiwań binarnych ........................................................... 208
Listy w listach.................................................................................................................................... 212
Rżzszerzżne ćwiczenie: żbliczanie wyrażeń języka Scheme..................................................... 215
15. Wzajemne >dw>lania w definicjach danych........................................217
Listy struktur. Listy w strukturach................................................................................................ 217
Prżjektżwanie funkcji dla definicji danych zawierających wzajemne żdwżlania ................. 223
Rżzszerzżne ćwiczenie: więcej na strżnach WWW..................................................................... 225
16. Tw>rzenie pr>gramów met>dą iteracyjneg> ulepszania...................227
ęnaliza danych.................................................................................................................................. 228
Definiżwanie i ulepszanie klas danych......................................................................................... 229
Ulepszanie funkcji i prżgramów .................................................................................................... 232
17. Przetwarzanie dwóch sk>mplik>wanych elementów danych .........235
Jednżczesne przetwarzanie dwóch list. Przypadek 1. ................................................................. 235
Jednżczesne przetwarzanie dwóch list. Przypadek 2. ................................................................. 237
Jednżczesne przetwarzanie dwóch list. Przypadek 3. ................................................................. 240
Upraszczanie funkcji ........................................................................................................................ 245
Prżjektżwanie funkcji pżbierających dwie zlżżżne dane wejściżwe ....................................... 247
Ćwiczenia z przetwarzania dwóch zlżżżnych danych wejściżwych....................................... 248
Rżzszerzżne ćwiczenie: żbliczanie wyrażeń języka Scheme. Część 2. .................................... 251
Równżść i testżwanie....................................................................................................................... 253
W3. L>kalne definicje i zasięg leksykalny ....................................................261
źrganizżwanie prżgramów za pżmżcą slżwa lżcal................................................................... 261
Zasięg leksykalny i struktura blżkżwa ......................................................................................... 276
Część IV Projektowanie abstrakcyjne 281
19. P>d>bieństwa w definicjach ...................................................................283
Pżdżbieństwa w funkcjach.............................................................................................................. 283
Pżdżbieństwa w definicjach danych ............................................................................................. 292
20. �unkcje są wart>ściami............................................................................297
Skladnia i semantyka ....................................................................................................................... 297
Kżntrakty dla abstrakcyjnych i pżlimżrficznych funkcji ........................................................... 299
21. Pr>jekt>wanie funkcji abstrakcyjnych na p>dstawie przykladów...303
ębstrahżwanie na pżdstawie przykladów................................................................................... 303
Ćwiczenia z abstrakcyjnymi funkcjami przetwarzającymi listy ............................................... 309
ębstrakcja i pżjedynczy punkt kżntrżli........................................................................................ 311
Rżzszerzżne ćwiczenie: przemieszczanie żbrazów jeszcze raz ................................................ 312
Uwaga: Prżjektżwanie abstrakcji na pżdstawie szablżnów...................................................... 314
6 SPIS TREŚCI
22. Pr>jekt>wanie abstrakcji .........................................................................317
�unkcje zwracające funkcje ............................................................................................................. 317
Prżjektżwanie abstrakcji z funkcjami jakż wartżściami............................................................. 319
Pierwsze spżjrzenie na graficzny interfejs użytkżwnika ........................................................... 322
23. Przyklady matematyczne........................................................................331
Ciągi i szeregi .................................................................................................................................... 331
Ciągi i szeregi arytmetyczne........................................................................................................... 333
Ciągi i szeregi geżmetryczne .......................................................................................................... 334
Pżle pżwierzchni pżd wykresem funkcji...................................................................................... 338
Nachylenie funkcji ............................................................................................................................ 340
W4. Bezp>średnie defini>wanie funkcji .......................................................345
Część V Rekursja generatywna 351
25. N>wa p>stać rekursji...............................................................................353
Mżdelżwanie kuli na stżle .............................................................................................................. 354
Szybkie sżrtżwanie........................................................................................................................... 357
26. Pr>jekt>wanie alg>rytmów.....................................................................363
Zakżńczenie....................................................................................................................................... 365
Rekursja strukturalna a generatywna............................................................................................ 368
Dżkżnywanie wybżrów .................................................................................................................. 369
27. Różne alg>rytmy rekurencyjne ..............................................................375
�raktale ............................................................................................................................................... 375
źd plików dż linii, żd list dż list list............................................................................................. 380
Wyszukiwanie binarne .................................................................................................................... 384
Metżda Newtżna .............................................................................................................................. 390
Rżzszerzżne ćwiczenie: eliminacja Gaussa .................................................................................. 392
28. ęlg>rytmy z nawracaniem .....................................................................397
Przechżdzenie grafów...................................................................................................................... 397
Rżzszerzżne ćwiczenie: szachżwanie hetmanów........................................................................ 403
W5. K>szt >bliczeni>wy >raz wekt>ry .........................................................405
Czas kżnkretny, czas abstrakcyjny ................................................................................................ 405
Definicja wyrażenia  rzędu ........................................................................................................... 410
Pierwsze spżjrzenie na wektżry..................................................................................................... 412
Część VI Gromadzenie wiedzy 423
30. Utrata wiedzy ...........................................................................................425
Prżblem przetwarzania strukturalnegż ........................................................................................ 425
Prżblem rekursji generatywnej....................................................................................................... 429
31. Pr>jekt>wanie funkcji z akumulat>rem................................................433
Czy akumulatżr jest pżtrzebny? .................................................................................................... 433
�unkcje z akumulatżrem ................................................................................................................. 434
Przeksztalcanie funkcji na funkcje z akumulatżrem................................................................... 436
SPIS TREŚCI 7
32. Dalsze użycie akumulacji........................................................................447
Rżzszerzżne ćwiczenie: akumulatżry i drzewa........................................................................... 447
Rżzszerzżne ćwiczenie: misjżnarze i ludżżercy.......................................................................... 452
Rżzszerzżne ćwiczenie: plansza gry Sżlitaire.............................................................................. 455
W6. Natura liczb nied>kladnych ...................................................................457
ęrytmetyka liczb ż stalym rżzmiarze ........................................................................................... 457
Przepelnienie ..................................................................................................................................... 463
Niedżmiar .......................................................................................................................................... 464
Liczby w DrScheme.......................................................................................................................... 465
Część VII Zmiana stanu zmiennych 467
34. Pamięć dla funkcji ....................................................................................469
35. Przypisanie d> zmiennych......................................................................475
Dzialanie prżstych przypisań ......................................................................................................... 475
Sekwencja wyrażeń żbliczeniżwych.............................................................................................. 477
Przypisania i funkcje ........................................................................................................................ 479
Pierwszy użyteczny przyklad......................................................................................................... 482
36. Pr>jekt>wanie funkcji z pamięcią..........................................................485
Zapżtrzebżwanie na pamięć........................................................................................................... 485
Pamięć i zmienne stanu ................................................................................................................... 487
�unkcje inicjalizujące pamięć.......................................................................................................... 489
�unkcje zmieniające pamięć............................................................................................................ 489
37. Przyklady zast>s>wania pamięci...........................................................497
Inicjalizacja stanu .............................................................................................................................. 497
Zmiana stanu przez interakcję z użytkżwnikiem ....................................................................... 500
Zmiany stanu przez rekursję .......................................................................................................... 508
Ćwiczenia na zmianach stanu ........................................................................................................ 514
Rżzszerzżne ćwiczenie: zwiedzanie .............................................................................................. 516
W7. K>ńc>wa skladnia i semantyka..............................................................519
Slżwnik ędvanced Scheme............................................................................................................. 519
Gramatyka ędvanced Scheme ....................................................................................................... 519
Znaczenie ędvanced Scheme ......................................................................................................... 522
Blędy w ędvanced Scheme............................................................................................................. 534
Część VIII Zmiana wartości zloz
onych 539
39. Hermetyzacja ............................................................................................541
ębstrahżwanie ze zmiennymi stanu ............................................................................................. 541
Ćwiczenia z hermetyzacji ................................................................................................................ 551
40. Mutacja struktur .......................................................................................553
Struktury z funkcji............................................................................................................................ 553
Mutacja struktur funkcjżnalnych ................................................................................................... 556
8 SPIS TREŚCI
Mutacja struktur................................................................................................................................ 558
Mutacja wektżrów ............................................................................................................................ 565
Zmiana zmiennych, zmiana struktur ............................................................................................ 567
41. Pr>jekt>wanie funkcji zmieniających struktury ..................................571
Pż cż mutżwać struktury ................................................................................................................ 571
Zasady prżjektżwania strukturalnegż i mutacji, część 1. .......................................................... 572
Zasady prżjektżwania strukturalnegż i mutacji, część 2. .......................................................... 583
Ćwiczenie rżzszerzżne: ruchżme żbrazy pż raz żstatni............................................................ 594
42. Równ>ść.....................................................................................................595
Równżść ekstensjżnalna .................................................................................................................. 595
Równżść intensjżnalna..................................................................................................................... 596
43. Zmiana struktur, wekt>rów i >biektów................................................601
Ćwiczenia praktyczne z wektżrami............................................................................................... 601
Zbiżry struktur z cyklami................................................................................................................ 616
Nawracanie ze stanem ..................................................................................................................... 626
Zak>ńczenie ..............................................................................................629
Technika żbliczeniżwa..................................................................................................................... 629
Prżgramżwanie................................................................................................................................. 630
Krżk naprzód..................................................................................................................................... 631
Dodatki 633
Sk>r>widz..................................................................................................635
17
Przetwarzanie dwóch
sk>mplik>wanych elementów danych
Czasami funkcja pobiera dwa argumenty należące do klas zdefiniowanych za pomocą
skomplikowanych definicji danych. W niektórych przypadkach jeden z argumentów
powinien być traktowany tak, jakby byl argumentem atomowym; precyzyjnie sformu-
lowany opis celu zazwyczaj to wyjaśnia. W innych przypadkach oba argumenty muszą
być przetwarzane równolegle. Czasem funkcja będzie musiala brać pod uwagę wszystkie
możliwe przypadki i odpowiednio przetwarzać dane argumenty. Ten rozdzial ilustruje
te trzy możliwości za pomocą przykladów i wprowadza rozszerzoną metodę projekto-
wania dla ostatniego przypadku. W ostatnim podrozdziale omawiamy równoważność
danych zlożonych i jej związek z procesem testowania; ma to istotne znaczenie dla au-
tomatyzacji testów funkcji.
Jedn>czesne przetwarzanie dwóch list. Przypadek 1.
Przeanalizuj następujący kontrakt, opis celu i naglówek:
;; zastap-empty-lista : lista-liczb lista-liczb -> lista-liczb
;; tworzy nową listę zastępując empty w liście dana-lista-liczb1 listą dana-lista-liczb2
(define (zastap-empty-lista dana-lista-liczb1 dana-lista-liczb2) & )
Kontrakt mówi, że funkcja pobiera dwie listy; z takim zdarzeniem nie spotkaliśmy się
wcześniej. Zobaczmy, jak nasza metoda projektowania sprawdzi się w tym przypadku.
Po pierwsze, tworzymy przyklady. Przypuśćmy, że pierwszą daną wejściową jest
empty. Funkcja zastap-empty-lista powinna w takim przypadku zwrócić drugi argument,
niezależnie od tego, co zawiera:
(zastap-empty-lista empty L)
= L
W powyższym równaniu L reprezentuje dowolną listę liczb. Przypuśćmy teraz, że
pierwszy argument jest różny od empty. Opis celu mówi, że powinniśmy w takim przy-
padku zastąpić empty na końcu listy dana-lista-liczb1 listą dana-lista-liczb2:
236 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
(zastap-empty-lista (cons 1 empty) L)
;; oczekiwana wartość:
(cons 1 L)
(zastap-empty-lista (cons 2 (cons 1 empty)) L)
;; oczekiwana wartość:
(cons 2 (cons 1 L))
(zastap-empty-lista (cons 2 (cons 11 (cons 1 empty))) L)
;; oczekiwana wartość:
(cons 2 (cons 11 (cons 1 L)))
W powyższych przykladach L ponownie reprezentuje dowolną listę liczb.
Przyklady sugerują, że tak dlugo, jak drugi argument jest listą, nie ma znaczenia, co
on zawiera; w przeciwnym przypadku nie mialoby sensu zastępowanie empty drugim
argumentem. Oznacza to, że mając na uwadze pierwszy argument, powinniśmy wyko-
rzystać szablon dla funkcji przetwarzających listy:
(define (zastap-empty-lista dana-lista-liczb1 dana-lista-liczb2)
(cond
((empty? dana-lista-liczb1) & )
(else & (first dana-lista-liczb1) & (zastap-empty-lista (rest dana-lista-liczb1)
dana-lista-liczb2) & )))
Drugi argument traktujemy na razie tak, jakby byl daną atomową.
Wypelnijmy teraz puste miejsca w szablonie zgodnie z zaleceniami metody projekto-
wania. Jeśli lista dana-lista-liczb1 jest pusta, funkcja zastap-empty-lista zwraca dana-lista-liczb2
zgodnie z naszymi przykladami. W drugiej klauzuli wyrażenia cond, odpowiadającej danej
na wejściu niepustej liście dana-lista-liczb1, musimy przeanalizować dostępne wyrażenia:
(1) (first dana-lista-liczb1) wyciąga pierwszy element listy,
(2) (zastap-empty-lista (rest dana-lista-liczb1) dana-lista-liczb2) zamienia empty na liście
(rest dana-lista-liczb1) listą dana-lista-liczb2.
Aby lepiej zrozumieć, co to oznacza, przeanalizuj poniższy przyklad:
(zastap-empty-lista (cons 2 (cons 11 (cons 1 empty))) L)
;; oczekiwana wartość:
(cons 2 (cons 11 (cons 1 L)))
Powyżej (first dana-lista-liczb1) wynosi 2, (rest dana-lista-liczb1) ma wartość (cons 11 (cons
1 empty)), zaś (zastap-empty-lista (rest dana-lista-liczb1) dana-lista-liczb2) zwraca wartość
(cons 11 (cons 1 dana-lista-liczb2)). A
ącząc liczbę 2 z ostatnią wartością za pomocą in-
strukcji cons, możemy otrzymać pożądany wynik. Ogólnie:
(cons (first dana-lista-liczb1) (zastap-empty-lista (rest dana-lista-liczb1) dana-lista-
liczb2))
jest wynikiem drugiej klauzuli wyrażenia cond. Listing 17.1 zawiera kompletną definicję
funkcji.
JEDNOCZESNE PRZETWARZANIE DWÓCH LIST. PRZYPADEK 2. 237
Listing 17.1. Kompletna definicja funkcji zastap-empty-lista
;; zastap-empty-lista : lista-liczb lista-liczb -> lista-liczb
;; tworzy nową listę zastępując empty w liście dana-lista-liczb1 listą dana-lista-liczb2
(define (zastap-empty-lista dana-lista-liczb1 dana-lista-liczb2)
(cond
((empty? dana-lista-liczb1) dana-lista-liczb2)
(else (cons (first dana-lista-liczb1) (zastap-empty-lista (rest dana-lista-liczb1)
dana-lista-liczb2)))))
Ćwiczenia
Ćwiczenie 17.1. W wielu ćwiczeniach używaliśmy operacji append języka Scheme, która
pobiera trzy listy i zestawia ich elementy w jedną listę:
(append (list 'a) (list 'b 'c) (list 'd 'e 'f))
;; oczekiwana wartość:
(list 'a 'b 'c 'd 'e 'f)
Wykorzystaj funkcję zastap-empty-lista do zdefiniowania funkcji nasz-append, która
powinna dzialać identycznie jak append udostępniany w języku Scheme.
Ćwiczenie 17.2. Opracuj funkcję krzyzuj, która pobierze listę symboli oraz listę liczb
i zwróci wszystkie możliwe pary symboli z liczbami.
Przyklad:
(krzyzuj '(a b c) '(1 2))
;; oczekiwana wartość:
(list (list 'a 1) (list 'a 2) (list 'b 1) (list 'b 2) (list 'c 1) (list 'c 2))
Jedn>czesne przetwarzanie dwóch list. Przypadek 2.
W rozdziale 10. opracowaliśmy funkcję godziny->wynagrodzenie obliczającą wynagro-
dzenie pracowników na podstawie przepracowanych godzin. Funkcja pobierala listę
liczb (przepracowanych przez pracowników godzin) i zwracala inną listę liczb (należ-
nych wynagrodzeń). Dla uproszczenia zalożyliśmy, że wszyscy pracownicy mają taką
samą stawkę godzinową. Nawet jednak male firmy zatrudniają pracowników na zróż-
nicowanych warunkach. Przeważnie księgowy firmy utrzymuje dwa zbiory informacji:
stalą, która między innymi zawiera stawkę godzinową danego pracownika, oraz tym-
czasową, w której zawarta jest informacja o liczbie przepracowanych w ostatnich mie-
siącach godzin.
Nowy, rozszerzony opis problemu oznacza, że funkcja powinna pobierać dwie listy.
Aby uprościć sobie ten problem, zalóżmy, że listy zawierają jedynie liczby: jedna 
stawki godzinowe, druga  liczby przepracowanych godzin. Oto nasz kontrakt, opis
celu i naglówek:
238 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
;; godziny->wynagrodzenia : lista-liczb lista-liczb -> lista-liczb
;; konstruuje nową listę zawierającą iloczyny odpowiednich
;; elementów list dana-lista-liczb1 i dana-lista-liczb2
;; ZAA
OŻEN�E: listy mają równą dlugość
(define (godziny->wynagrodzenia dana-lista-liczb1 dana-lista-liczb2) & )
Możemy traktować listę dana-lista-liczb1 jako listę stawek godzinowych, zaś dana-lista-
liczb2 jako listę przepracowanych w ostatnim miesiącu godzin. Aby otrzymać listę wy-
nagrodzeń, musimy przemnożyć odpowiednie liczby z obu list.
Spójrzmy na kilka przykladów:
(godziny->wynagrodzenia empty empty)
;; oczekiwana wartość:
empty
(godziny->wynagrodzenia (cons 5.65 empty) (cons 40 empty))
;; oczekiwana wartość:
(cons 226.0 empty)
(godziny->wynagrodzenia (cons 5.65 (cons 8.75 empty))
(cons 40.0 (cons 30.0 empty)))
;; oczekiwana wartość:
(cons 226.0 (cons 262.5 empty))
We wszystkich trzech przykladach na wejściu funkcji podano pary list takich samych
dlugości. Jak napisaliśmy w dodatku do opisu celu, funkcja zaklada, że dane spelniają ten
warunek  i faktycznie, stosowanie funkcji z naruszeniem tego warunku nie ma sensu.
Warunek dotyczący danych wejściowych można wyjaśnić podczas opracowywania
szablonu. Konkretnie, warunek mówi, że (empty? dana-lista-liczb1) ma wartość true wtedy
i tylko wtedy, gdy (empty? dana-lista-liczb2) ma wartość true. Co więcej, (cons? dana-lista-
liczb1) ma wartość true wtedy i tylko wtedy, gdy (cons? dana-lista-liczb2) ma wartość true.
�nnymi slowy, warunek upraszcza projekt struktury wyrażeń warunkowych cond w sza-
blonie, ponieważ oznacza, że szablon jest podobny do szablonu dla funkcji przetwarza-
jących listy:
(define (godziny->wynagrodzenia dana-lista-liczb1 dana-lista-liczb2)
(cond
((empty? dana-lista-liczb1) & )
(else & )))
W pierwszej klauzuli cond zarówno dana-lista-liczb1 jak i dana-lista-liczb2 są listami
pustymi  empty. Nie potrzebujemy więc żadnego selektora. W drugiej klauzuli za-
równo dana-lista-liczb1 jak i dana-lista-liczb2 są skonstruowanymi listami, co oznacza, że
potrzebujemy czterech selektorów:
(define (godziny->wynagrodzenia dana-lista-liczb1 dana-lista-liczb2)
(cond
((empty? dana-lista-liczb1) & )
JEDNOCZESNE PRZETWARZANIE DWÓCH LIST. PRZYPADEK 2. 239
(else
& (first dana-lista-liczb1) & (first dana-lista-liczb2) &
& (rest dana-lista-liczb1) & (rest dana-lista-liczb2) & )))
Ponieważ ostatnie dwa selektory dotyczą list o identycznych dlugościach, w oczywisty
sposób możemy je wykorzystać w naturalnej rekursji funkcji godziny->wynagrodzenia:
(define (godziny->wynagrodzenia dana-lista-liczb1 dana-lista-liczb2)
(cond
((empty? dana-lista-liczb1) & )
(else
& (first dana-lista-liczb1) & (first dana-lista-liczb2) &
& (godziny->wynagrodzenia (rest dana-lista-liczb1) (rest dana-lista-liczb2)) & )))
Jedynym niezwyklym elementem tego szablonu jest rekursywne wywolanie funkcji zlo-
żone z dwóch wyrażeń, z których oba są selektorami dwóch argumentów funkcji. Jak się
już przekonaliśmy, idea dzialania funkcji jest latwa do wytlumaczenia dzięki zalożeniu,
że dana-lista-liczb1 i dana-lista-liczb2 mają równą dlugość.
Podczas definiowania funkcji będziemy postępować zgodnie z zaleceniami metody
projektowania. Pierwszy przyklad oznacza, że odpowiedzią pierwszej klauzuli wyraże-
nia cond powinna być lista pusta  empty. W drugiej klauzuli mamy do dyspozycji trzy
wartości:
(1) (first dana-lista-liczb1), która reprezentuje pierwszy element listy stawek godzino-
wych;
(2) (first dana-lista-liczb2), która reprezentuje pierwszy element listy przepracowanych
godzin; oraz
(3) (godziny->wynagrodzenia (rest dana-lista-liczb1) (rest dana-lista-liczb2)), która jest listą
wynagrodzeń dla reszt list dana-lista-liczb1 i dana-lista-liczb2.
Aby otrzymać ostateczny wynik, musimy jedynie odpowiednio polączyć te wartości.
A dokladniej, zgodnie z opisem celu musimy obliczyć wynagrodzenie dla pierwszego pra-
cownika i skonstruować listę zlożoną z tej wartości i wynagrodzeń pozostalych pracow-
ników. Oznacza to, że odpowiedz
dla drugiej klauzuli wyrażenia cond powinna wyglą-
dać następująco:
(cons (wynagrodzenie (first dana-lista-liczb1) (first dana-lista-liczb2))
(godziny->wynagrodzenia (rest dana-lista-liczb1) (rest dana-lista-liczb2)))
Zewnętrzna funkcja wynagrodzenie pobiera dwa pierwsze elementy i oblicza odpowied-
nie wynagrodzenie. Listing 17.2 zawiera kompletne definicje obu funkcji.
Listing 17.2. Kompletna definicja funkcji godziny->wynagrodzenia
;; godziny->wynagrodzenia : lista-liczb lista-liczb -> lista-liczb
;; konstruuje nową listę zawierającą iloczyny odpowiednich
;; elementów list dana-lista-liczb1 i dana-lista-liczb2
;; ZAA
OŻEN�E: listy mają równą dlugość
240 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
(define (godziny->wynagrodzenia dana-lista-liczb1 dana-lista-liczb2)
(cond
((empty? dana-lista-liczb1) empty)
(else (cons (wynagrodzenie (first dana-lista-liczb1) (first dana-lista-liczb2))
(godziny->wynagrodzenia (rest dana-lista-liczb1) (rest dana-lista-liczb2))))))
;; wynagrodzenie : liczba liczba -> liczba
;; oblicza wynagrodzenie na podstawie danych liczb: stawka-godzinowa oraz
przepracowane-godziny
(define (wynagrodzenie stawka-godzinowa przepracowane-godziny)
(" stawka-godzinowa przepracowane-godziny))
Ćwiczenia
Ćwiczenie 17.3. W rzeczywistym świecie funkcja godziny->wynagrodzenia pobieralaby li-
stę struktur reprezentujących pracowników i listę struktur reprezentujących przebieg
prac w ostatnim miesiącu. Struktura pracownika zawiera jego nazwisko, numer PESEL
oraz stawkę godzinową. Struktura opisująca przebieg pracy zawiera nazwisko pracow-
nika i liczbę przepracowanych w danym miesiącu godzin. Wynikiem jest lista struktur
zawierających nazwisko pracownika i należne mu wynagrodzenie.
Zmodyfikuj funkcję z listingu 17.2 tak, aby pracowala na powyższych klasach da-
nych. Opracuj potrzebne definicje struktur i definicje danych. Zastosuj metodę projek-
towania w procesie modyfikacji funkcji.
Ćwiczenie 17.4. Opracuj funkcję zepnij, która pobierze listę nazwisk oraz listę numerów
telefonicznych i polączy je w listę podobną do książki telefonicznej. Zakladając, że ma-
my następującą definicję struktury:
(define struct wpis (nazwisko numer))
pojedynczy wpis w książce telefonicznej konstruujemy za pomocą instrukcji (make-wpis
s n), gdzie s jest symbolem, a n jest liczbą. Zalóż, że dane na wejściu listy mają identyczne
dlugości. Uprość definicję na tyle, na ile będzie to możliwe.
Jedn>czesne przetwarzanie dwóch list. Przypadek 3.
Oto trzeci opis problemu przedstawiony w formie kontraktu, opisu celu i naglówka:
;; wybierz-z-listy : lista-symboli N[>= 1] -> symbol
;; określa n-ty symbol na liście dana-lista-symboli, licząc od 1;
;; sygnalizuje bląd, jeśli na danej liście nie ma n-tego symbolu
(define (wybierz-z-listy dana-lista-symboli n) & )
JEDNOCZESNE PRZETWARZANIE DWÓCH LIST. PRZYPADEK 3. 241
Powyższy program wymaga opracowania funkcji, która będzie pobierać liczbę naturalną
i listę symboli. Obie dane wejściowe należą do klas opisanych skomplikowanymi defini-
cjami danych, jednak inaczej niż w dwóch poprzednich problemach, klasy te są calkowi-
cie rozlączne. Na listingu 17.3 przypominamy obie definicje.
Listing 17.3. Definicje danych dla funkcji wybierz-z-listy
Definicje danych:
liczba naturalna [>=1] (N[>=1]) jest albo:
(1) 1, albo
(2) (dodaj1 n), jeśli n należy do N[>=1].
lista-symboli jest albo:
(1) listą pustą, empty, albo
(2) (cons s ls), gdzie s jest symbolem, a ls jest listą symboli.
Ponieważ problem jest nietypowy, powinniśmy upewnić się, że nasze przyklady
obejmują wszystkie ważne przypadki. Ten cel osiągamy zazwyczaj wybierając po jed-
nym przykladzie dla każdej klauzuli z definicji i wybierając losowo elementy dla pozo-
stalych, prostych elementów danych. W tym przykladzie taka procedura prowadzi nas
do wybrania co najmniej dwóch elementów dla danej lista-symboli i dwóch dla N[>= 1].
Wybierzmy empty i (cons 'a empty) dla listy, oraz 1 i 3 dla liczb naturalnych. Po dwa
przyklady dla obu argumentów oznaczają, że będziemy mieli ich lącznie cztery, nie mamy
jednak danego wprost związku pomiędzy tymi dwoma argumentami, ani żadnych ogra-
niczeń wspomnianych w kontrakcie:
(wybierz-z-listy empty 1)
;; oczekiwane zachowanie:
(error 'wybierz-z-listy "& ")
(wybierz-z-listy (cons 'a empty) 1)
;; oczekiwana wartość:
'a
(wybierz-z-listy empty 3)
;; oczekiwane zachowanie:
(error 'wybierz-z-listy "& ")
(wybierz-z-listy (cons 'a empty) 3)
;; oczekiwane zachowanie:
(error 'wybierz-z-listy "& ")
Tylko jeden z czterech wyników jest symbolem; w pozostalych przypadkach otrzymali-
śmy blędy związane z brakiem elementów na danych listach.
242 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
Dyskusja o przykladach wykazala, że istnieją faktycznie cztery możliwe, niezależne
przypadki, które musimy brać pod uwagę podczas projektowania funkcji. Możemy ana-
lizować te przypadki za pomocą tabeli zawierającej niezbędne warunki:
(empty? dana-lista-symboli) (cons? dana-lista-symboli)
(= n 1)
(> n 1)
Wiersze tabeli opisują dane wejściowe, dla których funkcja wybierz-z-listy musi określić,
co podano jako listę symboli; w kolumnach rozróżniamy dane liczby naturalne. Co wię-
cej, w tabeli mamy cztery pola, z których każde reprezentuje przypadek, w którym za-
równo warunek odpowiedniej kolumny jak i wiersza ma wartość true. Możemy to wy-
razić za pomocą wyrażeń z operatorem and w odpowiednich komórkach tabeli:
(empty? dana-lista-symboli) (cons? dana-lista-symboli)
(= n 1) (and (= n 1) (empty? dana-lista-symboli)) (and (= n 1) (cons? dana-lista-symboli))
(> n 1) (and (> n 1) (empty? dana-lista-symboli)) (and (> n 1) (cons? dana-lista-symboli))
A
atwo teraz wykazać, że dla dowolnej danej pary argumentów dokladnie jeden z czte-
rech warunków zawartych w komórkach tabeli powyżej i ma wartość true.
Korzystając z naszej analizy przypadków, możemy teraz zaprojektować pierwszą
część szablonu  wyrażenie warunkowe:
(define (wybierz-z-listy dana-lista-symboli n)
(cond
[(and (= n 1) (empty? dana-lista-symboli)) & ]
[(and (> n 1) (empty? dana-lista-symboli)) & ]
[(and (= n 1) (cons? dana-lista-symboli)) & ]
[(and (> n 1) (cons? dana-lista-symboli)) & ]))
Wyrażenie cond sprawdza wszystkie cztery warunki wyróżniając wszystkie możliwości.
Następnie, jeśli to możliwe, musimy dodać selektory do każdej klauzuli tego wyrażenia:
(define (wybierz-z-listy dana-lista-symboli n)
(cond
[(and (= n 1) (empty? dana-lista-symboli))
& ]
[(and (> n 1) (empty? dana-lista-symboli))
& (odejmij1 n) & ]
[(and (= n 1) (cons? dana-lista-symboli))
& (first dana-lista-symboli) & (rest dana-lista-symboli)& ]
[(and (> n 1) (cons? dana-lista-symboli))
& (odejmij1 n) & (first dana-lista-symboli) & (rest dana-lista-symboli) & ]))
JEDNOCZESNE PRZETWARZANIE DWÓCH LIST. PRZYPADEK 3. 243
Dla liczby naturalnej n szablon zawiera co najwyżej jeden selektor, który określa po-
przednika tej liczby w zbiorze liczb naturalnych. Dla listy dana-lista-symboli możliwe są
maksymalnie dwa selektory. Jednak w przypadku, w którym prawdziwy jest warunek
(= n 1) lub (empty? dana-lista-symboli), czyli jeden z dwóch argumentów jest atomowy,
nie ma potrzeby stosowania odpowiadających tym danym wejściowym selektorów.
Ostatni krok w procesie konstruowania szablonu wymaga wypisania szablonu z za-
znaczonymi rekursjami dla wyrażeń, w których wyrażenia selektorów zwracają dane na-
leżące do tej samej klasy, co dane wejściowe. W szablonie dla funkcji wybierz-z-listy takie
dzialanie ma sens jedynie dla ostatniej klauzuli cond, która zawiera wyrażenia zarówno
dla N[>= 1], jak i dla listy symboli. Wszystkie inne klauzule zawierają co najwyżej jedno
odpowiednie wyrażenie. Nie jest jednak do końca jasne, jak sformulować w tym przy-
padku naturalną rekursję. Jeśli zbagatelizujemy cel funkcji i w kroku konstruowania sza-
blonu wypiszemy wszystkie możliwe rekursje, otrzymamy trzy przypadki:
(wybierz-z-listy (rest dana-lista-symboli) (odejmij1 n))
(wybierz-z-listy dana-lista-symboli (odejmij1 n))
(wybierz-z-listy (rest dana-lista-symboli) n)
Ponieważ nie wiemy, ani która rekursja ma w tym przykladzie zastosowanie, ani czy
możemy wykorzystać wszystkie trzy rekursje, przechodzimy do następnego etapu.
Zgodnie z metodą projektowania, przeanalizujmy każdą z klauzul wyrażenia cond
naszego szablonu i znajdz
my prawidlową odpowiedz
na powyższe pytanie:
(1) Jeśli warunek (and (= n 1) (empty? dana-lista-symboli)) jest prawdziwy, funkcja wy-
bierz-z-listy powinna wybrać pierwszy element z pustej listy, co jest niemożliwe.
Odpowiedzią funkcji będzie więc sygnalizacja o blędzie.
(2) Jeśli warunek (and (> n 1) (empty? dana-lista-symboli)) jest prawdziwy, funkcja wy-
bierz-z-listy powinna znowu wybrać element z pustej listy. Odpowiedzią jest więc
znowu bląd.
(3) Jeśli warunek (and (= n 1) (cons? dana-lista-symboli)) jest prawdziwy, funkcja wy-
bierz-z-listy powinna zwrócić pierwszy element danej listy. Selektor (first dana-
lista-symboli) przypomina nam, jak uzyskać ten element. Wlaśnie on będzie odpo-
wiedzią funkcji.
(4) W ostatniej klauzuli, jeśli warunek (and (> n 1) (cons? dana-lista-symboli)) jest praw-
dziwy, musimy przeanalizować, co zwracają poszczególne selektory:
(a) (first dana-lista-symboli) wybiera pierwszy element z listy symboli;
(b) (rest dana-lista-symboli) reprezentuje resztę listy; oraz
(c) (odejmij1 n) zwraca liczbę mniejszą od jeden od danego indeksu listy.
Rozważmy przyklad ilustrujący znaczenie powyższych wyrażeń. Przypuśćmy, że
funkcję wybierz-z-listy zastosowano dla listy (cons 'a (cons 'b empty)) i liczby 2:
(wybierz-z-listy (cons 'a (cons 'b empty)) 2)
Funkcja powinna zwrócić symbol 'b, ponieważ (first dana-lista-symboli) zwróci 'a,
natomiast (odejmij1 n) zwróci 1. Poniżej przedstawiamy efekty ewentualnego zasto-
sowania trzech naturalnych rekursji dla tych wartości:
244 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
(a) (wybierz-z-listy (cons 'b empty) 1) zwraca 'b, czyli pożądaną wartość;
(b) (wybierz-z-listy (cons 'a (cons 'b empty)) 1) zwraca wartość 'a, która jest sym-
bolem, ale nie jest oczekiwaną wartością dla naszego problemu;
(c) (wybierz-z-listy (cons 'b empty) 2) sygnalizuje bląd, ponieważ indeks jest więk-
szy niż dlugość listy.
Powyższa analiza sugeruje, że powinniśmy użyć wyrażenia (wybierz-z-listy (cons 'b
empty) 1) jako odpowiedzi ostatniej klauzuli cond. Oparte na przykladzie rozwią-
zania są jednak często zawodne, powinniśmy więc spróbować zrozumieć, dlaczego
to wyrażenie jest odpowiednie dla naszej funkcji.
Przypomnij sobie, że zgodnie z opisem celu,
(wybierz-z-listy (rest dana-lista-symboli) (odejmij1 n))
wybiera element o indeksie (n-1) z listy (rest dana-lista-liczb). �nnymi slowy, zmniejszamy
indeks o 1, skracamy listę o jeden element i szukamy w nowej liście elementu o zmniej-
szonym indeksie. Wyrażenie zwraca wartość zgodną z oczekiwaniami, podobnie jak
odpowiedz
klauzuli z warunkiem (= n 1), przy zalożeniu, że dana-lista-symboli i n są
wartościami zlożonymi. Nasz wybór odpowiedzi dla ostatniej klauzuli jest więc calko-
wicie uzasadniony. Kompletną definicję funkcji wybierz-z-listy przedstawia listing 17.4.
Listing 17.4. Kompletna definicja funkcji wybierz-z-listy
;; wybierz-z-listy : lista-symboli N[>= 1] -> symbol
;; określa n-ty symbol na liście dana-lista-symboli, licząc od 1;
;; sygnalizuje bląd, jeśli na danej liście nie ma n-tego symbolu
(define (wybierz-z-listy dana-lista-symboli n)
(cond
[(and (= n 1) (empty? dana-lista-symboli)) (error 'wybierz-z-listy "lista jest za
krótka")]
[(and (> n 1) (empty? dana-lista-symboli)) (error 'wybierz-z-listy "lista jest za
krótka")]
[(and (= n 1) (cons? dana-lista-symboli)) (first dana-lista-symboli)]
[(and (> n 1) (cons? dana-lista-symboli)) (wybierz-z-listy (rest dana-lista-symboli)
(odejmij1 n))]))
Ćwiczenia
Ćwiczenie 17.5. Opracuj funkcję wybierz-z-listy0, która wybierze elementy z listy podob-
nie jak wybierz-z-listy, ale począwszy od indeksu 0.
Przyklady:
(symbol=? (wybierz-z-listy0 (list 'a 'b 'c 'd) 3)
'd)
(wybierz-z-listy0 (list 'a 'b 'c 'd) 4)
;; oczekiwane zachowanie:
(error 'wybierz-z-listy0 "lista jest za krótka")
UPRASZCZANIE FUNKCJI 245
Upraszczanie funkcji
Funkcja wybierz-z-listy zaprezentowana na listingu 17.4 jest bardziej skomplikowana niż
jest to konieczne. Pierwsza i druga klauzula wyrażenia cond zwracają takie same odpo-
wiedzi: bląd. �nnymi slowy, jeśli wyrażenie:
(and (= n 1) (empty? dana-lista-symboli))
lub
(and (> n 1) (empty? dana-lista-symboli))
ma wartość true, efektem dzialania funkcji jest bląd. Możemy więc wykorzystać to po-
dobieństwo i stworzyć prostsze wyrażenie cond:
(define (wybierz-z-listy dana-lista-symboli n)
(cond
[(or (and (= n 1) (empty? dana-lista-symboli))
(and (> n 1) (empty? dana-lista-symboli))) (error 'wybierz-z-listy "lista jest
za krótka")]
[(and (= n 1) (cons? dana-lista-symboli)) (first dana-lista-symboli)]
[(and (> n 1) (cons? dana-lista-symboli)) (wybierz-z-listy (rest dana-lista-symboli)
(odejmij1 n))]))
Nowe wyrażenie jest prostym przelożeniem naszych obserwacji na język Scheme.
Aby jeszcze bardziej uprościć naszą funkcję, musimy zapoznać się z regulą algebra-
iczną dotyczącą wartości logicznych:
(or (and warunek1 dany-warunek)
(and warunek2 dany-warunek))
= (and (or warunek1 warunek2)
dany-warunek)
Powyższe równanie nazywa się prawem de Morgana. Zastosowanie go w naszej funkcji
spowoduje następujące uproszczenie:
(define (wybierz-z-listy n dana-lista-symboli)
(cond
[(and (or (= n 1) (> n 1))
(empty? dana-lista-symboli)) (error 'wybierz-z-listy "lista jest za krótka")]
[(and (= n 1) (cons? dana-lista-symboli)) (first dana-lista-symboli)]
[(and (> n 1) (cons? dana-lista-symboli)) (wybierz-z-listy (rest dana-lista-symboli)
(odejmij1 n))]))
Rozważ teraz pierwszą część warunku (or (= n 1) (> n 1)). Ponieważ n należy do
zbioru N[>= 1], warunek jest zawsze prawdziwy. Gdybyśmy jednak zastąpili go slowem
true, otrzymalibyśmy warunek:
246 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
(and true
(empty? dana-lista-symboli))
który jest równoważny z warunkiem (empty? dana-lista-symboli). �nnymi slowy, funkcję
możemy zapisać w następujący sposób:
(define (wybierz-z-listy dana-lista-symboli n)
(cond
[(empty? dana-lista-symboli) (error 'wybierz-z-listy "lista jest za krótka")]
[(and (= n 1) (cons? dana-lista-symboli)) (first dana-lista-symboli)]
[(and (> n 1) (cons? dana-lista-symboli)) (wybierz-z-listy (rest dana-lista-symboli)
(odejmij1 n))]))
Ta definicja jest znacznie prostsza niż ta, którą zademonstrowaliśmy na listingu 17.4.
Możemy uprościć naszą definicję jeszcze bardziej. Pierwszy warunek w ostatniej
wersji funkcji wybierz-z-listy odrzuca wszystkie przypadki, w których dana-lista-symboli
jest pusta. Wyrażenie (cons? dana-lista-symboli) w następnych dwóch klauzulach będzie
więc mialo zawsze wartość true. Jeśli zastąpimy warunek tą wartością i uprościmy wyra-
żenie and, otrzymamy najprostszą z możliwych wersję funkcji wybierz-z-listy, którą przed-
stawiliśmy na listingu 17.5. Mimo że ostatnia funkcja jest dużo prostsza od oryginalnej,
ważne jest, byśmy rozumieli, że opracowaliśmy obie wersje w sposób systematyczny i tylko
dzięki temu możemy być pewni, że dzialają one poprawnie. Gdybyśmy próbowali od
początku tworzyć wersję uproszczoną, prędzej czy póz
niej popelnilibyśmy bląd.
Listing 17.5. Uproszczona definicja funkcji wybierz-z-listy
;; wybierz-z-listy : lista-symboli N[>= 1] -> symbol
;; określa n-ty symbol na liście dana-lista-symboli, licząc od 1;
;; sygnalizuje bląd, jeśli na danej liście nie ma n-tego symbolu
(define (wybierz-z-listy dana-lista-symboli n)
(cond
[(empty? dana-lista-symboli) (error 'wybierz-z-listy "lista jest za krótka")]
[(= n 1) (first dana-lista-symboli)]
[(> n 1) (wybierz-z-listy (rest dana-lista-symboli) (odejmij1 n))]))
Ćwiczenia
Ćwiczenie 17.6. Opracuj funkcję zastap-empty-lista zgodnie ze strategią z podrozdzialu
 Jednoczesne przetwarzanie dwóch list. Przypadek 2. . Następnie systematycznie uprasz-
czaj definicję funkcji.
Ćwiczenie 17.7. Uprość definicję funkcji wybierz-z-listy0 z ćwiczenia 17.5 lub wyjaśnij,
dlaczego nie można jej uprościć.
PROJEKTOWANIE FUNKCJI POBIERAJ
CYCH DWIE ZA
OŻONE DANE WEJŚCIOWE 247
Pr>jekt>wanie funkcji p>bierających
dwie zl>ż>ne dane wejści>we
Napotkamy czasem problemy, które wymagają funkcji pobierających dwie zlożone klasy
danych wejściowych. Najbardziej interesujące będą przypadki, w których obie dane będą
mialy nieznane rozmiary. Jak się przekonaliśmy w pierwszych trzech podrozdzialach,
możemy postępować z takimi danymi wejściowymi na trzy różne sposoby.
Odpowiednim podejściem do tego typu problemów jest postępowanie zgodne z za-
leceniami metody projektowania. Przede wszystkim musimy przeprowadzić analizę da-
nych i zdefiniować odpowiednie klasy danych. Następnie możemy stworzyć kontrakt, opis
celu funkcji, które kolejno doprowadzają nas do momentu, w którym możemy przejść
do następnego kroku. Zanim to jednak zrobimy, powinniśmy się zastanowić, z którą z na-
stępujących sytuacji mamy do czynienia:
(1) W niektórych przypadkach jeden z parametrów ma rolę dominującą. � odwrotnie,
możemy traktować jeden z parametrów jako atomowy fragment danych z punktu
widzenia opracowywanej funkcji.
(2) W innych przypadkach oba parametry są zsynchronizowane. Muszą obejmować
tę samą klasę wartości o takiej samej strukturze. Np. jeśli mamy dwie listy, to obie
muszą mieć taką samą dlugość. Jeśli mamy dwie strony WWW, muszą one mieć
taką samą dlugość i jeśli jedna z nich zawiera osadzoną stronę, druga również
musi zawierać taką stronę. Jeśli decydujemy, że dwa parametry mają taki sam status
i muszą być przetwarzane w sposób zsynchronizowany, możemy wybrać jeden
z nich i zorganizować funkcję wokól niego.
(3) Wreszcie, w rzadkich przypadkach, może nie być oczywistego związku pomiędzy
dwoma parametrami. Dla takich danych wejściowych musimy analizować wszyst-
kie możliwe przypadki, zanim opracujemy przyklady i zaprojektujemy szablon.
Dla pierwszych dwóch przypadków stosujemy istniejącą metodę projektowania. Ostatni
przypadek wymaga dodatkowych uwag.
Po tym, jak zdecydujemy, że funkcja należy do trzeciej kategorii, ale zanim opracu-
jemy przyklady i szablon funkcji, musimy opracować dwuwymiarową tabelę. Oto po-
nownie tabela dla funkcji wybierz-z-listy:
dana-lista-symboli
(empty? dana-lista-symboli) (cons? dana-lista-symboli)
(= n 1)
n
(> n 1)
W kolumnach wyliczamy warunki rozróżniające podklasy pierwszego parametru, w wier-
szach wyliczamy warunki dla drugiego parametru.
Tabela pomaga w opracowaniu zarówno zbioru przykladów dla naszej funkcji, jak
i jej szablonu. Jeśli chodzi o przyklady, muszą one pokrywać wszystkie możliwe przy-
padki. Oznacza to, że musimy opracować przynajmniej po jednym przykladzie dla każ-
dej komórki tabeli.
248 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
Jeśli chodzi o szablon, musimy w nim zawrzeć po jednej klauzuli wyrażenia cond
dla każdej komórki. Każda z tych klauzul musi zawierać wszystkie możliwe selektory
dla obu parametrów. Jeśli jeden z nich jest atomowy, nie ma oczywiście potrzeby stoso-
wania selektorów. Wreszcie, zamiast pojedynczej naturalnej rekursji może zaistnieć ko-
nieczność wprowadzenia wielu rekursji. Dla funkcji wybierz-z-listy znalez
liśmy trzy
przypadki. Generalnie wszystkie możliwe kombinacje selektorów są potencjalnymi kan-
dydatami do wykorzystania w naturalnej rekursji. Ponieważ nie możemy wiedzieć, które
z nich są konieczne, a które nie są, wypisujemy je wszystkie i wybieramy te, które będą
odpowiednie dla naszej definicji funkcji.
Podsumowując, projektowanie funkcji dla wielu parametrów opiera się na pewnej
odmianie starej metody projektowania. Kluczowe znaczenie ma przelożenie definicji da-
nych na tabelę demonstrującą wszystkie możliwe i interesujące nas kombinacje. Two-
rzenie przykladów dla funkcji i jej szablonu musi opierać się w jak największym stopniu
wlaśnie na tej tabeli. Wypelnienie pustych przestrzeni w szablonie wymaga, jak zresztą
wszystkie pozostale czynności, praktyki.
Ćwiczenia z przetwarzania
dwóch zl>ż>nych danych wejści>wych
Ćwiczenia
Ćwiczenie 17.8. Opracuj funkcję scalaj, która pobierze dwie listy liczb posortowane ro-
snąco. Wynikiem funkcji będzie pojedyncza, posortowana lista liczb zawierająca wszyst-
kie liczby z obu list (i żadnej innej). Poszczególne liczby powinny występować w liście
wyjściowej tyle razy, ile razy pojawily się w dwóch listach wejściowych.
Przyklady:
(scalaj (list 1 3 5 7 9) (list 0 2 4 6 8))
;; oczekiwana wartość:
(list 0 1 2 3 4 5 6 7 8 9)
(scalaj (list 1 8 8 11 12) (list 2 3 4 8 13 14))
;; oczekiwana wartość:
(list 1 2 3 4 8 8 8 11 12 13 14)
Ćwiczenie 17.9. Celem tego ćwiczenia jest opracowanie nowej wersji gry w szubienicę
z rozdzialu 6. dla slów o dowolnej dlugości.
Stwórz definicję danych reprezentujących slowa dowolnej dlugości za pomocą list.
Litera powinna być reprezentowana przez symbole od 'a do 'z oraz symbol '_.
Opracuj funkcję odslon-liste, która pobierze trzy argumenty:
(1) Wybrane slowo, które należy odgadnąć.
(2) Slowo statusu, które określa, jak dużą część slowa odgadliśmy do te pory.
(3) Literę, która reprezentuje naszą aktualną próbę.
ĆWICZENIA Z PRZETWARZANIA DWÓCH ZA
OŻONYCH DANYCH WEJŚCIOWYCH 249
Funkcja zwróci nowe slowo statusu, które sklada się z dowolnych liter i znaków '_. Pola
w nowym slowie statusu określamy porównując próbę z każdą parą liter ze slowa statusu
i wybranego slowa:
(1) Jeśli próba jest równa danej literze w wybranym slowie, wstawiamy tę literę w od-
powiednie miejsce w slowie statusu.
(2) W przeciwnym przypadku nowa litera odpowiada literze ze slowa statusu.
Przetestuj funkcję odslon-liste dla następujących przykladów:
(odslon-liste (list 't 'e 'a) (list '_ 'e '_) 'u)
(odslon-liste (list 'a 'l 'e) (list 'a '_ '_) 'e)
(odslon-liste (list 'a 'l 'l) (list '_ '_ '_) 'l)
Określ  najpierw ręcznie  jakie powinny być rezultaty powyższych wywolań.
Zastosuj pakiet szkoleniowy hangman.ss i funkcje dorysuj-nastepna-czesc (patrz ćwi-
czenie 6.27) oraz odslon-liste, aby rozegrać grę w szubienicę. Oblicz także wartość nastę-
pującego wyrażenia:
(hangman-list odslon-liste dorysuj-nastepna-czesc)
Funkcja hangman-list (udostępniona we wspomnianym pakiecie nauczania) wybiera lo-
sowe slowo i wyświetla okno z menu wyboru liter. Wybierz litery i gdy będziesz gotowy,
kliknij przycisk Check, aby sprawdzić, czy Twój strzal byl trafny. Powodzenia!
Ćwiczenie 17.10. Robotnicy w fabryce podbijają swoje karty czasowe rano, gdy przy-
chodzą do pracy, i po poludniu  gdy wychodzą. Obecnie stosuje się elektroniczne karty
zawierające numer pracownika i liczbę przepracowanych godzin. Ponadto akta pracow-
nika zawierają zawsze jego nazwisko, numer i stawkę godzinową.
Opracuj funkcję godziny->wynagrodzenia2, która pobierze listę akt pracowniczych oraz
listę (elektronicznych) kart. Funkcja będzie obliczać miesięczne wynagrodzenie każdego
pracownika odpowiednio dopasowując, na podstawie numeru pracownika, dane z jego
akt z danymi zapisanymi na karcie. Jeśli zabraknie danej pary lub numery pracowników
nie będą się zgadzać, funkcja zatrzyma się z odpowiednim komunikatem o blędzie. Zalóż,
że istnieje co najwyżej jedna karta dla jednego pracownika i dla odpowiadającemu mu
numeru.
WskazO
wka: Księgowy posortowalby najpierw obie listy wedlug numerów pracowników.
Ćwiczenie 17.11. Kombinacja liniowa jest sumą kilku skladników liniowych, co oznacza,
że zwraca zmienne i liczby. Te drugie nazywamy w tym kontekście wspólczynnikami.
Oto kilka przykladów:
5 " x
5 " x + 17 " y
5 " x + 17 " y + 3 " z
We wszystkich trzech przykladach wspólczynnikiem przy x jest 5, przy y jest liczba 17,
a jedynym przy z jest 3.
250 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
Jeśli mamy dane wartości zmiennych, możemy określić wartość wielomianu. Np. je-
śli x = 10, wartością iloczynu 5 " x będzie 50; jeśli x = 10 i y = 1, wielomian 5 " x + 17 " y
przyjmie wartość 67; jeśli zaś x = 10, y = 1 i z = 2, wyrażenie 5 " x + 17 " y + 3 " z będzie
mialo wartość 73.
W przeszlości opracowalibyśmy funkcje obliczające wartości liniowych kombinacji
dla poszczególnych wartości. Alternatywną reprezentacją takich wielomianów jest lista
wspólczynników. Powyższe kombinacje bylyby reprezentowane przez takie listy:
(list 5)
(list 5 17)
(list 5 17 3)
Powyższa reprezentacja zaklada, że zgadzamy się zawsze używać zmiennych w okre-
ślonej kolejności.
Opracuj funkcję wartosc, która pobierze reprezentację wielomianu (lista wspólczyn-
ników) oraz listę liczb (wartości zmiennych). Obie listy mają tę samą dlugość. Funkcja
powinna zwrócić wartość tego wielomianu dla danych wartości zmiennych.
Ćwiczenie 17.12. Ewa, Joanna, Dorota i Maria są siostrami, które chcialyby zaoszczędzić
pieniądze i ograniczyć wysilek związany z kupowaniem prezentów gwiazdkowych. Po-
stanowily więc przeprowadzić losowanie, które przypisze każdej z nich jedną osobę, która
następnie zostanie obdarowana prezentem. Ponieważ Joanna jest programistą kompute-
rowym, siostry poprosily ją o napisanie programu, który przeprowadzi losowanie w spo-
sób bezstronny. Program nie może oczywiście przypisać żadnej siostrze jej samej jako
odbiorcy prezentu.
Oto definicja funkcji wybierz-prezent, która pobiera listę różnych imion (symboli) i wy-
biera losowo jeden z ukladów listy, w którym żaden z elementów nie pozostal na swoim
miejscu:
;; wybierz-prezent: lista-imion -> lista-imion
;; wybiera "losowy", inny niż oryginalny uklad imion
(define (wybierz-prezent imiona)
(wybierz-losowo
(nie-takie-same imiona (uklady imiona))))
Przypomnij sobie podobną funkcję z ćwiczenia 12.6, która pobierala listę symboli i zwra-
cala listę wszystkich możliwych ukladów zlożonych z elementów tej listy.
Opracuj zewnętrzne funkcje:
(1) wybierz-losowo : lista-list-imion -> lista-imion, która pobierze listę elementów i loso-
wo wybierze jeden z nich;
(2) nie-takie-same : lista-imion lista-list-imion -> lista-list-imion, która pobierze listę imion
L oraz listę ukladów i zwróci listę takich ukladów, w których żadne imię nie wy-
stępuje na takiej samej pozycji co w danej liście imion.
Dwie permutacje są ze sobą zgodne na pewnej pozycji, jeśli możemy pobrać to
samo imię z obu list za pomocą slowa first lub takiej samej liczby slów rest. Np. li-
sty (list 'a 'b 'c) oraz (list 'c 'a 'b) nie są ze sobą zgodne; natomiast listy (list 'a 'b 'c)
i (list 'c 'b 'a) zgadzają się ze sobą na drugiej pozycji. Możemy to udowodnić sto-
sując dla obu list operację rest poprzedzającą first.
ROZSZERZONE ĆWICZENIE: OBLICZANIE WYRAŻEC
J
ZYKA SCHEME. CZ
ŚĆ 2. 251
Postępuj ostrożnie i zgodnie z odpowiednią metodą projektowania dla każdej klauzuli.
WskazO
wka: Przypomnij sobie, że funkcja (random n) wybiera losową liczbę od 0 do n
(patrz także ćwiczenie 11.5).
Ćwiczenie 17.13. Opracuj funkcję prefiksDNA. Funkcja pobierze dwa argumenty będące
listami symboli (w DNA występują jedynie 'a, 'c, 'g oraz 't, ale możemy to ograniczenie
na razie pominąć). Pierwsza lista nazywana jest wzorcem, druga szukanym łańcuchem.
Funkcja zwraca wartość true, jeśli wzorzec jest prefiksem szukanego lańcucha. We wszyst-
kich innych przypadkach funkcja powinna zwrócić wartość false.
Przyklady:
(PrefiksDNA (list 'a 't) (list 'a 't 'c))
(not (PrefiksDNA (list 'a 't) (list 'a)))
(PrefiksDNA (list 'a 't) (list 'a 't))
(not (PrefiksDNA (list 'a 'c 'g 't) (list 'a 'g)))
(not (PrefiksDNA (list 'a 'a 'c 'c) (list 'a 'c)))
Jeśli to możliwe, uprość funkcję PrefiksDNA.
Zmodyfikuj funkcję tak, aby zwracala pierwszy element szukanego lańcucha, który
nie znalazl się we wzorcu, jeśli oczywiście wzorzec jest prawidlowym prefiksem szuka-
nego lańcucha. Jeśli listy do siebie nie pasują lub wzorzec jest dluższy od szukanego lań-
cucha, zmodyfikowana funkcja powinna nadal zwracać false. Jeśli listy są tej samej dlu-
gości i pasują do siebie, wynikiem powinno być nadal true.
Przyklady:
(symbol=? (PrefiksDNA (list 'a 't) (list 'a 't 'c))
'c)
(not (PrefiksDNA (list 'a 't) (list 'a)))
(PrefiksDNA (list 'a 't) (list 'a 't))
Czy ten wariant funkcji PrefiksDNA może być uproszczony? Jeśli tak, zrób to. Jeśli nie,
wyjaśnij dlaczego.
R>zszerz>ne ćwiczenie:
>bliczanie wyrażeń języka Scheme. Część 2.
Celem tego podrozdzialu jest rozszerzenie możliwości programu stworzonego w roz-
dziale 14. (podrozdzial  Rozszerzone ćwiczenie: obliczanie wyrażeń języka Scheme ) tak,
by mógl radzić sobie z wywolaniami i definicjami funkcji. �nnymi slowy, nowy program
powinien symulować, co staloby się w środowisku DrScheme, gdybyśmy wpisali dane
wyrażenie w oknie Interactions i kliknęli przycisk Execute. Aby uprościć sobie zadanie,
zakladamy, że wszystkie funkcje zdefiniowane w oknie Definitions pobierają po jednym
argumencie.
252 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
Ćwiczenia
Ćwiczenie 17.14. Rozszerz definicję danych z ćwiczenia 14.17 tak, aby bylo możliwe re-
prezentowanie wywolań funkcji w wyrażeniach. Wywolanie powinno być reprezento-
wane jako struktura z dwoma polami. Pierwsze pole zawiera nazwę funkcji, drugie 
jedną reprezentację wyrażenia będącego argumentem funkcji.
Kompletny program obliczający wartości wyrażeń powinien obslugiwać także defi-
nicje funkcji.
Ćwiczenie 17.15. Opracuj definicję struktury i definicję danych dla definicji funkcji.
Przypomnij sobie, że definicja funkcji zawiera trzy istotne atrybuty:
(1) Nazwę funkcji.
(2) Nazwę parametru.
(3) Cialo funkcji.
Taka charakterystyka funkcji sugeruje wprowadzenie struktury z trzema polami. Pierw-
sze dwa zawierają symbole, ostatni reprezentuje cialo funkcji, które jest wyrażeniem.
Przelóż następujące definicje na wartości w języku Scheme:
(define (f x) (+ 3 x))
(define (g x) (" 3 x))
(define (h u) (f (" 2 u)))
(define (i v) (+ (" v v) (" v v)))
(define (k w) (" (h w) (i w)))
Opracuj więcej przykladów i podobnie przelóż je na naszą reprezentację.
Ćwiczenie 17.16. Opracuj funkcję interpretuj-z-jedna-definicja. Funkcja pobierze repre-
zentację wyrażenia Scheme i reprezentację definicji funkcji  P.
Pozostale wyrażenia z ćwiczenia 14.17 powinny być interpretowane jak wcześniej.
W przypadku pojawienia się reprezentacji zmiennej w wyrażeniu funkcja interpretuj-z-
jedna-definicja powinna zasygnalizować bląd. Dla wywolania funkcji P w wyrażeniu funk-
cja interpretuj-z-jedna-definicja powinna:
(1) obliczyć wartość argumentu;
(2) zastąpić wszystkie wystąpienia parametru funkcji P w jej ciele wartością obliczo-
nego w poprzednim kroku argumentu; oraz
(3) obliczyć nowe wyrażenie za pomocą rekursji. Oto szkic takiego dzialania:1
(oblicz-z-jedna-definicja (zastąp & & & )
dana-definicja-funkcji)
Dla wszystkich innych wywolań funkcja interpretuj-z-jedna-definicja powinna sygnalizo-
wać bląd.
1
źmówimy szczególżwż tę fżrmę rekursji w części V.
RÓWNOŚĆ I TESTOWANIE 253
Ćwiczenie 17.17. Opracuj funkcję interpretuj-z-definicjami. Funkcja pobierze reprezentację
wyrażenia Scheme i listę reprezentacji definicji funkcji  definicje. Funkcja powinna
zwrócić liczbę, jaką środowisko DrScheme wyświetliloby w oknie Interactions, gdybyśmy
wpisali wyrażenie reprezentowane przez pierwszy parametr w tym oknie, zaś okno De-
finitions zawieraloby, reprezentowane przez drugi parametr, definicje funkcji.
Pozostale wyrażenia z ćwiczenia 14.17 powinny być interpretowane jak wcześniej.
Dla wywolania funkcji P w wyrażeniu funkcja interpretuj-z-definicjami powinna:
(1) obliczyć wartość argumentu;
(2) znalez
ć definicję odpowiedniej funkcji na liście definicje;
(3) zastąpić wszystkie wystąpienia parametru funkcji P w jej ciele wartością obliczo-
nego w pierwszym kroku argumentu; oraz
(4) obliczyć nowe wyrażenie za pomocą rekursji.
Podobnie jak DrScheme, funkcja interpretuj-z-definicjami sygnalizuje bląd w przypadku
wywolania funkcji, której nazwy nie ma na liście, oraz w przypadku odwolania się do
reprezentacji zmiennej w wyrażeniu.
Równ>ść i test>wanie
Wiele opracowanych przez nas funkcji zwraca listy. Kiedy je testujemy, musimy porów-
nywać dwie listy: wyniki zwracane przez funkcje z przewidywanymi wartościami. Po-
równywanie list ręcznie jest nudne i nie daje pewności, że nie popelniliśmy blędu.
Opracujmy funkcję, która pobiera dwie listy liczb i określa, czy są sobie równe:
;; lista=? : lista-liczb lista-liczb -> boolean
;; określa, czy dana-lista i inna-lista
;; zawierają te same liczby w tym samym porządku
(define (lista=? dana-lista inna-lista) & )
Opis celu ulepsza ogólne przeznaczenie funkcji i przypomina nam, że o ile klienci mogą
uważać dwie listy za równe, jeśli zawierają te same elementy, niezależnie od kolejności,
to programiści są bardziej dokladni i wlączają kolejność elementów jako element porów-
nania. Kontrakt i opis celu pokazują także, że lista=? jest funkcją przetwarzającą dwie
skomplikowane wartości  i w rzeczywistości to nas najbardziej interesuje.
Porównywanie dwóch list oznacza, że musimy przejrzeć wszystkie elementy obu list.
Eliminuje to możliwość projektowania funkcji lista=? linia po linii, jak w przypadku funkcji
zastap-empty-lista z podrozdzialu  Jednoczesne przetwarzanie dwóch list. Przypadek 1. .
Na pierwszy rzut oka nie istnieje żaden związek pomiędzy dwiema listami wejściowymi,
co sugeruje, że powinniśmy wykorzystać zmodyfikowaną metodę projektowania.
Zacznijmy więc od tabeli:
(empty? dana-lista) (cons? dana-lista)
(empty? inna-lista)
(cons? inna-lista)
254 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
Tabela ma cztery komórki do wypelnienia, co oznacza, że potrzebujemy (przynajmniej)
czterech testów i czterech klauzul wyrażenia cond w szablonie.
Oto pięć testów:
(lista=? empty empty)
(not
(lista=? empty (cons 1 empty)))
(not
(lista=? (cons 1 empty) empty))
(lista=? (cons 1 (cons 2 (cons 3 empty)))
(cons 1 (cons 2 (cons 3 empty))))
(not
(lista=? (cons 1 (cons 2 (cons 3 empty)))
(cons 1 (cons 3 empty))))
Drugi i trzeci pokazują, że lista=? musi obslugiwać swoje argumenty symetrycznie. Dwa
ostatnie testy pokazują natomiast, dla jakich danych wejściowych funkcja lista=? powinna
zwracać true lub false.
Trzy z czterech klauzul cond zawierają selektory, natomiast jedna z nich zawiera
naturalne rekursje:
(define (lista=? dana-lista inna-lista)
(cond
[(and (empty? dana-lista) (empty? inna-lista)) & ]
[(and (cons? dana-lista) (empty? inna-lista))
& (first dana-lista) & (rest dana-lista) & ]
[(and (empty? dana-lista) (cons? inna-lista))
& (first inna-lista) & (rest inna-lista) & ]
[(and (cons? dana-lista) (cons? inna-lista))
& (first dana-lista) & (first inna-lista) &
& (lista=? (rest dana-lista) (rest inna-lista)) &
& (lista=? dana-lista (rest inna-lista)) &
& (lista=? (rest dana-lista) inna-lista) & ]))
W czwartej klauzuli mamy trzy naturalne rekursje, ponieważ możemy polączyć parami
dwa selektory oraz możemy polączyć w pary każdy parametr z jednym selektorem.
Od powyższego szablonu do kompletnej definicji dzieli nas jedynie niewielki krok.
Dwie listy mogą zawierać te same elementy tylko wtedy, gdy obie są puste lub skon-
struowane za pomocą instrukcji cons. Ten warunek natychmiast sugeruje wartość true
jako odpowiedz
dla pierwszej klauzuli oraz false dla dwóch następnych. W ostatniej
klauzuli mamy dwie liczby będące pierwszymi elementami obu list oraz trzy naturalne
rekursje. Musimy porównać te dwie liczby. Co więcej, wyrażenie (lista=? (rest dana-lista)
(rest inna-lista)) oblicza, czy reszty obu list są identyczne. Dwie listy są sobie równe wte-
dy i tylko wtedy, gdy spelnione są oba warunki, co oznacza, że musimy je polączyć za
pomocą operatora logicznego and:
RÓWNOŚĆ I TESTOWANIE 255
(define (lista=? dana-lista inna-lista)
(cond
[(and (empty? dana-lista) (empty? inna-lista)) true]
[(and (cons? dana-lista) (empty? inna-lista)) false]
[(and (empty? dana-lista) (cons? inna-lista)) false]
[(and (cons? dana-lista) (cons? inna-lista))
(and (= (first dana-lista) (first inna-lista))
(lista=? (rest dana-lista) (rest inna-lista)))]))
Dwie pozostale naturalne rekursje nie odgrywają dla naszego rozwiązania żadnej roli.
Spójrzmy po raz drugi na związki pomiędzy dwoma parametrami. Pierwszy spo-
sób, w jaki rozwiązaliśmy problem porównywania list, sugeruje, że jeśli dwie listy mają
być sobie równe, to drugi parametr musi mieć identyczny ksztalt jak pierwszy. �naczej
mówiąc, moglibyśmy opracować funkcję opartą na strukturze pierwszego parametru
i sprawdzającą w razie potrzeby strukturę innego parametru.
Pierwszy parametr jest listą liczb, możemy więc ponownie wykorzystać szablon
funkcji przetwarzających listy:
(define (lista=? dana-lista inna-lista)
(cond
[(empty? dana-lista) & ]
[(cons? dana-lista)
& (first dana-lista) & (first inna-lista) &
& (lista=? (rest dana-lista) (rest inna-lista)) & ]))
Jedyną różnicą jest to, że druga klauzula przetwarza drugi parametr w taki sam sposób
jak pierwszy. Takie rozwiązanie bardzo przypomina funkcję godziny->wynagrodzenia z pod-
rozdzialu  Jednoczesne przetwarzanie dwóch list. Przypadek 2. .
Wypelnienie wolnych przestrzeni w szablonie jest trudniejsze niż w pierwszej próbie
rozwiązania tego problemu. Jeśli dana-lista jest pusta, odpowiedz
zależy od drugiej danej
wejściowej: inna-lista. Jak pokazują przyklady, odpowiedzią będzie w tym przypadku true
wtedy i tylko wtedy, gdy inna-lista również będzie listą pustą. Przekladając to na język
Scheme, otrzymamy następującą odpowiedz
dla pierwszej klauzuli: (empty? inna-lista).
Jeśli dana-lista nie jest pusta, szablon sugeruje, że powinniśmy obliczyć odpowiedz

funkcji na podstawie:
(1) (first dana-lista), pierwsza liczba na liście dana-lista;
(2) (first inna-lista), pierwsza liczba na liście inna-lista;
(3) (lista=? (rest dana-lista) (rest inna-lista)), wyrażenie, które określa, czy reszty obu
list są sobie równe.
Mając dany opis celu funkcji i przyklady jej dzialania, możemy po prostu porównać
elementy (first dana-lista) oraz (first inna-lista) i polączyć wynik z naturalną rekursją za
pomocą operacji and:
(and (= (first dana-lista) (first inna-lista))
(lista=? (rest dana-lista) (rest inna-lista)))
256 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
Mimo że wykonany przez nas krok wygląda na prosty, jego efektem jest niepoprawna
definicja. Celem wypisania warunków w wyrażeniu cond jest upewnienie się, że wszyst-
kie selektory są poprawne.
Żaden element w specyfikacji funkcji lista=? nie sugeruje jednak, że inna-lista jest
skonstruowana za pomocą instrukcji cons, jeśli dana-lista jest skonstruowana za pomocą
tej samej instrukcji.
Możemy poradzić sobie z tym problemem za pomocą dodatkowego warunku:
(define (lista=? dana-lista inna-lista)
(cond
[(empty? dana-lista) (empty? inna-lista)]
[(cons? dana-lista)
(and (cons? inna-lista)
(and (= (first dana-lista) (first inna-lista))
(lista=? (rest dana-lista) (rest inna-lista))))]))
Dodatkowym warunkiem jest (cons? inna-lista), co oznacza, że lista=? zwróci false, jeśli
warunek (cons? dana-lista) będzie prawdziwy oraz (cons? inna-lista) będzie falszywy. Jak
pokazują przyklady, taki wlaśnie powinien być pożądany efekt.
Podsumowując, funkcja lista=? pokazuje, że czasami możemy zastosować więcej niż
jedną metodę projektowania w celu opracowania danej funkcji. Efekty prac są różne,
mimo że są ze sobą blisko powiązane; faktycznie, moglibyśmy udowodnić, że obie funk-
cje zwracają zawsze takie same wyniki dla tych samych danych wejściowych. Podczas
drugiego procesu tworzenia funkcji wykorzystaliśmy także spostrzeżenia z pierwszej
próby.
Ćwiczenia
Ćwiczenia 17.18. Przetestuj obie wersje funkcji lista=?.
Ćwiczenie 17.19. Uprość pierwszą wersję funkcji lista=?. Oznacza to, że powinieneś po-
lączyć sąsiadujące klauzule wyrażenia cond, które zwracają takie same wyniki, lącząc
ich warunki za pomocą operatora or. Jeśli to konieczne, poprzestawiaj klauzule i użyj
slowa else w ostatniej klauzuli w ostatecznej wersji funkcji.
Ćwiczenie 17.20. Opracuj funkcję sym-lista=?. Funkcja określi, czy dwie listy symboli są
sobie równe.
Ćwiczenie 17.21. Opracuj funkcję zawiera-te-same-liczby, która określi, czy dwie listy liczb
zawierają te same liczby, niezależnie od ich kolejności. Np. wyrażenie:
(zawiera-te-same-liczby (list 1 2 3) (list 3 2 1))
zwróci wartość true.
Ćwiczenie 17.22. Klasy liczb, symboli i wartości logicznych nazywamy czasami atomami:2
2
Niektórzy wlączają dż tej klasy także wartżść empty i pżjedyncze znaki.
RÓWNOŚĆ I TESTOWANIE 257
atom jest albo:
(1) liczbą;
(2) wartością logiczną (boolean);
(3) symbolem.
Opracuj funkcję rowne-listy?, która pobierze dwie listy atomów i określi, czy są sobie
równe.
Porównanie obu wersji funkcji lista=? sugeruje, że druga wersja jest latwiejsza do
zrozumienia od pierwszej. Stwierdzamy w niej, że dwie zlożone wartości są sobie równe,
jeśli druga jest stworzona za pomocą tego samego konstruktora co pierwsza oraz jeśli ele-
menty wykorzystane w tym konstruktorze są takie same. Ten pomysl można wykorzy-
stać podczas opracowywania innych funkcji porównujących ze sobą dane wejściowe.
Aby potwierdzić nasze przypuszczenie, spójrzmy na funkcję porównującą strony
WWW:
;; www=? : strona-www strona-www -> boolean
;; określa, czy dana-strona i inna-strona mają taki sam ksztalt drzewa
;; i zawierają te same symbole ulożone w tym samym porządku
(define (www=? dana-strona inna-strona) & )
Przypomnij sobie definicję dla prostych stron WWW:
strona-WWW (w skrócie SW) jest albo:
(1) empty;
(2) (cons s sw), gdzie s jest symbolem, zaś sw jest stroną WWW;
(3) (cons esw sw), gdzie esw i sw są stronami WWW.
Definicja danych zawiera trzy klauzule, co oznacza, że jeśli chcielibyśmy opracować funk-
cję www=? zgodnie ze zmodyfikowaną metodą projektowania, musielibyśmy przestu-
diować dziewięć przypadków. Wykorzystując zamiast tego doświadczenie zdobyte pod-
czas tworzenia funkcji lista=?, możemy rozpocząć pracę od prostego szablonu dla stron
WWW:
(define (www=? dana-strona inna-strona)
(cond
[(empty? dana-strona) & ]
[(symbol? (first dana-strona))
& (first dana-strona) & (first inna-strona) &
& (www=? (rest dana-strona) (rest inna-strona)) & ]
[else
& (www=? (first dana-strona) (first inna-strona)) &
& (www=? (rest dana-strona) (rest inna-strona)) & ]))
258 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
W drugiej klauzuli wyrażenia cond ponownie musimy postępować podobnie jak w przy-
padku funkcji godziny->wynagrodzenia i lista=?. Oznacza to, że mówimy, iż inna-strona
musi mieć taki sam ksztalt co dana-strona, jeśli ma być identyczna i mamy przetwarzać obie
strony w analogiczny sposób. Rozumowanie dla drugiej klauzuli jest podobne.
W miarę ulepszania powyższego szablonu musimy znowu dodać warunki związane
z parametrem inna-strona, aby upewnić się, że odpowiednie selektory będą dzialać po-
prawnie:
(define (www=? dana-strona inna-strona)
(cond
[(empty? dana-strona) (empty? inna-strona)]
[(symbol? (first dana-strona))
(and (and (cons? inna-strona) (symbol? (first inna-strona)))
(and (symbol=? (first dana-strona) (first inna-strona))
(www=? (rest dana-strona) (rest inna-strona))))]
[else
(and (and (cons? inna-strona) (list? (first inna-strona)))
(and (www=? (first dana-strona) (first inna-strona))
(www=? (rest dana-strona) (rest inna-strona))))]))
Musimy zwlaszcza upewnić się w drugiej i trzeciej klauzuli, że inna-strona jest skonstru-
owaną listą, oraz że jej pierwszy element jest symbolem lub listą. W przeciwnym przy-
padku funkcja bylaby analogiczna z funkcją lista=? i dzialalaby w identyczny sposób.
Ćwiczenia
Ćwiczenie 17.23. Narysuj tabelę opartą na definicji danych dla prostej strony WWW.
Opracuj przynajmniej po jednym przykladzie dla każdego z dziewięciu przypadków.
Przetestuj funkcję www=? dla tych przykladów.
Ćwiczenie 17.24. Opracuj funkcję posn=?, która pobiera dwie struktury posn i określa,
czy są identyczne.
Ćwiczenie 17.25. Opracuj funkcję drzewo=?, która pobierze dwa drzewa binarne i określi,
czy są identyczne.
Ćwiczenie 17.26. Przeanalizuj poniższe dwie wzajemnie rekursywne definicje danych:
s-lista jest albo:
(1) listą pustą, empty, albo
(2) (cons s sl), gdzie s jest s-wyr, zaś sl jest listą s-lista.
s-wyr jest albo:
(1) liczbą,
(2) wartością logiczną,
(3) symbolem,
(4) listą s-lista.
RÓWNOŚĆ I TESTOWANIE 259
Opracuj funkcję s-lista=?, która pobiera dwie listy s-lista i określa, czy są identyczne. Po-
dobnie jak w przypadku list liczb, dwie listy zgodne z definicją klasy s-lista są sobie
równe, jeśli zawierają te same elementy na analogicznych pozycjach.
Skoro przeanalizowaliśmy już problem równości pewnych wartości, możemy wró-
cić do oryginalnego z
ródla rozważań w tym rozdziale: funkcji testujących. Przypuśćmy,
że chcemy przetestować funkcję godziny->wynagrodzenia z podrozdzialu  Jednoczesne
przetwarzanie dwóch list. Przypadek 2. :
(godziny->wynagrodzenia (cons 5.65 (cons 8.75 empty))
(cons 40 (cons 30 empty)))
= (cons 226.0 (cons 262.5 empty))
Jeśli po prostu wpiszemy wywolanie tej funkcji w oknie Interactions lub dodamy je na
końcu okna Definitions, musimy ręcznie porównać otrzymany wynik z przewidywaną
wartością. Dla krótkich list, podobnych do powyższej, jest to możliwe; dla dlugich list,
glębokich stron WWW lub innych dużych danych zlożonych ręczne porównywanie mo-
że być z
ródlem blędów.
Korzystając z funkcji porównujących podobnych do lista=?, możemy znacznie zre-
dukować konieczność ręcznego porównywania wyników testów. W naszym obecnym
przypadku możemy dodać następujące wyrażenie:
(lista=?
(godziny->wynagrodzenia (cons 5.65 (cons 8.75 empty))
(cons 40 (cons 30 empty)))
(cons 226.0 (cons 262.5 empty)))
na końcu okna Definitions. Jeśli klikniemy teraz przycisk Execute, musimy tylko odczytać
w oknie Interactions, czy wszystkie podobne testy zwrócily wartość true.
W rzeczywistości możemy iść jeszcze dalej. Możemy napisać funkcję testującą po-
dobną do tej z listingu 17.6. Klasa wynik-testow sklada się z wartości i listy czterech ele-
mentów: lańcucha "zle wyniki testów:" i trzech list. Korzystając z naszej nowej zewnętrz-
nej funkcji, możemy przetestować godziny->wynagrodzenia w sposób następujący:
(testuj-godziny->wynagrodzenia
(cons 5.65 (cons 8.75 empty))
(cons 40 (cons 30 empty))
(cons 226.0 (cons 262.5 empty)))
Listing 17.6. Funkcja testująca
;; testuj-godziny->wynagrodzenia : lista-liczb lista-liczb lista-liczb -> wynik-testow
;; testuje funkcję godziny->wynagrodzenia
(define (testuj-godziny->wynagrodzenia dana-lista inna-lista oczekiwany-wynik)
(cond
[(lista=? (godziny->wynagrodzenia dana-lista inna-lista) oczekiwany-wynik)
true]
[else
(list "zle wyniki testów:" dana-lista inna-lista oczekiwany-wynik)]))
260 17. PRZETWARZANIE DWÓCH SKOMPLIKOWANYCH ELEMENTÓW DANYCH
Jeśli coś nie zadziala poprawnie w naszych testach, wspomniana czteroelementowa lista
określi dokladnie, w którym przypadku wynik różni się od oczekiwanego.
Testowanie za pomocą równości? Twórcy języka Scheme przewidzieli konieczność sto-
sowania ogólnej funkcji porównującej dane i udostępnili ją:
;; equal? : dowolna-wartosc dowolna-wartosc -> boolean
;; określa, czy dwie wartości są strukturalnie identyczne
;; i zawierają te same wartości atomowe na analogicznych pozycjach
Jeśli stosujemy equal? dla dwóch list, funkcja porównuje je w taki sam sposób, jak robila
to funkcja lista=?; kiedy dajemy na wejściu funkcji equal? parę struktur, to funkcja po-
równuje kolejno odpowiednie pola, jeśli obie dane należą do tego samego typu struktur;
jeśli natomiast uruchomimy funkcję equal? dla dwóch danych atomowych, dane te zo-
staną porównane za pomocą =, symbol=? lub boolean=?, w zależności od ich typu.
Wskazówka d>tycząca test>wania
Używaj funkcji equal? w procesie testowania (jeśli konieczne jest porównywanie
wartości).
Nieposortowane listy: W niektórych przypadkach stosujemy listy, mimo że porządek
elementów nie gra roli. Ważne jest wówczas posiadanie takich funkcji, jak zawiera-te-
same-liczby (patrz ćwiczenie 17.21), jeśli chcemy określić, czy wyniki wywolania jakiejś
funkcji zawierają odpowiednie elementy.
Ćwiczenia
Ćwiczenie 17.27. Zdefiniuj, za pomocą funkcji equal?, funkcję testującą funkcję zastap-
empty-lista z podrozdzialu  Jednoczesne przetwarzanie dwóch list. Przypadek 1. . Sfor-
muluj także przyklady będące przypadkami testowymi w tej funkcji.
Ćwiczenie 17.28. Zdefiniuj funkcję testuj-wybierz-z-listy, która będzie zarządzać przy-
padkami testowymi dla funkcji wybierz-z-listy z podrozdzialu  Jednoczesne przetwarza-
nie dwóch list. Przypadek 1. . Sformuluj przyklady z rozdzialu jako przypadki testowe
dla funkcji testuj-wybierz-z-listy.
Ćwiczenie 17.29. Zdefiniuj funkcję testuj-interpretuj, która będzie przeprowadzać testy
funkcji interpretuj-z-definicjami za pomocą funkcji equal?. Sformuluj ponownie przypadki
testowe za pomocą nowej funkcji.


Wyszukiwarka

Podobne podstrony:
Wstęp do pakietu algebry komputerowej Maple
Wstęp do programowania C
e Wstep do programowania DS
Wstęp do analizy technicznej
Wstep do programowania w jezyku C wstpcp
Wstep do programowania w jezyku C wstpch
Wstep do programowania w jezyku C wstpch
wstęp do programowania
2006 06 Wstęp do Scrum [Inzynieria Oprogramowania]
Wstęp do projektowania 2014 15 wykład 6,7

więcej podobnych podstron