Procedury APPLY, MAP, REDUCE a FOREACH

Obsah

1. Použití seznamů pro předávání parametrů procedurám
2. Demonstrační příklad: seznam jako náhrada několika parametrů předávaných proceduře
3. Procedury foreach, map, apply a reduce – „funkcionální“ iterátory
4. Iterace nad seznamem – procedura foreach
5. Zpracování položek v seznamu – procedura map
6. Zpracování položek v seznamu – procedura apply
7. Zpracování položek v seznamu – procedura reduce
8. Odkazy na další informační zdroje
9. Obsah následující části tohoto seriálu

1. Použití seznamů pro předávání parametrů procedurám

V předchozí části tohoto seriálu jsme si ukázali, jakým způsobem lze vytvářet seznamy pomocí konstruktorů, spojovacích funkcí sentence a list a také připojovacích funkcí fput a lput. Kromě popisu těchto funkcí jsme si vysvětlili princip selektorů, tj. funkcí určených pro výběr hodnot ze seznamů. Konkrétně se jednalo o funkce first, last, butfirst, butlast a item. Dnes si ukážeme použití funkcí, které provádí manipulaci s celými seznamy.

Budou popsány především funkce apply, map či reduce, jež jsou implementovány i v dalších vysokoúrovňových programovacích jazycích. Kromě toho si také ukážeme způsob tvorby iteračních cyklů prováděných nad seznamy, tj. programovou smyčku typu for-each a některé její varianty. V navazující části si také řekneme, jak lze pomocí seznamů simulovat další lineární datové struktury, například zásobníky či fronty.

Obrázek 1: Tvar vytvořený pomocí prvního demonstračního příkladu

Seznamy je možné v Logu využít na mnoha místech. Typicky se jedná o ty programátorské postupy, ve kterých by se v jiných programovacích jazycích použily struktury, vektory, pole či matice (a jak uvidíme v další části tohoto seriálu, tak i řetězce jsou v Logu poněkud netypicky ukládány do seznamů). Pokud například potřebujeme některé proceduře (funkci) předat větší množství parametrů, které jsou buď stejného typu a/nebo předem neznáme jejich počet, nabízí se právě použití seznamů.

I při potřebě vrácení většího množství hodnot z nějaké funkce lze použít seznamy, protože v Logu, podobně jako mnoha dalších programovacích jazycích, je počet návratových hodnot omezen na maximálně jednu hodnotu. Pokud však funkce vrací seznam, může být v tomto seznamu (který je jedinou návratovou hodnotou funkce) uložené libovolné množství údajů, včetně podseznamů. Na tomto místě můžeme vidět velkou podobnost Loga s LISPem a v širších souvislostech s prakticky všemi objektově orientovanými jazyky. Nejprve si řekněme, jakým způsobem je možné předat nějaké proceduře či funkci seznam, posléze si vše vysvětlíme na demonstračních příkladech.

Předávání seznamů je velmi jednoduché, protože v Logu není nutné specifikovat datový typ předávaného parametru. To znamená, že postačuje například zápis to obrat :seznam. Samotné Logo nás nijak neomezuje v tom, jaký datový typ této proceduře ve skutečnosti předáme. To může v mnoha programech představovat problém, protože například budeme požadovat, aby se této funkci vždy předal seznam a ne například celé číslo, reálné číslo nebo symbol. V Logu však naštěstí existují minule vysvětlené predikáty, pomocí nichž lze za běhu programu zjistit, jakého typu je předávaný parametr.

V našem případě by bylo vhodné použít predikát listp, který vrací pravdivostní hodnotu true pouze v případě, že jemu předaná hodnota je typu seznam. Dalším predikátem, který se použije ve druhém kroku, je emptyp, který vrací true tehdy, jestliže jde o prázdný seznam. Počáteční příkazy procedury obrat by mohly vypadat následovně (těmto úvodním příkazů se také někdy říká aserce):

to obrat :seznam
    ; test, zda byl proceduře skutečně
    ; předaný seznam a ne jiný datový typ
    if not listp :seznam [
        show "Chyba1
        stop
    ]
    ; sice jde o seznam, ale co když
    ; je prázdný?
    if emptyp :seznam [
        show "Chyba2
        stop
    ]
    ; všechno je v pořádku, procedura
    ; může pokračovat
    show "ok
end

; zkusíme, jak bude program reagovat
; na různé vstupy
obrat 42

obrat []
obrat [42]
obrat [a b c] 

