Naprogramujte proceduru euclid, která vypočte největší společný dělitel dvou zadaných čísel pomocí Euklidova algoritmu.
Proceduru implementujte
(a) jako iterativní proceduru, kde je pro modifikaci lokálního prostředí využita speciální forma define,
(b) jako iterativní proceduru pomocí pojmenovaného let.

Příklady použití:
> (euclid 9 24)
3
> (euclid 17 25)
1

Pomocí foldl nebo foldr naprogramujte proceduru count zjišťující počet výskytu prvku v daném seznamu.

Příklady použití:
> (count ’(3 1 3 2 1 2 3 3 3))
((3 . 5) (1 . 2) (2 . 2))
> (count ’(d b a c b b a))
((d . 1) (b . 3) (a . 2) (c . 1))

Vytvořte proceduru histogram, která počítá histogram daného obrázku.
Uvažujte pouze osmibitovou barevnou hloubku, barvy jednotlivých pixelu jsou tedy vyjádřeny čísly 0 až 255.
Obrázek je reprezentován pomocí seznamu, jehož jednotlivé prvky jsou opět seznamy určující hodnoty pixelu na jednotlivých rádcích.
Např., obrázek daný hodnotami pixelu
0 100 80
255 0 255
0 100 255
0 0 0
je reprezentován seznamem
((0 100 80) (255 0 255) (0 100 255) (0 0 0))

Příklady použití:
> (histogram ’((0 100 80) (255 0 255) (0 100 255) (0 0 0)))
((0 . 6) (100 . 2) (80 . 1) (255 . 3))

Pomocí rekurze naprogramujte proceduru map-index-pred.
Tuto proceduru znáte z předchozího úkolu.
Přijímá tři argumenty: predikát , proceduru a seznam = (a1 a2 …an) .
Procedura map-index-pred vrací seznam
(b1 b2 …bn), jehož prvky bi jsou f(ai) pro indexy splňující predikát a ai pro
indexy nesplňující predikát .

Například:
> (map-index-pred odd? sqr ’(2 3 4 5))
(2 9 4 25)
Prvky seznamu na lichých indexech (tedy prvky 3 a 5) jsou ve výsledném seznamu umocněny.
Protože indexy prvku 2 a 4 jsou 0 a 2 (nejsou tedy liché), jsou tyto prvky ve
výsledném seznamu stejné jako v původním seznamu.

Další příklad:
> (map-index-pred (lambda(i) (< i 2)) – ’(1 2 3 4 5)) (-1 -2 3 4 5) Prvky na indexech menší než 2 jsou ve výsledném seznamu nahrazeny jejich opacnou hodnotou, ostatní zůstavají stejné.

Napište iterativní proceduru divided-by-three?, která zjistí, jestli je součet čísel v daném
seznamu (obsahující pouze čísla 0, 1 a 2) dělitelný třemi. K implementaci použijte
tzv. konečný automat, jehož činnost je popsána orientovaným grafem znázorněným na
následujícím obrázku:

Vrcholy označené jako q0, q1, q2 představují stavy, ve kterých se automat muže nacházet,
hrany znázorňují do jakého stavu automat přejde zpracováním čísla určeného ohodnocením
dané hrany. Činnost automatu je podrobněji popsána na následujícím příkladu:

> (divided-by-three? ’(2 0 2 1 1))
#t

Stav automatu na začátku zpracování seznamu je vždy q0 (vrchol oznacený šipkou, která vede „odnikud“).
Automat muže zpracovávat seznam čísel např. zleva doprava, tzn. začne číslem 2.
Prejde tedy ze stavu q0 do stavu q2 (díky hraně, která směřuje z q0 do q2 a je
ohodnocena císlem 2). Poté zpracovává další císlo v seznamu, tzn. císlo 0. Hrana ohodnocená
nulou vycházející z vrcholu q2 vede opět do vrcholu q2, automat tedy zpracováním čísla 0 svůj stav nezmění.
Dál je přečteno číslo 2, automat přejde do stavu q1.
Zpracováním čísla 1 přejde z q1 zpět do q2 a na závěr přečtením čísla 1 přejde do stavu q0.
Pokud bude stav automatu po přečtení všech čísel q0 1, pak je součet všech čísel dělitelný třemi.

Pokud bude jeho stav na konci zpracování jiný než q0, pak soucet není delitelný tremi.

Další příklad:
> (divided-by-three? ’(0 1 2 2 2 2 1))
#f
Automat po přečtení všech čísel skončí ve stavu q1, tzn., že součet čísel 0+1+2+2+2+2+1
není dělitelný třemi.

Vytvořte proceduru singletons očekávající jako argument seznam a vracející seznam
singletonů (tzn. jednoprvkových seznamů) tvořených prvky vstupního seznamu.
Příklady použití:
> (singletons ’(2))
((2))
> (singletons ’(2 -1 3))
((2) (-1) (3))

Řešení