Funkcionální programování - Příklad o hanoiských věžích

V této části seriálu si ukážeme některé další funkce pracující se seznamy a napíšeme si první spustitelný funkcionální „miniprogram“ se vstupy a výstupy.

(++)       ::  [a] -> [a] -> [a]
[]    ++ t  =  t
(x:s) ++ t  =  x : (s ++ t)

Například [1,2,3]++[4,5] bude [1,2,3,4,5], nebo "Ája"++" a "++"Fík" bude spojený řetězec "Ája a Fík".

Pozor na rozdílnost operátorů (:) a (++). Operátor (:) připojuje jeden prvek na začátek seznamu a je to datový konstruktor – to znamená, že nemá žádnou definici, ale sám vytváří seznamy: třeba 2:1:[] je nezjednodušitelný výraz (s alternativní syntaxí [2,1]). Naproti tomu operátor (++) je běžná funkce, která má výše uvedenou definici. Od výrazu [3]++[1,2]++[1] je nutno k ekvivalentnímu výrazu [3,1,2,1] dospět výpočtem.

V Haskellu je celá řada užitečných knihovních funkcí pro práci se seznamy. S některými jsme se už seznámili, na jiné ještě narazíme. Připomeňme, že funkce filter vybírá ze seznamu ty prvky, které vyhovují zadanému predikátu. Například filter odd [1,2,3,4,5] vrátí [1,3,5] (odd je predikát "lichosti"), anebo filter (<5) [1,2,3,4,5] vrátí seznam [1,2,3,4] (predikát zapisovaný (<5) je pravdivý na každém argumentu, který je menší než pět).

Zkusme odhadnout, co dělá následující funkce qs:

qs      ::  Ord a => [a] -> [a]
qs []    = []
qs (p:s) = qs (filter (< p) s) ++ [p] ++ qs (filter (>= p) s)

Jde o známý řadicí algoritmus, který lze v Haskellu zapsat, i s nepovinnou typovou anotací, na tři řádky.

Hanoiské věže

Nyní si vytvoříme první netriviální prográmek v Haskellu. Úloha o takzvaných Hanoiských věžích je známá hříčka, ale pro jistotu si stručně připomeňme její zadání.

V Hanoi jsou tři stejné „věže“ A, B, C. Věže B, C jsou na počátku prázdné, ve věži A je uloženo na sobě n zlatých disků nestejného průměru tak, že vždy leží menší na větším. Úkolem je přestěhovat tyto disky po jednom do věže B. Věž C lze použít pro dočasné odkládání disků. Tedy věž A je zdrojová, B je cílová a C je pomocná. Podmínkou je, že disky se smějí odebírat pouze shora a přidávat zase jen nahoru, v žádné věži nesmí nikdy ležet větší disk na menším a nikdy nesmí být venku více než jeden disk (ten, který se zrovna stěhuje).

Například pro n = 2 má plán stěhování tři kroky:

Pro n = 3 se plán stěhování skládá ze sedmi kroků:

My chceme řešit problém pro obecný počet n. Definujeme funkci hanoi, která pro daný argument n vrátí plán stěhování ve tvaru seznamu řetězců. Protože při řešení podproblémů si budou věže měnit role (pomocná se stane dočasně cílovou, zdrojová pomocnou atd.), použijeme „podrobnější“ funkci

ha :: Int -> Char -> Char -> Char -> [String]

jejímiž argumenty budou kromě počtu disků n také věže: ha n z c p bude plán stěhování n disků z věže z (zdrojové) do věže c (cílové) s použitím věže p (pomocné). Potom lze celý problém řešit užitím této pomocné funkce ha:

hanoi n = ha n 'A' 'B' 'C'

Je-li n = 0, pak je řešení triviální a výsledkem je prázdný seznam přesunů – nic není třeba stěhovat:

ha 0 _ _ _ = []

Nechť n je větší než nula a předpokládejme, že problém ha n z c p umíme řešit pro n−1. Řešení rozdělíme na tři části:

1. Nejprve přestěhujeme n−1 disků do pomocné věže p, cílovou věž c použijeme jako pomocnou: ha (n-1) z p c.
2. Poslední disk přeneseme jedním přesunem ze zdrojové věže z do cílové věže c: [[z]++"–>"++[c]].
3. Odložených n−1 disků přestěhujeme do cílové věže; věž p se teď stává zdrojovou, věž z se stává pomocnou: ha (n-1) p c z.

Každá z těchto tří částí řešení je seznamem jednotlivých kroků (řetězců tvaru "z–>c"), takže řešení vznikne jejich spojením:

ha n z c p =    ha (n-1) z p c
             ++ [[z]++"->"++[c]]
             ++ ha (n-1) p c z

Funkce hanoi pro řešení problému hanoiských věží tedy bude:

hanoi :: Int -> [String]
hanoi n = ha n 'A' 'B' 'C'
          where ha 0 _ _ _ = []
                ha n z c p =    ha (n-1) z p c
                             ++ [[z]++"->"++[c]]
                             ++ ha (n-1) p c z