Obrázek 2: Další tvar vytvořený pomocí prvního demonstračního příkladu

2. Demonstrační příklad: seznam jako náhrada několika parametrů předávaných proceduře

V dnešním prvním demonstračním příkladu je ukázáno, jakým způsobem lze do nějaké funkce přenášet více hodnot pomocí jednoho parametru. Vytvořená procedura qix (pojmenovaná po jedné hře z časů osmibitových počítačů) vykresluje obrazce složené z úseček, jejichž koncové body se pohybují po drahách, která mají tvar takzvaných Lissajousových obrazců – ty jsou mimochodem používané například při zkoumání signálů pomocí osciloskopů.

Proceduře qix je zapotřebí předat počet opakování smyčky a tím i počet vytvořených úseček, „amplitudu“ Lissajousových obrazců, tj. maximální vzdálenost vygenerovaných bodů od počátku souřadné soustavy a nakonec také čtyři reálné hodnoty, které představují násobek základní frekvence a pomocí nichž se určuje vlastní tvar obrazce. Právě tyto čtyři reálné hodnoty jsou předávané ve formě seznamu v parametru nazvaném freq. Pro jednoduchost není v proceduře qix implementována aserce, tj. kontrola, zda jsou skutečně předány validní parametry.

Zajímavé je také samotné volání procedury qix. Testovací procedura nazvaná jednoduše test_qix totiž obsahuje seznam, ve kterém jsou uloženy další (vnořené) seznamy obsahující výše zmiňované čtyři reálné hodnoty. Vzhledem k tomu, že jsou všechny hodnoty uloženy v jednom seznamu, je snadné pomocí programové smyčky repeat zajistit procházení celého seznamu a vykreslení čtyř testovacích obrazců. Pro větší přehlednost je seznam se čtyřmi hodnotami nejdříve uložen do pomocné proměnné params, ve skutečnosti se však můžeme bez této proměnné obejít. V dalších kapitolách si ukážeme, že použití programové smyčky repeat není v tomto případě nejvhodnější, protože Logo nám nabízí i iterační smyčky určené přímo pro zpracování seznamů.

; Vytvoření obrazce složeného z úseček
; význam jednotlivých parametrů:
; opak - počet opakování
; amp  - "amplituda", maximální vzdálenost od počátku
; freq - seznam se čtyřmi reálnými hodnotami (násobky frekvence)

to qix :opak :amp :freq
    repeat :opak [
        ; výpočet souřadnic prvního vrcholu úsečky
        make "x1 :amp*cos repcount* item 1 :freq
        make "y1 :amp*sin repcount* item 2 :freq
        ; výpočet souřadnic druhého vrcholu úsečky
        make "x2 :amp*sin repcount* item 3 :freq
        make "y2 :amp*cos repcount* item 4 :freq
        ; přesun na počáteční pozici (bez kreslení)
        penup
        setpos list :x1 :y1
        ; vykreslení úsečky z počáteční do koncové pozice
        pendown
        setpos list :x2 :y2
    ]
end

; test funkčnosti procedury qix

to test_qix
    make "testdata [
        [4.0 3.0 2.0 7.0]
        [1.0 0.5 0.5 2.0]
        [3.0 3.0 2.0 2.0]
        [4.0 3.0 2.0 2.0]
    ]
    window
    hideturtle
    ; projdeme celý seznam a pro každou jeho položku
    ; (čtveřici hodnot) vykreslíme obrazec
    repeat 4 [
        ; do proměnné params je vložen jeden z podseznamů
        make "params item repcount :testdata
        clearscreen
        qix 400 250 :params
        ; pro některé interpretery je nutné provést úpravu
        ; následujícího řádku
        readline
    ]
end

; spuštění příkladu
test_qix 

Obrázek 3: Třetí tvar vytvořený pomocí prvního demonstračního příkladu

3. Procedury foreach, map, apply a reduce – „funkcionální“ iterátory

Pro zpracování celých seznamů není zapotřebí vytvářet ani iterační smyčky ani rekurzivní procedury. Logo totiž, podobně jako další programovací jazyky založené na funkcionálním základě, obsahuje takzvané funkcionální iterátory, zkráceně pouze iterátory. Brian Harvey (viz literatura) používá také termín Template-based Iteration. Mezi funkcionální iterátory patří především procedury foreach, map, apply a reduce, jejichž jména mohou být známá například programátorům pracujícím v Lispu, Scheme nebo Pythonu. V následujících kapitolách budou tyto procedury podrobněji popsány. Z matematického hlediska lze všechny jmenované procedury považovat za funkce, protože nemění hodnotu svých parametrů a veškerou svoji činnost vracejí ve formě výstupu bez vedlejších účinků na předávaná data. To znamená, že objekty (typicky seznamy), které se těmto funkcím předávají, zůstávají nezměněné.

