Funkcionální programování - Příklad o hanoiských věžích
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

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

Google       Google       27. 10. 2006       15 110×

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.

Reklama
Reklama
Pomocí perátoru (++) lze spojit dva seznamy stejného typu.

(++)       ::  [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:

AC Menší disk odložíme do C.
AB Přestěhujeme větší.
CB Odložený disk umístíme do B.

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

AB
AC
BC
Dva menší disky odstěhujeme do pomocné věže C; přitom použijeme výše uvedeného postupu pro dva disky, jen si vymění role cílová a pomocná věž, tj. A teď bude zdrojová, C cílová, B pomocná.
AB Přesuneme největší disk do cílové věže B.
CA
CB
AB
Dva disky odložené ve věži C odstěhujeme do cílové věže B; přitom zase použijeme známého postupu pro dva disky, jen si vymění role zdrojová a pomocná věž, tj. C teď bude zdrojová, B cílová, A pomocná.

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.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

1 názor  —  1 nový  
Hlasování bylo ukončeno    
0 hlasů
Google
Autor je profesorem na Fakultě informatiky Masarykovy univerzity v Brně.

Nové články

Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý