Redukční krok
- jeden podvýraz se nahradí zjednodušeným podvýrazem
- Redex = upravovaný podvýraz, který má tvar aplikace na argumenty, upravený podvýraz má tvar pravé strany definice této funkce do níž jsou za formální parametry dosazené skutečné parametry
- Nejdříve upravujeme argument, nezle-li, upravujeme výraz.
- při úpravě postupujeme zevnitř
- při úpravě postupujeme zvnějšku
- Normální redukční strategie, při niž si pamatujeme hodnoty upravených podvýrazů a žádný s opakovaným výskytem nevyhodnocujeme více než jednou.
- Referenční transparentnost = pokud se výraz vyhodnotí, vyhodnotí se na jeden výsledek
Haskell
- Používá normální redukční strategii.
- Nicméně mluví o líném vyhodnocování, zjednodušeně řečeno, vyhodnotí se pouze to, co je potřeba k dalšímu výpočtu
definice funkce
cube x = x *x * x
Striktní redukční strategie
cube (3+5) --> cube 8 --> 8 * 8 * 8 --> 64 * 8 --> 512
Normální redukční strategie
cube (3+5) --> (3+5) * (3+5) * (3+5)
--> 8 * (3+5) * (3+5) --> 8 * 8 * (3+5)
--> 64 * (3+5) --> 64 * 8 --> 512
Líná redukční strategie
cube (3+5) --> (3+5) * (3+5) * (3+5)
--> 8 * 8 * 8
- Výsledná hodnota ukončeného výpočtu výrazu nezáleží na redukční strategii: pokud výpočet skončí, je jeho výsledek vždy stejný
- Jestliže pro nějaký výraz M existuje redukční strategie, s jejímž použitím se úprava výrazu M zacyklí, pak se tento výpočet zacyklí i s použitím striktní redukční strategie.
- Jestliže pro nějaký výraz M existuje redukční strategie, s jejímž použití se úprava výrazu M nezacyklí, pak se tento výpočet nezacyklí ani s použitím normální strategie.
- Vyhodnocení až v okamžiku, kde je potřeba pro další výpočet, umožňuje manipulaci s nekonečnými datovými strukturami.
repeat :: a -> [a]
repeat x = x : repeat x
take 8 (repeat 1) --> [1,1,1,1,1,1,1,1]
head (repeat 1) --> head (1 : repeat 1) --> 1
enumFromTo 1 12 --> [1,2,3,4,5,6,7,8,9,10,11,12]
enumFromTo 'A' 'Z' -->asd
- nekonečná enumerace
nats = enumFrom 0
enumFrom m Enum => a -> [a] [m..]
enumFromTo m n Enum => a -> a -> [a] [m..n]
enumFromThen m m' Enum => a -> a -> [a] [m, m'..]
enumFromThen m m' n Enum => a -> a -> a -> [a] [m, m'..n]
- prvních deset násobků čísla 2:
[ 2*n | n <- [0..9] ]
[ definiční výraz | generátor a kvalifikátory ]- Kvalifikátory a generátory se vyhodnocují zleva doprava.
nová_proměnná <- seznam nebo vzor <- seznam
- Výraz typu
Bool
- Můžeme používáme výrazy z levé strany predikátu,
- Vygenerované instance, které nevyhovují predikátu, nebudou brány v potaz.
let nová_proměnná = výraz- Na pravé straně od použití proměnné.