Haskell Hero

Příklad

Vyhodnoťte krok po kroku výraz trikrat (5 + 2), kde

trikrat x = x + x + x

Jak začít? Vyhodnotit první 5 + 2, nebo to celé rozepsat podle definice funkce trikrat?

Odpověď zní: záleží na zvolené redukční strategii. Máme na výběr z následujícíh tří:

• normální redukční strategie
• striktní redukční strategie
• líná redukční strategie

Haskell bez dalšího upřesnění vyhodnocuje líně.

Normální redukční stratregie spočívá ve vyhodnocování zvnějšku. Řečeno konkrétněji, pokud je vyhodnocovaný výraz ve tvaru F X a F se dá aplikovat na X, aplikuj F na X. V opačném případě vyhodnoť samotné F, opět podle normální strategie.

Kratčeji: Bez ohledu na vyhodnocení argumentů aplikuj funkci F.

Náš ukázkový výraz by se tedy podle normální strategie vyhodnotil následovně:

trikrat (5 + 2)

~>  (5 + 2) + (5 + 2) + (5 + 2)
~>     7    + (5 + 2) + (5 + 2)
~>     7    +    7    + (5 + 2)
~>     7    +    7    +    7
~>          14        +    7
~>  21

Striktní redukční stratregie spočívá ve vyhodnocování zevnitř. Řečeno konkrétněji, nejprve vyhodnoť argumenty na nezjednodušitelné výrazy a teprve potom aplikuj funkci.

Náš ukázkový výraz by se tedy podle striktní strategie vyhodnotil následovně:

trikrat (5 + 2)

~>  trikrat 7
~>  7 + 7 + 7
~>    14  + 7
~>  21

Líné vyhodnocování funguje na stejném principu jako vyhodnocování normální. S tím rozdílem, že si pamatujeme výsledky vyhodnocení jednotlivých výrazů. Před každým vyhodnocením se nejdřív podíváme, jestli jsme již takový výraz někdy nevyhodnocovali. Pokud ano, použijeme výsledek z prvního vyhodnocení.

Náš příklad vyhodnocený líně by tedy vypadal takto:

trikrat (5 + 2)

~>  (5 + 2) + (5 + 2) + (5 + 2)
~>  7 + 7 + 7
~>    14  + 7
~>  21

Vždyť se přece zdá, že striktní strategie je nejefektivnější. Nemusí se kontrolovat, zda se výraz již jednou nepočítal, a je nejrychlejší. Tak proč další dvě strategie?

Například kvůli vyhodnocení výrazu take 3 [1..]. Seznam prvních tří prvků z nekonečného seznamu začínajícího jedničkou je [1,2,3]. Jak by vypadalo striktní vyhodnocení?

take 3 [1..]

~>  take 3 ( 1: [2..] )
~>  take 3 ( 1: 2: [3..] )
~>  take 3 ( 1: 2: 3: [4..] )
~>  take 3 ( 1: 2: 3: 4: [5..] )
~>  take 3 ( 1: 2: 3: 4: 5: [6..] )
~>  take 3 ( 1: 2: 3: 4: 5: 6: [7..] )
~>  ...

take 3 [1..]

~>  take 3 ( 1: [2..] )

~>  1 : take 2 [2..]

~>  1 : take 2 ( 2: [3..] )

~>  1 : 2 : take 1 [3..]

~>  1 : 2 : take 1 ( 3: [4..] )

~>  1 : 2 : 3 : take 0 [4..]

~>  1 : 2 : 3 : []

False && _  =  False
True  && x  =  x
------------------------

False && ( and [True, True..] )

~>  False

O línou nádstavbu jsme normální strategii doplnili proto, abychom zabránili vícenásobnému vyhodnocování stejných výrazů.