Obrázek 4: Čtvrtý tvar vytvořený pomocí prvního demonstračního příkladu

4. Iterace nad seznamem – procedura foreach

Pravděpodobně nejpoužívanější procedurou určenou pro zpracování celého seznamu, je procedura foreach. Její použití je celkem jednoduché: pro každou položku seznamu (předaného jako první parametr této procedury) je zavolán zvolený příkaz či příkazy, které jsou předány jako druhý parametr. Syntaxe zápisu procedury foreach je foreach seznam příkazy, popř. existuje i rozšířená forma (foreach seznam1 seznam2 … příkazy). Příkazy jsou, jak je ostatně v Logu zvykem, také uloženy v seznamu. Jak se však v těchto příkazech použije aktuální hodnota vybraná ze seznamu?

K tomuto účelu slouží znak ? (otazník), za který jsou postupně dosazovány všechny hodnoty obsažené v předávaném seznamu. Některé implementace ještě používají symbol ?rest, který představuje seznam obsahující všechny položky ZA právě vybranou položkou (jedná se tedy o prozatím nezpracované položky). Dalším speciálním symbolem je #, do kterého jsou dosazovány pozice vybraných položek z předávaného seznamu. Vidíme, že v Logu se můžeme obejít bez pomocných proměnných, na druhou stranu však může být vnořené použití procedury foreach nepřehledné (to však platí i pro jiné programovací jazyky, obecně je vhodné vnořené cykly nahradit voláním funkcí). Ukažme si jednoduché použití procedury foreach spolu se všemi popisovanými zástupnými symboly:

foreach [a b c d] [
    print (sentence "index # "hodnota ? "zbytek ?rest)
]

; na výstup se vypíše
index 1 hodnota a zbytek b c d
index 2 hodnota b zbytek c d
index 3 hodnota c zbytek d
index 4 hodnota d zbytek 

Obrázek 5: Pátý tvar vytvořený pomocí prvního demonstračního příkladu

První demonstrační příklad uvedený ve druhé kapitole je možné upravit tak, aby místo smyčky typu repeat použil smyčku typu foreach. Upravená procedura test_qix bude mít tvar uvedený v následujícím výpisu (zbytek programu zůstává nezměněn). Všimněte si použití zástupného symbolu ? uvnitř seznamu příkazů předávaného smyčce foreach:

; test funkčnosti procedury qix

to test_qix
    make "testdata [
        [4.0 3.0 2.0 7.0]
        [1.0 0.5 0.5 2.0]
        [3.0 3.0 2.0 2.0]
        [4.0 3.0 2.0 2.0]
    ]
    window
    hideturtle
    ; projdeme celý seznam a pro každou jeho položku
    ; (čtveřici hodnot) vykreslíme obrazec
    foreach :testdata [
        clearscreen
        qix 400 250 ?
        ; pro některé interpretery je nutné provést úpravu
        ; následujícího řádku
        readline
    ]
end 

5. Zpracování položek v seznamu – procedura map

Další tři procedury, tj. map, apply a reduce také umožňují práci s celým seznamem. Procedura map je volaná buď se dvěma parametry nebo s libovolným větším množstvím parametrů. V prvním případě je syntaxe volání map šablona seznam, ve druhém případě může být použito větší množství předávaných seznamů: (map šablona seznam1 seznam2). Po zavolání procedury map je pro každou položku seznamu zavolána předaná šablona, což je typicky nějaká matematická nebo logická funkce (šablonu tak, jak ho chápe Logo, je nutné odlišovat například od šablon podporovaných jazykem C++).

Pokud je použit druhý způsob volání s více seznamy, je šablona aplikována vždy na všechny korespondující položky seznamů (tj. na všechny první položky, potom na všechny druhé položky atd.). Tyto seznamy by z tohoto důvodu měly mít stejnou délku, jinak by došlo k oříznutí delších seznamů tak, aby jejich délka odpovídala nejkratšímu předávanému seznamu. Výsledkem běhu procedury map je nový seznam – to je největší rozdíl mezi map a foreach.

