Kapitola 8: Struktury dat – Seznamy a Inventáře

V minulé kapitole jsme se naučili rekurzi. Možná jste si říkali: "K čemu je to dobré v praxi?" Tady je odpověď. Rekurze je naprosto nezbytná pro práci se seznamy. Představte si hrdinu v RPG hře. Má batoh (inventář), ve kterém může mít meč, lektvar, mapu, nebo taky nic. Nevíme předem, kolik věcí tam bude. Pro uchování takové řady věcí používáme seznamy.

8.1 Vlaková analogie – Hlava a Ocas

Seznam v Prologu se píše do hranatých závorek: [jablko, hruska, banan]. Abychom se seznamem mohli pracovat, musíme ho umět rozebrat. Prolog vidí seznam jako vlak, který má dvě části:

HLAVA (HEAD) První prvek seznamu. Lokomotiva. Je to ta jedna konkrétní věc, kterou právě držíme v ruce.
OCAS (TAIL) Zbytek seznamu za hlavou. Všechny ostatní vagóny. Pozor: Ocas je VŽDYCKY seznam! I když je v něm jen jedna věc, nebo nic.
Vlak se seznamem
Obrázek 8.1: Seznam jako vlak. Lokomotiva je Hlava, zbytek vagónů je Ocas.

Pro rozdělení vlaku na lokomotivu a zbytek používáme "svislítko" | (pipe). Zápis [H | T] znamená: "Vezmi první prvek a dej ho do H, zbytek dej do T."

?- [H | T] = [jablko, hruska, banan].
H = jablko,
T = [hruska, banan].

?- [H | T] = [jablko].
H = jablko,
T = [].  % Prázdný seznam!

⚠️ Častá chyba: Ocas seznamu [a] není nic, ale prázdný seznam []. Je to jako prázdný vlak, který už nemá žádné vagóny.

8.2 Práce se seznamy – Rekurze v praxi

Jak zpracovat celý vlak? Jednoduše:

  1. Uděláme něco s lokomotivou (Hlavou).
  2. Zbytek vlaku (Ocas) pošleme zpátky do stejného pravidla (Rekurze).
  3. Opakujeme, dokud nenarazíme na prázdný vlak (Základní případ).

Příklad 1: Je prvek v seznamu? (Member)

Hledáme, jestli je v batohu X.

% 1. Základní případ: Našli jsme to! X je hned na začátku (v Hlavě).
obsahuje(X, [X | _]).

% 2. Rekurzivní krok: X na začátku není. Musíme se podívat do zbytku (Ocasu).
obsahuje(X, [_ | Ocas]) :-
    obsahuje(X, Ocas).

Jak to funguje: ?- obsahuje(banan, [jablko, hruska, banan]).

  1. Je banan to samé co jablko? Ne. (Pravidlo 1 selže).
  2. Zkusíme pravidlo 2: Zahodíme jablko a hledáme banan v [hruska, banan].
  3. Je banan to samé co hruska? Ne.
  4. Zkusíme pravidlo 2: Zahodíme hruska a hledáme banan v [banan].
  5. Je banan to samé co banan? ANO! (Pravidlo 1 uspěje).
  6. Odpověď: true.

Příklad 2: Délka seznamu

Jak dlouhý je vlak?

delka([], 0).                 % Prázdný seznam má délku 0.
delka([_ | Ocas], N) :-       % Délka je 1 + délka ocasu.
    delka(Ocas, N1),          % Zjisti délku zbytku
    N is N1 + 1.              % Přičti 1

Řešené příklady: Počítáme poklad

Příklad 8.1: Součet seznamu
Máme seznam mincí [1, 2, 5, 10]. Kolik máme celkem peněz?

soucet([], 0).                % Prázdný měšec má hodnotu 0.
soucet([Hlava | Ocas], Celkem) :-
    soucet(Ocas, SoucetZbytku), % Nejdřív sečti zbytek
    Celkem is Hlava + SoucetZbytku. % Pak přičti aktuální minci

Klíčový koncept: Zpracování seznamu

Většina predikátů pro práci se seznamy má stejnou strukturu: 1. Základní případ pro prázdný seznam []. 2. Rekurzivní pravidlo pro seznam s hlavou a ocasem [H|T], které zpracuje hlavu a zavolá se znovu na ocas.

Otázky k zamyšlení

  1. Co by se stalo, kdybychom v predikátu obsahuje prohodili pořadí pravidel? Fungovalo by to stále?
  2. Jaký je ocas seznamu [a]? A jaký je ocas seznamu []? (Chyták: prázdný seznam nemá ocas, pokus o jeho získání selže).
  3. Jak byste pomocí unifikace získali třetí prvek seznamu? (Nápověda: [_, _, X | _]).

🧪 Laboratoř: Práce s inventářem