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