(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 seznamu
  • take a drop
  • member
  • append nebo + pro spojování dvou seznamů
  • split-at