Následují dva jednoduché příklady použití procedury map. V prvním případě se provede součet odpovídajících položek předávaných seznamů (nelze zde použít operátor +, ale pouze funkci), ve druhém případě se vždy dvě odpovídající položky ze vstupních seznamů sjednotí do nového seznamu a vznikne tak seznam složený ze dvojic položek:

show (map "sum [1 2 3] [4 5 6])
[5 7 9]

show (map "list [a b c] [d e f])
[[a d] [b e] [c f]] 

Použití pouze jednoho seznamu na vstupu je ještě jednodušší:

show map "log10 [1 10 100 42 6502]
[0 1 2 1.6232492903979 3.81304696516011] 

Obrázek 6: Šestý tvar vytvořený pomocí prvního demonstračního příkladu

6. Zpracování položek v seznamu – procedura apply

Procedura apply provádí, jak už ostatně její název napovídá, aplikaci nějaké šablony (tj. funkce) na všechny prvky předávaného seznamu. Je povolen pouze jeden způsob zápisu apply šablona seznam, protože v tomto případě nemá smysl předávat větší množství seznamů – místo toho je možné zřetězit až výsledky několikerého volání procedury apply, například pomocí minule popsaných spojovacích funkcí list či sentence. Šablona (což je typicky opět nějaká matematická či logická funkce) musí být uzpůsobena tak, aby akceptovala takové množství parametrů, kolik jich daný seznam obsahuje. Učebnicový případ použití procedury apply vypadá následovně:

show apply "sum [1 2 3]
6

; primitivní metoda výpočtu faktoriálu šesti
show apply "product [1 2 3 4 5 6]
720 

Obrázek 7: Sedmý tvar vytvořený pomocí prvního demonstračního příkladu

7. Zpracování položek v seznamu – procedura reduce

Pomocí procedury reduce je umožněno zpracovávání seznamů i pomocí šablon (procedur, funkcí), které samy o sobě neumí pracovat se seznamy, ale pouze s dvojicí objektů, typicky číselných hodnot. Procedura reduce postupně redukuje seznam, který jí byl předán ve druhém parametru. Redukce probíhá tak, že se z tohoto seznamu vyberou poslední dvě položky, aplikuje se na ně šablona (předaná v prvním parametru) a výsledek je použit při zpracování dalších položek vstupního seznamu – další volání šablony je provedeno se třetí položkou od konce seznamu a výsledkem předchozí operace, posléze se čtvrtou položkou od konce seznamu a výsledkem operace provedené nad třetí položkou atd.

Seznam je tedy zkracován od konce (to vychází z rekurzivní definice procedury reduce). Zpracování končí v případě, že je vstupní seznam tímto způsobem vyprázdněn. Procedura reduce v tomto případě vrátí hodnotu získanou z posledního volání šablony. Opět si ukážeme typické případy použití procedury reduce:

to max :a :b
output ifelse :a > :b [:a] [:b]
end

print reduce "max [2 3 8 7 9 0]
9

; v některých případech je výsledek reduce obdobný apply
show reduce "product [1 2 3 4 5 6]
720

; ovšem funkce power akceptuje pouze dva parametry
; je tedy vypočten výraz 234
show reduce "power [2 3 4]
2.41785163922926e+24 

8. Odkazy na další informační zdroje

1. Friendly M.:
   Advanced LOGO a Language for learning
   New Jersey, Hillsdale, 1988
2. Goldenberg E. Paul, a Wallace Feurzeig:
   Exploring Language with Logo
   MIT Press
3. Harvey Brian:
   Berkeley Logo 5.5
   Regents of the University of California, August, 8 2005
4. Muller Jim:
   The Great Logo Adventure
   Young People's Logo Association:
5. Tržilová Dana:
   LOGO a matematika
   JIHOČESKÁ UNIVERZITA V ČESKÝCH BUDĚJOVICÍCH, PEDAGOGICKÁ FAKULTA, 1993
   učební text pro studenty výběrového semináře
6. Young People's Logo Association:
   The Logo Library
7. Young People's Logo Association:
   Learning Logo On and Off the Computer

9. Obsah následující části tohoto seriálu

V následujícím pokračování seriálu o programovacím jazyce Logo dokončíme kapitolu věnovanou seznamům a následně si ukážeme práci s řetězci, která je v Logu poněkud odlišná, než v ostatních programovacích jazycích. Také si popíšeme některé procedury, jež je možné použít pro načítání řetězců i jiných dat ze vstupu či naopak zápis řetězců na konzoli či do souboru.