Hlavní navigace

Práce se seznamy v Logu

Pavel Tišnovský

V dnešním článku o jazyce Logo se zaměříme na práci se seznamy. Logo, podobně jako další programovací jazyky vysoké úrovně, obsahuje už v základní knihovně mnoho procedur, pomocí kterých je možné jednoduše a elegantně se seznamy pracovat. Jedná se například o "funkcionální" iterátory typu map, apply či foreach.

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ů.

logo1301

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.

logo1302

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] 

logo1303

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.

logo1304

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]] 

logo1305

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 

logo1306

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

logo1307

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

  1. James F. Korsh and Leonard J. Garrett:
    Data Structures, Algorithms and Program Style Using C
  2. Wayne Amsbury:
    Data Structures: From Arrays to Priority Queues
  3. Ellis Horowitz and Sartaj Sahni:
    Fundamentals of Data Structures,
    Dr. Dobb's Journal
  4. 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
  5. Wikipedia (EN):
    List (Computing)
    http://en.wiki­pedia.org/wiki/Lis­t_(computing)
  6. Wikipedia (EN):
    Functional programming
    http://en.wiki­pedia.org/wiki/Fun­ctional_langu­age

logo1308

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 
Našli jste v článku chybu?

25. 9. 2007 9:00

neni problem - pavel tecka tisnovsky zavinac cdtel tecka cz

22. 9. 2007 11:40

patlálek (neregistrovaný)
Dobrý den! Pane Tišnovský, potřeboval byh zvědět něco k vytvoření Barnsleyovy fraktální množiny J1. Kam to můžu poslat? Myslím jako mail na vás, nebo tak, je v tom i obrázek. Děkuji.
Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

DigiZone.cz: Test Philips 24PFS5231 s Bluetooth repro

Test Philips 24PFS5231 s Bluetooth repro

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Vitalia.cz: Pamlsková vyhláška bude platit jen na základkách

Pamlsková vyhláška bude platit jen na základkách

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Vitalia.cz: 9 největších mýtů o mase

9 největších mýtů o mase

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Vitalia.cz: Když přijdete o oko, přijdete na rok o řidičák

Když přijdete o oko, přijdete na rok o řidičák

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Vitalia.cz: I církev dnes vyrábí potraviny

I církev dnes vyrábí potraviny