Máme-li instalován interpret Haskellu (např. Hugs nebo GHCi), dáme mu načíst definici funkce hanoi a pak si můžeme hrát: na vstup interpreta napíšeme volání funkce hanoi (aplikaci funkce hanoi na vhodné číslo) a interpret vypíše výsledek tohoto volání:

hanoi 3

["A->B","A->C","B->C","A->B","C->A","C->B","A->B"]

Výsledek je seznam řetězců, takže se také takto vypíše. Když budeme chtít, aby se jednotlivé přesuny vypisovaly pod sebe, musíme ze seznamu řetězců udělat jeden dlouhý řetězec. Krátké řetězce ze seznamu pospojujeme tak, že mezi každé dva vložíme znak oddělovače řádků, '\n'. To zařídí haskellovská funkce unlines::[String]–>String.

unlines (hanoi 3)

"A->B\nA->C\nB->C\nA->B\nC->A\nC->B\nA->B\n"

Výsledek je sice správně, ale interpret nám výstup vypisuje v „syrovém“ tvaru – tam, kde má být nový řádek, je jen jeho symbol ('\n') a celý výstupní řetězec zobrazen na jednom řádku. To proto, že interpret vypisuje hodnoty, tedy i řetězce, přesně v tom tvaru, v jakém se zapisují do výrazů. Pokud chceme, aby se oddělovače řádků a jiné řídicí znaky zobrazily přímo, použijeme funkci putStr, která, když ji aplikujeme na řetězec, vrátí takzvanou výstupní akci a ta se provede.

putStr (unlines (hanoi 3))

A->B
A->C
B->C
A->B
C->A
C->B
A->B

To je už docela přijatelný tvar (aspoň v rámci možností znakového výstupu).

Stále to však moc nepřipomíná práci se spustitelným programem. Povídáme si s interpretem stejně jako s kalkulačkou: napíšeme výraz, kalkulačka ho vyhodnotí a napíše výsledek (tzv. styl read-eval-write).

Jenže my bychom chtěli program, který lze přeložit a spustit a po spuštění bude sám číst vstup a psát na výstup, ne jen kód pro kalkulačku. Vytvoříme proto program, kterým bude vstupně-výstupní akce.

Vstupně-výstupní akce jsou novými hodnotami, se kterými se setkáváme. Příkladem takové akce je aplikace putStr "A\nB". Zatímco "A\nB" je řetězec typu String, putStr "A\nB" je akce typu IO () a interpret s ní naloží tak, že ji provede – znaky řetězce se pošlou na výstup přímo, písmeno A a pod něho písmeno B.

Náš program se bude skládat z více vstupních a výstupních akcí. Složené akce se z jednodušších vytvářejí pomocí konstrukce do.

main ::  IO ()
main  =  do putStr "n = "
            n <- getInt
            if n > 0
               then putStr (unlines (hanoi n))
               else return ()

Program se jmenuje main a skládá se ze tří akcí. První z nich je výstupní, putStr "n = ". Druhá je vstupní a obsahuje takzvaný vnitřní výsledek. U vstupních akcí je vnitřním výsledkem hodnota přečtená ze vstupu, v našem případě tedy celé číslo. Zápisem n <– getInt se vnitřní výsledek akce pojmenuje symbolem n. Třetí akce v main je výsledek podmíněného výrazu a závisí tedy na podmínce. Je-li načtené číslo kladné, vypíše se řešení problému věží. Pokud na vstupu zadáme záporné číslo nebo nulu, neprovede se nic. Přesněji, provede se akce return (), která nedělá se vstupem ani výstupem nic a jejímž vnitřním výsledkem je uspořádaná nultice ().

Celý program pak vypadá takto (použitá vstupní akce getInt není zařazena ve standardních knihovnách, které se implicitně importují, a proto je definovaná přímo v programu – o vstupních a výstupních akcích si ví ce řekneme později).

main ::  IO ()
main  =  do putStr "n = "
            n <- getInt
            if n > 0
               then putStr (unlines (hanoi n))
               else return ()

getInt ::  IO Int
getInt  =  getLine >>= return . read

hanoi   ::  Int -> [String]
hanoi n  =  ha n 'A' 'B' 'C'
            where ha 0 _ _ _ = []
                  ha n z c p =    ha (n-1) z p c
                               ++ [[z]++"->"++[c]]
                               ++ ha (n-1) p c z

Ještě jedna drobná poznámka k syntaxi. Pozor na to odsazování. V Haskellu lze použít dva styly psaní zdrojového textu. Buďto vůbec nemusíme dbát na formát a můžeme psát takto:

main = do { putStr "n = "; n <- getInt; if n > 0 then
putStr (unlines (hanoi n)) else return () }
hanoi n = ha n 'A' 'B' 'C' where { ha 0 _ _ _ = [];
   ha n z c p = ha (n-1) z p c
  ++[[z]++"->"++[c]]++ ha (n-1) p c z  }

Lokální definice a bloky do se přitom uzavírají do složených závorek a jednotlivé klausule se oddělují středníky. Tento styl je vhodný například pro programy generované jinými programy.

Anebo můžeme psát přehlednějším stylem, ušetřit si psaní závorek a středníků a místo nich strukturovat kód odsazováním – tak to zde děláme ve všech příkladech a zůstaneme u toho.