A
Seznam vybraných programů
2.1 Výpočet délky přepony v pravoúhlém trojúhelníku . . . . . . . . . . . . . . . . . . . . . . . . .
51
2.2 Infixovaáplikace procedury dvou argumentů (procedura infix) . . . . . . . . . . . . . . . . .
53
2.3 Rozložení procedury na dvě procedury jednoho argumentu (procedura curry+) . . . . . . . .
53
2.4 Vytářenínových pocedur posunem a násobením . . . . . . . . . . . . . . . . . . . . . . . . . .
59
2.5 Vytváření procedur reprezentujících polynomické funkce . . . . . . . . . . . . . . . . . . . . .
60
2.6 Kompozice dvou procedur (procedura compose2) . . . . . . . . . . . . . . . . . . . . . . . . .
61
2.7 Přibližnásměrnice tečny a přibližná derivace . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
2.8 Procedura negace (procedura not) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
2.9 Predikáty sudých a lichých čísel (procedury even? a odd?) . . . . . . . . . . . . . . . . . . . .
65
2.10 Minumum a maximum ze dvou prvků (procedury min a max) . . . . . . . . . . . . . . . . . . .
69
2.11 Hledání extrémních hodnot (procedura extrem) . . . . . . . . . . . . . . . . . . . . . . . . . .
69
3.1 Procedura dostrel s lokálními vazbami vytvářenými s využitím and. . . . . . . . . . . . . . .
87
3.2 Procedura dostrel s lokálními vazbami vytvářenými pomocíspeciální formy define. . . . .
88
3.3 Procedura derivace s použitím interní definice. . . . . . . . . . . . . . . . . . . . . . . . . . .
91
3.4 Procedura derivace s použitím speciální formy let. . . . . . . . . . . . . . . . . . . . . . . . .
91
4.1 Příklad abstrakční bariéry: výpočet kořenů kvadratické rovnice. . . . . . . . . . . . . . . . . . 104
4.2 Implementace procedury koreny pomocí procedur vyšších řádů . . . . . . . . . . . . . . . . . 105
4.3 Procedury cons, car a cdr (implementace tečkových párů pomocí procedur vyšších řádů) . . 107
5.1 Obraceníseznamu pomocí build-list (procedura reverse) . . . . . . . . . . . . . . . . . . . 123
5.2 Spojení dvou seznamů pomocí build-list (procedura append2) . . . . . . . . . . . . . . . . 124
5.3 Mapování přes jeden seznam pomocí build-list (procedura map1) . . . . . . . . . . . . . . . 126
6.1 Délka seznamu (procedura length) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.2 Filtrace prvků seznam (procedura filter) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.3 Procedury remove a member? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.4 Vrácení prvku na dané pozici (procedura list-ref) . . . . . . . . . . . . . . . . . . . . . . . . 147
6.5 Vrácení pozic výskytu prvku (procedura list-indices) . . . . . . . . . . . . . . . . . . . . . 148
6.6 Test přítomnosti prvku v seznamu s navrácením příznaku (procedura find) . . . . . . . . . . 150
6.7 Součet druhých mocnin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.8 Konstruktor seznamu (procedura list) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.1 Délka seznamu pomocí foldr (procedura length) . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.2 Spojení dvou seznamů pomocí foldr (procedura append2) . . . . . . . . . . . . . . . . . . . . 175
7.3 Spojeníseznamů pomocí foldr (procedura append) . . . . . . . . . . . . . . . . . . . . . . . . 176
7.4 Mapování přes jeden seznam pomocí foldr (procedura map1) . . . . . . . . . . . . . . . . . . 176
7.5 Mapování přes libovolné seznamy pomocí foldr (procedura map) . . . . . . . . . . . . . . . . 177
7.6 Filtrace prvků seznam pomocí foldr (procedura filter) . . . . . . . . . . . . . . . . . . . . . 178
7.7 Test přítomnosti prvku v seznamu pomocí foldr (procedura member?) . . . . . . . . . . . . . 178
7.8 Nahrazování prvků v seznamu pomocí foldr (procedura replace) . . . . . . . . . . . . . . . 178
7.9 Procedury genuine-foldl a foldl pomocí foldr a reverze seznamu . . . . . . . . . . . . . . 183
7.10 Složení libovolného množství procedur pomocí foldl (procedura compose) . . . . . . . . . . 184
7.11 Procedury genuine-foldl a foldl pro libovolný počet seznamů . . . . . . . . . . . . . . . . 185
7.12 Výpočet faktoriálu pomocí procedur vyšších řádů (procedura fac) . . . . . . . . . . . . . . . . 187
7.13 Výpočet prvků Fibinacciho posloupnosti pomocí procedur vyšších řádů (procedura fib) . . . 187
8.1 Rekurzivní procedura počítající xn (procedura expt) . . . . . . . . . . . . . . . . . . . . . . . . 200
329
8.2 Rychlá rekurzivní procedura počítající xn (procedura expt) . . . . . . . . . . . . . . . . . . . . 203
8.3 Rekurzivní výpočet faktoriálu (procedura fac) . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
8.4 Rekurzivní výpočet prvků Fibonacciho posloupnosti (procedura fib) . . . . . . . . . . . . . . 206
8.5 Iterativní faktoriál (procedura fac) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.6 Iterativní faktoriál s interní definicí (procedura fac) . . . . . . . . . . . . . . . . . . . . . . . . 212
8.7 Iterativní verze expt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8.8 Iterativní mocněnís pomocízásobníku (procedura expt) . . . . . . . . . . . . . . . . . . . . . 213
8.9 Iterativní Fibonacciho čísla (procedura fib) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
8.10 Iterativní Fibonacciho čísla s interní definicí (procedura fib) . . . . . . . . . . . . . . . . . . . 218
8.11 Iterativní faktoriál používající pojmenovaný let (procedura fac) . . . . . . . . . . . . . . . . 220
8.12 Iterativní Fibonacciho čísla používající pojmenovaný let (procedura fib) . . . . . . . . . . . 220
8.13 Délka seznamu pomocí rekurze (procedura length) . . . . . . . . . . . . . . . . . . . . . . . . 221
8.14 Délka seznamu pomocí iterace (procedura length) . . . . . . . . . . . . . . . . . . . . . . . . . 221
8.15 Spojení dvou seznamů pomocí rekurze (procedura append2) . . . . . . . . . . . . . . . . . . . 222
8.16 Vrácení prvku na dané pozici pomocí rekurze (procedura list-ref) . . . . . . . . . . . . . . 222
8.17 Vráceníseznamu bez prvních prvků (procedura list-tail) . . . . . . . . . . . . . . . . . . . 223
8.18 Mapování přes jeden seznam pomocí rekurze (procedura map1) . . . . . . . . . . . . . . . . . 223
8.19 Rekurzivní verze vytvářeníseznamů (procedura build-list) . . . . . . . . . . . . . . . . . . 223
8.20 Neefektivní verze vytvářeníseznamů (procedura build-list) . . . . . . . . . . . . . . . . . . 224
8.21 Iterativní verze vytvářeníseznamů (procedura build-list) . . . . . . . . . . . . . . . . . . . 224
8.22 Neefektivní reverze seznamu (procedura reverse) . . . . . . . . . . . . . . . . . . . . . . . . . 225
8.23 Iterativní reverze seznamu (procedura reverse) . . . . . . . . . . . . . . . . . . . . . . . . . . 225
9.1 Rekurzivní výpočet faktoriálu pomocí y-kombinátoru . . . . . . . . . . . . . . . . . . . . . . . 245
9.2 Spojovaníseznamů append naprogramované rekurzivně . . . . . . . . . . . . . . . . . . . . . 249
9.3 Spojovaníseznamů append naprogramované rekurzivně bez použití pomocné procedury . . 249
9.4 Skládání funkcícompose bez použití procedury foldl . . . . . . . . . . . . . . . . . . . . . . . 250
9.5 Implementace procedury hloubkového nahrazovaní atomů depth-replace . . . . . . . . . . 253
10.1 Prohledávánístromu do hloubky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
10.2 Prohledávánístromu do šířky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
10.3 Výpočet potenční množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
10.4 Efektivnější výpočet potenční množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
10.5 Výpočet všech permutací prvků množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
10.6 Výpočet permutace prvků množiny pomocí faktoradických čísel . . . . . . . . . . . . . . . . . 268
10.7 Výpočet všech kombinací prvků množiny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
10.8 Výpočet všech kombinacís opakováním . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
11.1 Procedura pro zjednodušování aritmetických výrazů . . . . . . . . . . . . . . . . . . . . . . . . 273
11.2 Interní definice v proceduře pro zjednodušování výrazů . . . . . . . . . . . . . . . . . . . . . . 274
11.3 Tabulka procedur pro zjednodušování výrazů . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
11.4 Procedura assoc pro vyhledávání v asociačním seznamu . . . . . . . . . . . . . . . . . . . . . 275
11.5 Vylepšená procedura pro zjednodušování aritmetických výrazů . . . . . . . . . . . . . . . . . 276
11.6 Procedura pro symbolickou derivaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
11.7 Procedura prefix→postfix pro převod výrazů do postfixovénotace . . . . . . . . . . . . . 281
11.8 Procedura prefix→polish pro převod výrazů do postfixové bezzávorkovénotace . . . . . . 281
11.9 Procedura prefix→infix pro převod výrazů do infixovénotace . . . . . . . . . . . . . . . . 282
330
11.10 Procedura postfix-eval vyhodnocující postfixové výrazy . . . . . . . . . . . . . . . . . . . . 283
11.11 Jednoduchá tabulka s prostředím vazeb pro postfixovýevaluátor . . . . . . . . . . . . . . . . . 284
11.12 Procedura polish-eval vyhodnocující výrazy v polskénotaci . . . . . . . . . . . . . . . . . . 286
12.1 Procedura match-type? (porovnávání datového typu se vzorem) . . . . . . . . . . . . . . . . 291
12.2 Konkrétní tabulka metod generické procedury . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
12.3 Procedura table-lookup (vyhledání operace v tabulce metod generické procedury) . . . . . 292
12.4 Procedura apply-generic (aplikace generické procedury) . . . . . . . . . . . . . . . . . . . . 292
12.5 Generická procedura pro sčítání . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
12.6 Procedury pro práci s manifestovanými typy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
12.7 Reprezentace tečkových párů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
12.8 Reprezentace prostředí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
12.9 Konstruktor pro globální prostředí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
12.10 Vyhledávání vazeb v prostředí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
12.11 Reprezentace uživatelsky definovaných procedur . . . . . . . . . . . . . . . . . . . . . . . . . . 301
12.12 Převod do interní reprezentace a implementace readeru . . . . . . . . . . . . . . . . . . . . . . 302
12.13 Převod do externí reprezentace Implementace printeru . . . . . . . . . . . . . . . . . . . . . . 303
12.14 Reprezentace primitivních procedur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
12.15 Obecný konvertor seznamu na seznam ve vnitřní reprezentaci a zpět . . . . . . . . . . . . . . 304
12.16 Konverze seznamů na metaseznamy o obráceně . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
12.17 Implementace vlastního vyhodnocovacího procesu . . . . . . . . . . . . . . . . . . . . . . . . . 305
12.18 Tabulka vazeb mezi formálními/skutečnými argumenty (procedura make-bindings) . . . . 307
12.19 Implementace aplikace procedur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
12.20 Definice speciální formy if v globálním prostředí . . . . . . . . . . . . . . . . . . . . . . . . . . 308
12.21 Definice speciální formy and v globálním prostředí . . . . . . . . . . . . . . . . . . . . . . . . . 309
12.22 Definice forem lambda, the-environment a quote v globálním prostředí . . . . . . . . . . . . 310
12.23 Definice selektorů uživatelsky definovaných procedur v globálním prostředí . . . . . . . . . . 310
12.24 Procedura apply-collect-arguments (sestaveníseznamu argumentů pro apply) . . . . . . 310
12.25 Definice eval, apply and env-apply v globálním prostředí . . . . . . . . . . . . . . . . . . . . 311
12.26 Procedura length v prostředí odvozených definic . . . . . . . . . . . . . . . . . . . . . . . . . 312
12.27 Procedura map v prostředí odvozených definic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
12.28 Procedura scm-repl (implementace cyklu REPL) . . . . . . . . . . . . . . . . . . . . . . . . . . 313
331