(Spojové) seznamy
Odpřednášena v úterý 6. 10.
Doteď jsme se seznámili pouze s jednou kolekcí: se stringy. Pokud ale chceme pracovat se sbírkami jiných typů než jsou písmena, použijeme seznamy.
Vytváření seznamů
Syntax pro vytvoření nového seznamu je
[list: /PRVEK 1/, /PRVEK 2/, ..., /PRVEK N/]
Například seznam čísel od jedné do tří by byl
[list: 1, 2, 3]
Prázdný seznam tvoříme buďto pomocí [list: ]
nebo empty
.
Když už nějaký seznam máme, můžeme k němu za čátek přidávat další prvky:
>>> link("a", [list: "h", "o", "j"]) [list: "a", "h", "o", "j"] >>> link(1, empty) [list: 1]
Z toho plyne, že výše zmíněný seznam od jedné do tří (a všechny ostatní seznamy) můžeme napsat dvěma způsoby:
check: [list: 1, 2, 3] is link(1, link(2, link(3, empty))) end
Typ seznamů
Nechť proměnná l
je
l = [list: 1, 2, 3]
poté její typ je slovy Seznam čísel, což se píše jako
l :: List<Number> = [list: 1, 2, 3]
Pokud nám je jedno, jakého typu prvky seznamu jsou (například u funkce length
, která dostane seznam čehokoli a jen ho změří), můžeme použít typ Any
:
fun length(list :: List<Any>) -> Number: ... end
Cases
Obecná syntax cases
je:
cases (List) /JMÉNO SEZNAMU/: | empty => /KDYŽ JE SEZNAM PRÁZDNÝ/ | link(/POJMENOVÁNÍ PRVNÍHO PRVKU/, /POJMENOVÁNÍ ZBYTKU/) => /KDYŽ SEZNAM = PRVNÍ PRVEK + ZBYTEK/ end
Nechť například list :: List<Number> = [list: 1, 2, 3]
, poté:
cases (List) list: | empty => # do something when list is empty | link(first, rest) => # do something with first, rest # first = 1, rest = [list: 2, 3] end
Někdy první a poslední prvek nepotřebujeme a cases
používáme jen proto, abychom zjistili, zda je seznam prázdný, či ne. V tom případě si můžeme rozkládání pomocí link(first, rest)
odpustit a místo toho psát:
cases (List) list: | empty => # do something when list is empty | else => # do something when list is NOT empty end
Funkce na seznamech
Kompletní seznam Pyretovských funkcí o seznamech naleznete v dokumentaci. Sekce "List methods" si prosím zatím nevšímejte.
Funkce na seznamech musíme nejprve naimportovat (podobně jako u obrázků), a to buďto pomocí include
nebo ještě lépe jako
import lists as L
Všechny funkce z knihovny lists
poté budou dostupné s prefixem L
. Například:
>>> import lists as L >>> L.drop(2, [list: "a", "h", "o", "j"]) [list: "o", "j"]
Tento prefix můžete nastavit libovolně, ale L
se používá nejčastěji.
Seznamy v paměti
Vzpoměňte si na obrázek, popř viz zde: Linked List vs Array.
Seznamy, nebo lépe spojové seznamy jsou v paměti uloženy jako jednotlivé prvky, které jsou pospojovány šipkami. Reálně to znamená, že u prvního prvku si pamatujeme nejen jeho hodnotu, ale také adresu druhého prvku, u toho si zase pamatujeme adresu třetího atd.
Výhody seznamů
- rychlé připojení prvního prvku: někam ho prostě uložíme a k němu dáme šipku na původní první prvek
- rychlé odpojení prvního prvku
Nevýhody seznamů
- pomalé indexování doprostřed: pokud chceme vědět, jakou hodnotu má pátý prvek, musíme nejdřív projít první čtyři)
- pomalé měnění uprostřed a na konci
- zabírají zbytečně moc paměti: u každého prvku musíme mít adresu následujícího prvku, a adresy zpravidla zaberou tolik místa, jako ten prvek samotný
Pole
Na rozdíl od seznamů jsou pole (array) uložena jako souvislý blok paměti.
Výhody polí
- rychlé indexování: pokud chceme pátý prvek, rovnou se podíváme na jeho pozici (která je rovna
začátek pole + 5
) - rychlé přepisování prvků uprostřed
Nevýhody polí
- prodloužování a zkracování trvají dlouho: musíme celé pole vzít a překopírovat ho na jiné místo v paměti a při tom tam daný prvek smazat nebo přidat
Úkol
Pokud si jste jistí v kramflecích, rekurzi a seznamy máte v malíku a už vás nebaví psát funkce jako drop
potřetí, jistě uvítáte následující možnost.
Počínaje úkolem 6c
(včetně) můžete k řešení používat libovolné funkce (ne metody) z knihovny lists
, pokud jste je už v minulosti alespoň jednou (pro seznamy) napsali. Pokud si naopak chcete rekurzi ještě procvičit, pište si své pomocné funkce i nadále sami.
Výjimkou z tohoto pravidla jsou případy, kdy by vám daná funkce z lists
ušetřila až moc práce — například pokud máte napsat funkci list-length
, není dovoleno k tomu použít funkci L.length
. Sázím na váš úsudek.
Nejčastěji se vám budou hodit následující funkce (viz dokumentace):
link
pro přidávání prvku na začátek seznamutake
adrop
member
append
nebo+
pro spojování dvou seznamůsplit-at