Vyhodnocovací strategie (lenost vs. striktnost)
IB016 Seminář z funkcionálního programování
Adam Matoušek, Henrieta Micheľová
(původní autoři slajdů Vladimír Štill, Martin Ukrop)
Fakulta informatiky, Masarykova univerzita
Jaro 2021
IB016: Cvičení 04 Jaro 2021 1 / 20
Líné vyhodnocování: příklad
fst (1, undefined) ∗ 1
druhá složka dvojice se vůbec nevyhodnotí
let fact n = product [1..n]
in map fact [1000000,999999..0] !! 999995 ∗ 120
jednotlivé prvky jsou vypočítány, jen když jsou vyžádány
(počítá se jen faktoriál pětky)
let fibs = 0:1:zipWith (+) fibs (tail fibs)
in fibs !! 100 ∗ 354224848179261915075
seznam je konstruován líně, tedy jen prvky, které jsou potřeba
IB016: Cvičení 04 Jaro 2021 2 / 20
Líné vyhodnocování
každá hodnota v Haskellu může být
a) vyhodnocená
b) nevyhodnocená – tzv. thunk – výraz, který lze vyhodnotit
pokud se snažíme nevypočítanou hodnotu přečíst, vypočítá se
při příštím čtení je již vypočítaná
vyhodnocuje se vždy jen to, co je nezbytně nutné
jen ty části výrazů, jejichž výsledek je potřeba
jen do té hloubky, dokud je to nutné
(vzpomeňte na take na nekonečných seznamech)
IB016: Cvičení 04 Jaro 2021 3 / 20
Líné vyhodnocování
fact n = product [1..n]
facts = map fact [0..]
[] !! _ = error "(!!): index too large"
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n - 1)
facts !! 1
(map fact [0..]) !! 1
(map fact (0:[1..])) !! 1
(fact 0 : map fact [1..]) !! 1
(map fact [1..]) !! (1 - 1)
(map fact (1:[2..])) !! (1 - 1)
(fact 1 : map fact [2..]) !! (1 - 1)
(fact 1 : map fact [2..]) !! 0
fact 1 product [1..1] ∗ 1
IB016: Cvičení 04 Jaro 2021 4 / 20
Striktnost a lenost
selectsort :: Ord a => [a] -> [a]
selectsort [] = []
selectsort xs = min : selectsort (withoutMin xs)
where
min = minimum xs
withoutMin (y:ys)
| y == min = ys
| otherwise = y : withoutMin ys
striktní vzhledem ke struktuře seznamu (vyžaduje vyhodnotit
seznam až po [])
vyhodnotí všechny prvky až do té míry jak vyžaduje (<)
ale produkuje výstup líně!
jaká je složitost head (selectsort [10000,9999..0])?
O(n)
IB016: Cvičení 04 Jaro 2021 5 / 20
Sdílení podvýrazů
(1 + 2) * (1 + 2)
*
+ +
1 2 1 2
let a = 1 + 2 in a * a
*
+
1 2
square a = a * a
> square (1 + 2)
IB016: Cvičení 04 Jaro 2021 6 / 20
Sdílení v GHCi
standardně GHCi vypisuje hodnoty pomocí print, což
obvykle způsobuje plné vyhodnocení
pomocí :sprint lze vypsat bez vynucení vyhodnocení
pozor, polymorfní výrazy se vyhodnocují vždy znovu
> a = 5 + 2 :: Int
> xs = [a, 1, 2, a, 3]
> :sprint xs
xs = _ -- xs je thunk (nevyhodnocený výraz)
> head xs
7
> :sprint xs
xs = 7 : _ -- ocásek xs se zatím nevyhodnotil
> length xs
5
> :sprint xs
xs = [7, _, _, 7, _]
IB016: Cvičení 04 Jaro 2021 7 / 20
Teoretická vsuvka: vyhodnocovací strategie
Striktní vyhodnocovací strategie
výrazy vyhodnoceny při přiřazení do proměnných
argumenty vyhodnoceny před voláním
pořadí vyhodnocování obvykle do značné míry jasné ze
zdrojového kódu
typické pro imperativní jazyky, ale i mnohé funkcionální (*ML)
Normální/nestriktní vyhodnocovací strategie
výrazy se vyhodnocují, až když jsou potřeba
umožňuje existenci potenciálně nekonečných datových struktur
pořadí vyhodnocení méně viditelné
může mít větší spotřebu paměti (nevyhodnocené výrazy)
Líná vyhodnocovací strategie
normální + sdílení podvýrazů
IB016: Cvičení 04 Jaro 2021 8 / 20
Vzory vynucují vyhodnocení
f1, f2, f3 :: [a] -> ()
f1 _ = ()
f2 (_:_) = ()
f3 (_:_:[]) = ()
f1 undefined ∗ ()
f2 undefined ∗ *** Exception: Prelude.undefined
f1 [] ∗ ()
f2 [] ∗ *** Exception: ...
f2 [undefined,undefined] ∗ ()
f3 [undefined,undefined] ∗ ()
f2 (undefined:undefined) ∗ ()
f3 (undefined:undefined) ∗ *** Exception: ...
Argument se vyhodnocuje jen do hloubky nezbytně nutné k
rozhodnutí, zda hodnota odpovídá vzoru.
IB016: Cvičení 04 Jaro 2021 9 / 20
Líné vzory
Vlnovkou před vzorem lze odložit pattern matching až do
doby, kdy se nějaký argument navázaný vzorem použije.
Takový vzor nevynucuje vyhodnocení a vždy uspěje.
Srovnejte:
strict, lazy :: Bool -> Maybe Int -> Int
strict b (Just x) = if b then x else 0
lazy b ~(Just x) = if b then x else 0
strict False Nothing ∗ ???
lazy False Nothing ∗ ???
lazy True Nothing ∗ ???
f ~(x, y) = g x y se přeloží na (něco jako)
f p = g (fst p) (snd p)
IB016: Cvičení 04 Jaro 2021 10 / 20
seq vynucuje vyhodnocení
Funkce seq :: a -> b -> b
a `seq` b zaručuje, že a bude vyhodnoceno, a vrátí b
k vyhodnocení dojde až když něco vynutí výpočet výrazu
a `seq` b
nevyhodnocuje a plně, nýbrž jen po nejvyšší konstruktor:
(undefined, undefined) `seq` 1 ∗ 1
undefined `seq` 1 ∗ *** Exception: ...
Striktní aplikace ($!) :: (a -> b) -> a -> b
obdoba ($), ale vynutí vyhodnocení argumentu před aplikací
f1 $! undefined ∗ *** Exception: ...
IB016: Cvičení 04 Jaro 2021 11 / 20
Weak head normal form
seq vynucuje vyhodnocení pouze do tzv. weak head normal form:
po nejvyšší (i část. aplik.) hodnotový konstruktor, nebo
dokud výraz není λ-abstrakce, nebo
dokud výraz není nedostatečně aplikovanou vestavěnou funkcí.
Příklady výrazů a jejich WHNF:
replicate 3 'A' (:) 'A' (replicate (3-1) 'A')
replicate 3 \x -> x : replicate (3-1) x
head \(x:xs) -> x
(\x -> if x then Right else Left) (4 < 3) Left
Just (replicate 3 'A') už je ve WHNF
(+) (4 * 5) už je ve WHNF (uvažujeme-li vestavěné plus)
IB016: Cvičení 04 Jaro 2021 12 / 20
Proč striktnost?
striktní výpočet může být rychlejší, paměťově efektivnější
> :set +s
(0.18 secs, 74075592 bytes)
> const () $! product [1..100000]
()
(18.32 secs, 9052106864 bytes)
> :m + Data.List
> const () $! foldl' (*) 1 [1..100000]
()
(2.73 secs, 9045968328 bytes)
foldl' je striktní verze foldl
IB016: Cvičení 04 Jaro 2021 13 / 20
Proč striktnost?
readFiles :: [FilePath] -> IO [String]
readFiles paths = mapM readFile paths
readFile vrací obsah souboru líně
soubor je zavřen až když je dočten na konec!
lehce můžeme překročit limit na množství otevřených souborů
seq nepomůže
IB016: Cvičení 04 Jaro 2021 14 / 20
Control.DeepSeq
Úplné/hluboké vyhodnocení.
import Control.DeepSeq
readFiles :: [FilePath] -> IO [String]
readFiles paths = forM paths $ \p ->
withFile p ReadMode $ \h -> do
c <- hGetContents h
return $!! c
($!!) :: NFData a => (a -> b) -> a -> b
plně vyhodnotí argument, pak aplikuje funkci
deepseq :: NFData a => a -> b -> b
class NFData a where
rnf :: a -> ()
plně vyhodnotí argument
IB016: Cvičení 04 Jaro 2021 15 / 20
Control.DeepSeq
import Control.DeepSeq
data BinTree a = Empty
| Node a (BinTree a) (BinTree a)
deriving (Show, Eq)
instance NFData a => NFData (BinTree a) where
rnf Empty = ()
rnf (Node v t1 t2) = rnf v `seq` rnf t1 `seq`
rnf t2
IB016: Cvičení 04 Jaro 2021 16 / 20
Rozšíření BangPatterns
{- # LANGUAGE BangPatterns # -}
Umožňuje snadno vynutit striktnost u vzoru, výrazu let,
argumentu hodnotového konstruktoru.
data Tuple a b = Tuple !a !b
lazy, strict :: a -> ()
lazy _ = ()
strict !_ = ()
taková hodnota je pak před aplikací funkce/konstruktoru
vyhodnocena do WHNF (po první konstruktor)
v let způsobí vyhodnocení příslušného výrazu před započetím
vyhodnocování části in (striktní let)
($!) :: (a -> b) -> a -> b
($!) f x = let !ex = x in f ex
IB016: Cvičení 04 Jaro 2021 17 / 20
Rozšíření StrictData a Strict
{- # LANGUAGE StrictData # -}
jako by všechna pole v datových definicích v daném modulu
byla definována pomocí ! (z rozšíření BangPatterns)
lenost může být vynucena vlnovkou (data T = D ~Int)
{- # LANGUAGE Strict # -}
obsahuje StrictData
argumenty funkcí, definice where/let, vazby v case/do jsou
také striktní
vnořené vzory a top-level definice nadále striktní nejsou
https://downloads.haskell.org/~ghc/latest/docs/html/
users_guide/glasgow_exts.html#extension-StrictData
IB016: Cvičení 04 Jaro 2021 18 / 20
Striktnost v knihovně
Data.List: foldl', foldl1' – akumulátorem je jediná, vždy
vyhodnocená hodnota namísto potenciálně obrovského thunku
(nevyhodnoceného výrazu).
Data.Map.Lazy – klíče se vyhodnocují striktně (ukládají se už
vyhodnocené pro rychlejší vyhledávání).
Data.Map.Strict – klíče i hodnoty se ukládají vyhodnocené.
Pokročilé věci související s transformátory monád a ST.
IB016: Cvičení 04 Jaro 2021 19 / 20
Procvičení
Naprogramujte variantu ohodnocených binárních stromů se
striktními hodnotami (StrictValTree), ale línou reprezentací
stromové struktury, a variantu, která je plně striktní jak ve
struktuře tak v hodnotách (StrictTree).
rozmyslete si, pro jaké použití by se mohly jednotlivé varianty
hodit a kdy byste naopak použili línou variantu
rozmyslete si, jaké prostředky z tohoto cvičení chcete použít
pro vynucení striktnosti v jednotlivých případech a proč
pro obě verze stromů implementujte instanci Functor
IB016: Cvičení 04 Jaro 2021 20 / 20