Haskell Hero

Co je to kalkulačka? Je to zařízení, kterému zadáme výraz (například 5 + 3 * 2) a ono nám zobrazí výsledek (v našem příkladě 11).

Naprogramujeme si tedy kalkulačku, která umí sčítat, odčítat a násobit. Abychom tak mohli učinit, budeme potřebovat dvě věci:

1. Zadefinovat výrazy, které budeme chtít, aby kalkulačka vyhodnocovala. Budeme je definovat jako nový datový typ, který pojmenujeme například Vyraz.
2. Zadefinovat funkci, která bude výrazy vyhodnocovat, čili z hodnot typu Vyraz bude dělat hodnoty typu Integer. Pojmenujeme ji například vyhodnot a bude tedy typu vyhodnot :: Vyraz -> Integer.

Do běžné kalkulačky zadáváme výrazy ve tvaru 5 + 3 * 2 (myšleno do kalkulačky, do které se napíše nejdřív celý výraz a pak se stiskne rovnítko). V Haskellu jsou ale celá čísla a operátory (+), (-) a (*) zabrané, takže si budeme muset definovat vlastní.

Vytvoříme tedy nový datový typ, který bude obsahovat všechna celá čísla.

data Vyraz  =  Cislo Integer

K těmto číslům přidáme také výraz, který bude znázorňovat sčítání výrazů:

data Vyraz  =  Cislo Integer  |  Plus Vyraz Vyraz

Plus (Cislo 2) (Cislo 5)
Plus (Cislo 4) (Cislo 8)
Plus (Cislo 2) (Plus (Cislo 2) (Cislo 3))

A podobně doplníme i výrazy znázorňující odčítání a násobení:

data Vyraz  =  Cislo Integer
            |  Plus  Vyraz Vyraz
            |  Minus Vyraz Vyraz
            |  Krat  Vyraz Vyraz

Plus (Cislo 5) (Krat (Cislo 3) (Cislo 2))

Nyní máme definovány výrazy a potřebujeme funkci, která nám například výraz

Plus (Cislo 5) (Krat (Cislo 3) (Cislo 2))

Začneme vyhodnocením výrazu Cislo x. Chtěli bychom, aby se například výraz Cislo 2 vyhodnotil na číslo 2. Nebo výraz Cislo 5 na číslo 5 atd. Definice tedy bude vypadat následovně:

vyhodnot           ::  Vyraz -> Integer
vyhodnot (Cislo x)  =  x

Dále musíme definovat vyhodnocení sčítacího výrazu. Chceme, aby se například výraz Plus (Cislo 2) (Cislo 3) vyhodnotil na 2 + 3 a to následně na 5. Jak takové vyhodnocení zapsat?

Výraz Plus x y vyhodnotíme následovně:

1. Rekurzivně pomocí funkce vyhodnot vyhodnotíme výraz x.
2. Stejně vyhodnotíme výraz y.
3. A jelikož víme, že funkce vyhodnot nám vrátí celé číslo, můžeme výsledky vyhodnocení vyhodnot x a vyhodnot y sečíst klasickým operátorem (+).

Do definice tedy můžeme doplnit klauzuli

vyhodnot (Plus x y)  =  (vyhodnot x) + (vyhodnot y)

vyhodnot (Minus x y)  =  (vyhodnot x) - (vyhodnot y)
vyhodnot (Krat  x y)  =  (vyhodnot x) * (vyhodnot y)

Celá definice tedy bude vypadat následovně:

vyhodnot             ::  Vyraz -> Integer
vyhodnot (Cislo x)    =  x
vyhodnot (Plus  x y)  =  (vyhodnot x) + (vyhodnot y)
vyhodnot (Minus x y)  =  (vyhodnot x) - (vyhodnot y)
vyhodnot (Krat  x y)  =  (vyhodnot x) * (vyhodnot y)

Krok po kroku vyhodnotíme výraz 5 + 3 * 2:

    vyhodnot (Plus (Cislo 5) (Krat (Cislo 3) (Cislo 2)))
~>  (vyhodnot (Cislo 5))  +  (vyhodnot (Krat (Cislo 3) (Cislo 2)))
~>          5             +  (vyhodnot (Krat (Cislo 3) (Cislo 2)))
~>  5  +  ((vyhodnot (Cislo 3))  *  (vyhodnot (Cislo 2)))
~>  5  +  (          3           *  (vyhodnot (Cislo 2)))
~>  5  +  (          3           *           2          )
~>  5  +  6
~>  11

Může vyvstat otázka — k čemu je to dobré? Vždyť Hugs umí sčítat i násobit sám od sebe, tak proč se zatěžovat definováním nového datového typu a funkce nad ním?

Zkusme si představit, že násobení na velkých číslech je mnohokrát výpočetně náročnější než sčítání. Například vyhodnocení výrazu 3 * (5 + 6) by vypadalo tak, že se nejdřív sečte pětka s šestkou a pak se tento výsledek vynásobí třemi. Jelikož známe distributivní zákon, víme, že 3 * (5 + 6) je to samé jako (3 * 5) + (3 * 6).

Protože jsme si na začátku řekli, že násobení je na velkých číslech mnohonásobně náročnější než sčítání, vidíme, že výraz (3 * 5) + (3 * 6) se vyhodnotí rychleji než výraz 3 * (5 + 6). Chtěli bychom tedy výrazy ve tvaru x * (y + z) převést do tvaru (x * y) + (x * z) a pak teprve začít vyhodnocovat. Jak bude vypadat funkce, která bude takové zjednodušení provádět?

zjednodus                     ::  Vyraz -> Vyraz
zjednodus (Krat x (Plus y z))  =
                Plus (Krat (zjednodus x) (zjednodus y))
                     (Krat (zjednodus x) (zjednodus z))
zjednodus _                    =  _