Počáteční problémy imperativních programátorů

Snad všechny mainstreamové programovací jazyky jsou imperativní. Zatímco Haskell je funkcionální. Čistě funkcionální. Což v důsledku znamená, že je jiný. To může programátorům, kteří nikdy v žádném funkcionálním jazyce nepracovali, z počátku přinášet nutnost vynaložit větší úsilí k napsání byť i jednoduchých konstrukcí. Je si totiž potřeba zvyknout na trochu jiný způsob myšlení při psaní kódu. Jakmile si však zvyknete, nejen že nebude problém se s funkcionálními jazyky domluvit, ale rozšíříte si obzory a nově nabyté zkušenosti můžete zužitkovat i v běžných imperativních jazycích. Nemluvě o tom, že i imperativní jazyky (C#, Python, …) čím dál více zavádějí často s velkou slávou techniky, které jsou ve funkcionálních jazycích běžné.

Zde se vám pokusíme poskytnout informace, které pomohou zmiňovanou změnu ve způsobu myšlení překonat rychleji.

Inu, cykly nejsou. Cykly jsou nahrazeny rekurzí, případně problém, který bychom řešili cyklem, řešíme použitím funkcí vyššího řádu.

Je ve spoustě případů přehlednější. Možná vás napadne: co paměť? a co když nedej bože potřebuji nekonečný cyklus? Není potřeba se bát, kompilátor Haskellu (mluvíme o GHC, ale platí to i pro ostatní), jako většina implementací funcionálních jazyků, optimalizuje tzv. tail rekurzi. Jinými slovy, pokud zjistí, že se po rekurzivním skoku ve funkci již nic vykonávat nemá, zjednodušeně řečeno nahradí rekurzivní volání funkce skokem a už se do aktuálního zanoření nevrací. Programátor však musí vědět, jaké volání je tail-rekurzivní.

Každý cyklus je možné zapsat rekurzí. Pokud bychom v Haskellu měli naprogramovat cyklus for, vypadal by např. následovně:

  for m n f
    | m > n     = return ()
    | otherwise = f m >> for (m + 1) n f

Použít se dá následovně:

  for m n f
    | m > n     = return ()
    | otherwise = f m >> for (m + 1) n f
 
  main = do
    putStrLn "tri, dva, jedna, start.. "
    for 1 100 $ \i ->
        putStrLn ("Radek cislo " ++ show i)
    putStrLn "Konec"

$ ghc test.hs -o test
$ ./test
tri, dva, jedna, start..
Radek cislo 1
Radek cislo 2
...
Radek cislo 99
Radek cislo 100
Konec

To bylo ovšem jen na ukázku, že běžný cyklus pomocí rekurze vyjádřit jde a není to nijak složité. Troufám si tvrdit, že většině případů tohle není nutné.

Jak již bylo naznačeno, tail rekurze je speciální případ rekurze, kdy poslední operací funkce je její rekurzivní volání. Takové rekurze mohou být snadno nahrazeny kompilátorem iterací, čímž se zbavíme problému s narůstáním potřebné paměti na zásobníku se zvyšující se úrovní rekurzivního zanoření. GHC, ale i další překladače funkcionálních jazyků ji automaticky optimalizují bez toho, abychom jim to museli explicitně říkat.

Zde vidíme příklad faktoriálu zapsaného rekurzivně:

factorial 0 = 1
factorial n = n * factorial (n-1)

Při vyhodnocení musí nejříve znát obě hodnoty součinu, musí tedy nejprve rekurzivně volat funkci factorial a až po tom její návratovou hodnotu vynásobit s n. Zápis tedy není tail-rekurzivní. Odpovídající tail-rekurzivní faktoriál vidíme na následujícím příkladu:

factorial n = fact n 1 where
   fact 0 result = result
   fact n result = fact (n-1) (n * result)

Vytvořili jsme si tail-rekurzivní funkci fact, kterou voláme z funkce factorial (takto je to řešené pouze z důvodu zachování počtu parametrů původní funkce factorial). Při vyhodnocení funkce fact se nejdříve vypočítají parametry a potom se rekurzivě volá. Po případném návratu z rekurzivního volání se už nic nevykonává, vracet se tedy ani neni nutné. Mezivýsledek si předává v druhém parametru a ten v případě, že parametr n má hodnotu 0, vrátí.

Pozn: popisovaná funkce není totální – není definované pro hodnoty parametrů n < 0, v takovém případě bude cyklit, což nám nevadí, protože jde jen o ukázkový příklad.

A teď něco zajímavějšího. Funkce druhého řádu jsou běžné už z dob LISPu, ale i třeba objektového Smalltalku. Jsou to funkce, které jako jeden z parametrů přijímají jinou funkci. Není samozřejmě problém něco takového implementovat třeba v C, ale ve funkcionálních jazycích jde o standardní programovou konstrukci. Nejznámější funkce druhého řádu jsou beze sporu map a fold (ať už se jmenuje jakkoli – v haskellu jde o foldl, ve Smalltalku nebo Ruby je známý pod názvem inject). Ty můžete najít i v imperativních jazycích jako např. Python, Ruby, C# a podobně, tak jejich znalost můžete využít i tam.

Typová signatura funkce map vypadá následovně:

map :: (a -> b) -> [a] -> [b]

První parametr je funkce, druhý seznam. map aplikuje zadanou funkci na každý prvek seznamu a vrátí seznam výsledků. Zadaný a výsledký seznam nemusí být stejného typu. Vyhodnocení probíhá tedy následovně:

map f [a1, a2, ..., an]  ~>  [f a1, f a2, ..., f an]

Příklady použití

map (* 2) [1,2,3,4]                    ==>  [2,4,6,8]
 
map snd [(1, "hello"), (2, "world")]   ==> ["hello", "world"]
 
map (\x -> if odd x
                then x + 1
                else x) [1..10]        ==> [2,2,4,4,6,6,8,8,10,10]

Typová signatura funkce foldl vypadá následovně:

foldl   :: (a -> b -> a) -> a -> [b] -> a

Prvním parametrem je funkce přijímající dva parametry, druhým je výchozí hodnota výsledku, třetím seznam. Vyhodnocení funkce fold probíhá postupnou aplikací funkce na všechny prvky pole a mezivýsledek, který se na počátku rovná výchozí hodnotě, jak je znázorněno na následujícím příkladu:

foldl f x [a1, a2, ..., an]  ~>  (f ... (f (f x a1) a2) ... an)

Následují příklady použití. Jsou to pouze ukázky použití funkce foldl, většinu těchto funkcí najdete již implementovanou ve standardních knihovnách. Doporučuji projít zejména knihovnu Prelude.

-- implementace nekterych agregacnich funci znamych napr. ze SQL pomoci funkce foldl
sum lst = foldl (+) 0 lst
 
sum [1,2,3]  ==> 6
 
count lst = foldl (\r _ -> r+1) 0 lst
 
count ["a", "b", "c", "d"]   ==> 4
 
-- pozn: funkce pocita s pripadem, kdy seznam neni prazdny
min lst = foldl (\r x -> if x < r
                            then x
                            else r) (head lst) lst
 
-- dalsi prilklady
foldl (\r i -> r ++ "<li>" ++ show i ++ "</li>\n") "" [1,2,3]   ==>
"<li>1</li>
<li>2</li>
<li>3</li>"
 
-- vypocet faktorialu
foldl (*) 1 [1..5]  ==> 120

Opět začneme typovou signaturou:

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Funkce prochází postupně prvky dvou zadaných seznamů, předá je jako parametr zadané funkci a návratovou hodnotu uloží do výsledného seznamu.

Vyhodnocení tedy probíhá následovně:

zipWith f [a1, a2, ..., an] [b1, b2, ..., bn]  ~>  [f a1 b1, f a2 b2, ..., f an bn]

Příklady použití

zipWith (*) [1,2,3] [4,5,6]    ==>  [4,10,18]
 
zipWith (\x y -> if x == y
                    then True
                    else False) [1,2,3,4] [1,3,2,4]   ==> [True, False, False, True]

Inu, ani proměnné v běžném slova smyslu nejsou. Haskell je referenčně transparentní, nepřipouští tedy žádné implicitní vedlejší efekty. Například globální proměnné jsou považovány i v imperativních jazycích za věc, která se ve slušných rodinách nepoužívá. Má to své důvody a nemluvím jen o přehlednosti kódu.

(: neni to moc velka propaganda? kdyz ona to je pravda, tak co…;)
Vedlejší efekty mají neblahý vliv na obtížnost analýzy kódu, což ztěžuje optimalizaci, verifikaci a podobně. Absence vedlejších efektů v Haskellu má nemalý podíl na tom, že GHC produkuje, na to, jak je Haskell vysokoúrovňový jazyk, velmi rychlý kód. Obrovskou výhodu to přináší při analýze paralelismu. Pokud jste zatím neslyšeli pojmy jako nested data parallelism nebo software transactional memory a vyvíjíte software, který poběží na víceprocesorových strojích (což je dnes i na stolních počítačích běžné), doporučuji prozkoumat. Jeho výzkumem a implementací v překladači Haskellu GHC se zabývají vědci z Microsoft Research a University of New South Wales. O paralelismu v jazyce Haskell se více dozvíte zde (: odkaz na wiki na haskell.cz).

Ale abychom se vrátili k věci.