Obsah
1. Práce se seznamy v Logu
2. Vytváření seznamů – konstruktory
3. Seznamy konstruované pomocí hranatých závorek
4. Spojovací funkce sentence a list
5. Připojovací funkce fput a lput
6. Procedury pro výběr prvků ze seznamů – selektory
7. Predikáty
8. Odkazy na další informační zdroje
9. Obsah následující části tohoto seriálu
1. Logo a práce se seznamy
Seznam (list) patří mezi nejdůležitější datové struktury, se kterými se můžeme při programování setkat. Práce se seznamy je na jednu stranu jednoduchá (zejména pokud jsou podporovány použitým programovacím jazykem), na stranu druhou však umožňuje elegantní řešení mnohdy složitých algoritmů. V některých programovacích jazycích, jakými jsou Lisp, Logo, Tcl, Ruby či Python, seznam slouží jako základ pro tvorbu složitějších (lineárních i nelineárních) datových struktur, například zásobníků (stack), front (queue), stromů (tree), asociativních polí (hash array) či obecných grafů. V těchto programovacích jazycích je práce se seznamy podporovaná už na nejzákladnější úrovni – jedná se například o programové smyčky typu for-each, „seznamové“ funkce, mezi které patří apply, map či reduce apod. V dnešní i příští části tohoto seriálu si některé možnosti Loga při práci se seznamy popíšeme podrobněji, samozřejmě s využitím demonstračních příkladů.
2. Vytváření seznamů – konstruktory
Před vlastním zpracováním seznamů je nutné nějaký seznam vytvořit. K tomuto účelu slouží v Logu (ale samozřejmě i v dalších programovacích jazycích) takzvané konstruktory. Nejjednodušší formou konstruktoru je zápis hodnot, které potřebujeme mít uloženy v seznamu, do hranatých závorek. Tento způsob vytvoření seznamu je však možné použít pouze v případě, že se položky ukládané do seznamu nemají vyhodnocovat, tj. nejedná se o proměnné ani o volání procedur. Dále v Logu existuje několik spojovacích funkcí, pomocí kterých je možné seznam vytvořit spojením dvou či více jiných seznamů nebo připojením hodnot (či symbolů) k existujícímu seznamu. Mezi tyto spojovací funkce patří zejména sentence, list, fput a lput. Význam těchto funkcí bude popsán v následujících třech kapitolách.
3. Seznamy konstruované pomocí hranatých závorek
Pomocí hranatých závorek je možné vytvořit buď jednoduchý seznam, nebo seznam obsahující další vložené seznamy. Je možné zkonstruovat i prázdný seznam, který se zapisuje formou []. Tento způsob konstrukce seznamu se vyznačuje tím, že jednotlivé položky nejsou vyhodnocovány, tj. tímto způsobem není možné do seznamu vkládat hodnoty proměnných či návratové hodnoty funkcí. V podstatě totiž interpreter před každé slovo, které vkládá do seznamu, automaticky přidává znak ", čehož je možné využít při práci se symboly (symbolic computing), například při symbolické derivaci či použití seznamu místo množiny. Příklad několika seznamů:
[] ; prázdný seznam
[42] ; jednoprvkový seznam
[1 2 3 4 5] ; víceprvkový seznam
[A B C] ; seznam obsahující symboly
[WWW ROOT CZ] ; dtto
[A [B C] [D [E]]] ; seznam obsahující podseznamy Ukažme si, co se stane, pokud se pokusíme do seznamu vložit obsah proměnných. Nejprve vytvoříme dvě proměnné pojmenované foo a bar a potom pomocí hranatých závorek vytvoříme seznam, jehož položkami by měly být hodnoty těchto dvou proměnných. Na výpisu (poslední příkaz v programu) je však patrné, že interpreter Loga pochopil vyhodnocení proměnných jako zápis symbolu a ne jako příkaz:
; vytvoření první proměnné a přiřazení hodnoty
make "foo 42
; druhá proměnná má také přiřazenou hodnotu
make "bar 00100100
; zkontrolujeme, zda tomu tak opravdu je
show :foo
42
show :bar
100100
; vytvoření seznamu
make "seznam [:foo :bar]
; co se v seznamu skutečně nachází?
show :seznam
[:foo :bar]
což je odlišné od (možná očekávaného) výsledku [42 100100] 
4. Spojovací funkce sentence a list
Pro spojení dvou či více objektů do seznamu slouží funkce sentence a list. Opravdu se jedná o funkce (z matematického hlediska), protože obsah původních objektů se nemění, jelikož výsledek je vrácen ve formě nového seznamu. Jinými slovy to znamená, že tyto funkce nemají vedlejší efekty (to je ostatně jeden z předpokladů funkcionálního programování). Funkce sentence vytváří ze dvou či více objektů, které jsou jí předány jako parametry, seznam. Konstrukce seznamu je prováděna zřetězením těchto objektů, tj. v případě, že se spojují dva seznamy, vznikne z nich jeden (jednorozměrný) seznam. Tomuto chování se někdy říká zplošťování seznamu (flattening). Pokud je zapotřebí spojit pouze dva objekty, tj. předávají se dva parametry, je způsob volání funkce sentence následující:
sentence objekt1 objekt2 V případě potřeby spojení více objektů do seznamu se musí celý příkaz vložit do závorek, aby interpreter Loga poznal, ve kterém místě končí parametry a začíná další příkaz:
(sentence objekt1 objekt2 objekt3 ... objektN) Funkce list také slouží ke spojení dvou objektů do jednoho seznamu. Narozdíl od funkce sentence se však neprovádí zploštění, což znamená, že například spojením dvou seznamů vznikne seznam obsahující dva podseznamy. Pokud nejsou spojované objekty seznamy (přesněji řečeno nejsou typu seznam), je chování obou funkcí stejné. Rozdíl v chování funkcí sentence a list si ukážeme na několika příkladech:
; vytvoříme dva seznamy, z nichž každý obsahuje trojici symbolů
make "seznam1 [a b c]
make "seznam2 [d e f]
; podařilo se přiřazení?
show :seznam1
[a b c]
show :seznam2
[d e f]
; výše uvedené seznamy spojíme pomocí funkcí sentence a list
make "seznam3 sentence :seznam1 :seznam2
make "seznam4 list :seznam1 :seznam2
; jak vypadají výsledné seznamy po spojení?
show :seznam3
[a b c d e f]
show :seznam4
[[a b c] [d e f]] Můžeme vidět, že v prvním případě, tj. při použití funkce sentence, došlo ke zploštění výsledného seznamu, takže položky (prvky seznamu) uvedené v obou vstupních seznamech byly spojeny do seznamu jediného, který tedy obsahuje celkem šest symbolů. Ve druhém případě, tj. při spojení pomocí funkce list, ke zploštění nedošlo, takže výsledkem je dvouprvkový seznam, kde každý prvek je taktéž seznamem (tentokrát ovšem tříprvkovým). Podobným způsobem je možné s využitím vnořených seznamů vytvářet i složitější datové struktury, například binární stromy.
5. Připojovací funkce fput a lput
Kromě funkcí určených pro spojení objektů do společného seznamu obsahuje Logo i dvojici funkcí, které k již vytvořenému seznamu připojí další složku (dokonce je možné připojovat složku i k prázdným seznamům). Opět se jedná o funkce v matematickém významu, tj. obsah původního seznamu zůstane nezměněn a je vytvořen seznam nový. První z těchto funkcí se jmenuje fput a slouží k připojení objektu na začátek seznamu, tj. její jméno vzniklo ze sousloví first put (funkce tedy nemá nic společného se soubory). Prvním parametrem této funkce je objekt, který se má připojit k nějakému seznamu. Tento seznam je předán ve druhém parametru. Druhá připojovací funkce se jmenuje lput a slouží k připojení objektu ke konci seznamu (last put). Následuje ukázka použití obou těchto funkcí:
; vytvoříme proměnnou x obsahující tříprvkový seznam
make "x [2 3 4]
; do nové proměnné y vložíme původní seznam s připojeným prvkem na začátku
make "y fput 1 :x
; původní seznam zůstal nedotčen
show :x
[2 3 4]
; nový seznam má nyní čtyři složky
show :y
[1 2 3 4]
; seznam uložený do proměnné z vznikl ze seznamu x s připojeným prvkem na konci
make "z lput 5 :y
; můžeme se o tom jednoduše přesvědčit
show :z
[1 2 3 4 5]
; ------------------------------
; a nyní něco složitějšího
; nejprve vytvoříme potřebné seznamy (viz předchozí příklad)
make "seznam1 [a b c]
make "seznam2 [d e f]
make "seznam4 list :seznam1 :seznam2
; vložení symbolu na začátek seznamu4
show fput "x :seznam4
[x [a b c] [d e f]]
; místo pouhého symbolu je možné vložit i celý seznam
show fput :z :seznam4
[[1 2 3 4 5] [a b c] [d e f]]
show lput :z :seznam4
[[a b c] [d e f] [1 2 3 4 5]] Rozdíl mezi spojovacími a připojovacími funkcemi ozřejmí následující příklad, ve kterém jsou pro všechny čtyři výše popsané funkce použity stejné parametry:
; spojení objektů se zploštěním seznamů
show sentence [u v w] [x y z]
[u v w x y z]
; spojení objektů bez zploštění seznamů
show list [u v w] [x y z]
[[u v w] [x y z]]
; připojení objektu (i seznamu) na začátek seznamu (bez zploštění)
show fput [u v w] [x y z]
[[u v w] x y z]
; připojení objektu (i seznamu) na konec seznamu (bez zploštění)
show lput [u v w] [x y z]
[x y z [u v w]] 
6. Procedury pro výběr prvků ze seznamů – selektory
V předchozích třech kapitolách jsme si uvedli některé programové konstrukce určené pro vytváření seznamů ze samostatných objektů či jiných seznamů. Při praktické práci se seznamy však samozřejmě potřebujeme přistupovat k jejich položkám. V Logu je pro tento účel vyhrazeno pět funkcí, jejichž popis naleznete v následující tabulce. Za zmínku stojí fakt, že ideový předchůdce Loga, tj. programovací jazyk Lisp, obsahoval původně pouze dvě funkce pro přístup k prvkům seznamu – jedná se o funkce car a cdr, které jsou v Logu plně nahrazeny funkcemi first a butfirst. Pomocí funkce item je možné se seznamem pracovat jako s polem nebo vektorem, což sice mohou někteří skalní lispaři odmítat (na stejnou činnost lze naprogramovat vlastní rekurzivní funkci, což si ukážeme dále), jedná se však o užitečnou a často používanou činnost, proto je dobře, že je v Logu tato funkce přítomná.
| Procedura | Popis |
|---|---|
| first L | vrací první položku seznamu L |
| last L | vrací poslední položku seznamu L |
| butfirst L | vrací kopii seznamu L, ovšem bez první položky |
| butlast L | vrací kopii seznamu L, ovšem bez poslední položky |
| item N L | vrací N-tou položku seznamu L |
Pokud by funkce item v některém interpreteru Loga neexistovala, je možné si ji jednoduše doprogramovat pomocí rekurzivní funkce. Na níže uvedeném příkladu je ukázáno i použití funkcí first a butfirst:
to item :N :L
if :N = 1 [output first :L]
output item (:N - 1) (butfirst :L)
end
; test funkčnosti
show i 1 [a b c d]
a
show i 3 [a b c d]
c 
7. Predikáty
Využití seznamů je sice v mnoha programech velmi účinné, postavilo nás však před jeden problém. Pokud máme nějakou proměnnou, je v některých případech nutné zjistit typ hodnoty uložené do této proměnné. Z předchozích částí tohoto seriálu víme, že proměnná typ přiřazen nemá, ovšem její hodnota samozřejmě ano – je to ostatně vlastnost většiny dynamicky typovaných programovacích jazyků (a i takzvaných striktně typovaných objektově orientovaných jazyků, i když to jejich zastánci popírají :-). V Logu se pro zjištění typu nějaké hodnoty používají takzvané predikáty (na konci jejich jména je vždycky znak „p“, některé implementace používají i znak „?“). Jedná se o zabudované funkce, které dokáží zjistit typ hodnoty, která se jim předá v parametru. Návratovou hodnotou predikátů je pravdivostní hodnota true nebo false – ta se typicky použije v příkazu if nebo ifelse:
| Predikát | Význam |
|---|---|
| numberp | test, zda je předaný objekt číslem |
| wordp | test, zda je předaný objekt slovem |
| listp | test, zda je předaný objekt seznamem |
| emptyp | test, zda je předaný objekt prázdným seznamem |
| arrayp | test, zda je předaný objekt polem |
Kromě toho existují ještě další typy predikátů, které se typicky používají na test shodnosti objektů či na test, zda je nějaký objekt položkou předaného seznamu (lze použít například při implementaci množin):
| Predikát | Význam |
|---|---|
| equalp | test na shodnost dvou objektů |
| notequalp | test na neshodnost dvou objektů |
| memberp | test, zda je objekt položkou seznamu |
8. Odkazy na další informační zdroje
- James F. Korsh and Leonard J. Garrett:
Data Structures, Algorithms and Program Style Using C - Wayne Amsbury:
Data Structures: From Arrays to Priority Queues - Ellis Horowitz and Sartaj Sahni:
Fundamentals of Data Structures,
Dr. Dobb's Journal - Bruno R. Preiss:
Data Structures and Algorithms with Object-Oriented Design Patterns in Java,
Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Canada - Wikipedia (EN):
List (Computing)
http://en.wikipedia.org/wiki/List_(computing) - Wikipedia (EN):
Functional programming
http://en.wikipedia.org/wiki/Functional_language
9. Obsah následující části tohoto seriálu
V dalším pokračování seriálu o programovacím jazyce Logo si ukážeme použití funkcí, které provádí manipulaci s celými seznamy. Jedná se například o funkce apply, map či reduce, které jsou použity 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ů nad seznamy, tj. programovou smyčku typu for-each a některé její varianty.
Poznámka: většina výše uvedených ukázkových obrázků byla vytvořena následující procedurou:
to domek :strana :uhel
ifelse :strana>8 [
; základna
forward :strana
; úhlopříčka
left 90+45
forward :strana*sqrt 2
; stěna
left 90+45
forward :strana
; úhlopříčka
left 90+45
forward :strana*sqrt 2
; úsečka pod střechou
left 90+45
forward :strana
; první část střechy
right 90
right 90-:uhel
domek :strana*cos :uhel :uhel
; druhá část střechy
right 90
domek :strana*sin :uhel :uhel
; zbývající stěna
right :uhel
forward :strana
left 90
] [
setpencolor 0
repeat 36 [left 10 forward :strana/5]
forward :strana
setpencolor 1
]
end Popř. její modifikovanou variantou:
to domek :strana :uhel
ifelse :strana>4 [
; základna
forward :strana
; úhlopříčka
left 90+45
pu
forward :strana*sqrt 2
pd
; stěna
left 90+45
forward :strana
; úhlopříčka
pu
left 90+45
forward :strana*sqrt 2
pd
; úsečka pod střechou
left 90+45
forward :strana
; první část střechy
right 90
right 90-:uhel
; původní příkaz: domek :strana/sqrt 2 :uhel
domek :strana*cos :uhel :uhel
; druhá část střechy
right 90
; původní příkaz: domek :strana/sqrt 2 :uhel
domek :strana*sin :uhel :uhel
; zbývající stěna
setpencolor 1
pd
repeat 36 [left 10 forward :strana/12]
pu
setpencolor 0
right :uhel
forward :strana
left 90
] [
setpencolor 4
pd
repeat 36 [left 10 forward :strana/4]
setpencolor 0
pu
forward :strana
]
end 
