IB015 Neimperativní programování
Akumulační funkce, Typové třídy,
Časová složitost
Jiří Barnat
Libor Škarvada
Sekce
Akumulační funkce
IB015 Neimperativní programování – 07 str. 2/47
Akumulační funkce foldl, foldr
Pozorování
Seznam je posloupnost oddělených prvků.
Motivací akumulačních funkcí je “spojit” jednotlivé prvky
seznamu dohromady, tj. akumulovat informaci uloženou
v těchto jednotlivých prvcích do jedné hodnoty.
Počet prvků seznamu je variabilní, proto se tato akumulace
realizuje pomocí binárního operátoru postupně.
Spojení hodnot v seznamu pomocí binární operace
foldl1 ⊕ [x1,x2,...,xn] ∗
((...(x1⊕x2)...)⊕xn−1)⊕xn
foldr1 ⊕ [x1,x2,...,xn] ∗
x1⊕(x2⊕(...(xn−1⊕ xn)...))
IB015 Neimperativní programování – 07 str. 3/47
Akumulační funkce na neprázdných seznamech
Příklady použití
foldl1 (*) [1,2,3,4,5] ... 120
foldl1 (&&) [True, True, True, False, True] ... False
foldl1 (-) [2,3,2] ... -3
foldr1 (-) [2,3,2] ... 1
foldr1 (min) [18,12,23] ... 12
Funkce foldl1, foldr1 nejsou definovány pro []
foldl1 (*) [] ERROR
foldr1 (&&) [] ERROR
Na jednoprvkových seznamech je to identita s kontrolou typu
foldr1 (*) [0] 0
foldr1 (*) [1] 1
foldr1 (*) [True] ERROR
IB015 Neimperativní programování – 07 str. 4/47
Akumulační funkce foldl, foldr
Princip
Akumulační funkce, které mají fungovat i na prázdných
seznamech, vyžadují navíc iniciální hodnotu pro proces
akumulace.
Směr závorkování určuje i místo použití iniciální hodnoty.
Akumulace hodnot s využitím iniciální hodnoty
foldl ⊕ v [x1,x2,...,xn] ∗
((...((v⊕x1)⊕x2)...)⊕xn−1)⊕xn
foldr ⊕ v [x1,x2,...,xn] ∗
x1⊕(x2⊕(...(xn−1⊕(xn⊕v))...))
IB015 Neimperativní programování – 07 str. 5/47
Akumulační funkce na libovolných seznamech
Příklady
foldl (*) 0 [1,2,3,4,5] ... 0
foldl (&&) False [True, True, True, True] ... False
foldl (-) 0 [2,3,2] ... -7
foldr (-) 0 [2,3,2] ... 1
Aplikace na prázdné seznamy
foldl max 100 [] ... 100
foldr (++) "Nic"[] ... "Nic"
Výsledek může být opět seznam!
foldr (:) [] "Coze?" ... "Coze?"
foldr (\x y->(x+1):y) [100] [1,2,3] ... [2,3,4,100]
IB015 Neimperativní programování – 07 str. 6/47
Definice akumulačních funkcí
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ v [] = v
foldl op v (x:s) = foldl op (v ‘op‘ x) s
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ v [] = v
foldr op v (x:s) = x ‘op‘ foldr op v s
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 op (x:s) = foldl op x s
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 _ [x] = x
foldr1 op (x:s) = x ‘op‘ foldr1 op s
IB015 Neimperativní programování – 07 str. 7/47
Grafické znázornění foldr (katamorfismus)
foldr f z
1
:
2
:
3
:
4
:
5
:
[]
1
f
2
f
3
f
4
f
5
f
z
IB015 Neimperativní programování – 07 str. 8/47
Grafické znázornění foldl
foldl f z
1
:
2
:
3
:
4
:
5
:
[]
f
f
3
f
f
f
z 11
22
44
55
IB015 Neimperativní programování – 07 str. 9/47
Katamorfismus na seznamech
Katamorfismus
Výraz vzniklý nahrazením hodnotových konstruktorů v nějaké
hodnotě algebraického typu jinými funkcemi vhodné arity.
Nově vzniklý výraz je následně možné vyhodnotit (pokud lze).
Katamorfismus na seznamech
Realizován funkcí foldr .
Porovnejte typy hodnotových konstruktorů seznamu
(:) :: a -> [a] -> [a]
[] :: [a]
s typem funkce foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
IB015 Neimperativní programování – 07 str. 10/47
Katamorfismus na Peanových číslech
Peanova čísla
data Nat = Succ Nat | Zero
Katamorfismus na typu Nat
natFold :: (a -> a) -> a -> Nat -> a
natFold s z (Succ n) = s (natFold s z n)
natFold s z Zero = z
Příklad
Katamorfismus: Zero → 0
Succ → (1+)
natFold (1+) 0 (Succ (Succ Zero) ∗ (1+) ( (1+) 0 ) ∗ 2
IB015 Neimperativní programování – 07 str. 11/47
Katamorfismus na binárních stromech
Připomenutí
data BinTree a = Node a (BinTree a) (BinTree a) | Empty
Hodnotové konstruktory
Node :: a -> BinTree a -> BinTree a -> BinTree a
Empty :: BinTree a
Hodnotový konstruktor Node je ternární, i když se používá
pro konstrukci binárních stromů.
Katamorfismus na binárních stromech
treeFold :: (a -> b -> b -> b) -> b -> BinTree a -> b
treeFold n e (Node v l r) = n v (treeFold n e l)
(treeFold n e r)
treeFold n e Empty = e
IB015 Neimperativní programování – 07 str. 12/47
Katamorfismus na binárních stromech – příklad
Fold na binárních stromech
data BinTree a = Node a (BinTree a) (BinTree a) | Empty
let tree = Node 1 (Node 2 Empty Empty) Empty in
treeFold (\v l r -> v+l+r) 0 tree
∗ 1+(2+0+0)+0 ∗ 3
Graficky:
N
EN
EE2
1
treeFold (...) 0
−−−−−−−−→
\v l r → v+l+r
0\v l r → v+l+r
002
1 3
IB015 Neimperativní programování – 07 str. 13/47
Sekce
Typové třídy
IB015 Neimperativní programování – 07 str. 14/47
Připomenutí klasifikace typů
Monomorfní typy
not :: Bool -> Bool
(&&) :: Bool -> Bool -> Bool
Polymorfní typy
length :: [a] -> Int
flip :: (a -> b -> c) -> b -> a -> c
Kvalifikované typy
(==), (/=) :: Eq a => a -> a -> Bool
sum, product :: Num a => [a] -> a
minimum, maximum :: Ord a => [a] -> a
print :: Show a => a -> IO ()
IB015 Neimperativní programování – 07 str. 15/47
Typové třídy
Typové třídy
Sdružují a identifikují typy se společnými vlastnostmi.
Typová kvalifikace – Ord,Nat,Eq,Show,Foldable,...
Programátorský význam
Existence typových tříd umožňuje i ve striktně typovaných
jazycích sdílet kód funkcí, které dělají totéž, avšak pracují
s hodnotami různých typů.
Sdílení kódu funkcí, které dělají totéž,
by měl být svatý grál všech programátorů.
IB015 Neimperativní programování – 07 str. 16/47
Příklad typové třídy a jejího využití
Typová třída Eq
class Eq a where
(==), (/=) :: a -> a -> Bool
x /= y = not (x == y)
Přidružení typů k typové třídě (deklarace instance)
instance Eq Bool where
False == False = True
True == True = True
_ == _ = False
instance Eq Int where
(==) = primEqInt
instance (Eq a, Eq b) => Eq (a,b) where
(x,y) == (u,v) = x == u && y == v
IB015 Neimperativní programování – 07 str. 17/47
Využití typové třídy jinou typovou třídou
Typová třída Ord využívající typovou třídu Eq
class (Eq a) => Ord a where
(<=), (>=), (<), (>) :: a -> a -> Bool
max, min :: a -> a -> a
x >= y = y <= x
x < y = x <= y && x /= y
x > y = y < x
max x y = if x>= y then x else y
min x y = if x<= y then x else y
Deklarace instance
instance Ord Bool where
False <= _ = True
_ <= True = True
_ <= _ = False
instance (Ord a, Ord b) => Ord (a,b) where
(x,y) <= (u,v) = x < u || (x == u && y <= v)
IB015 Neimperativní programování – 07 str. 18/47
Přenos vlastností typu na složený typ
Pozorování
Instanciací lze přenést vlastnosti typu na složené typy.
Příklad
Rozšíření uspořadatelnosti hodnot typu na uspořadatelnost
seznamů hodnot daného typu.
instance (Ord a) => Ord [a] where
[] <= _ = True
(_:_) <= [] = False
(x:s) <= (y:t) = x < y || (x == y && s <= t)
IB015 Neimperativní programování – 07 str. 19/47
Obecná definice typové třídy a deklarace instance
Definice typové třídy
class (C1 a, . . . , Ck a) => C a





where op1 :: typ1...opn :: typn
default1...defaultm






Deklarace instance
instance (C1 a1, . . . , Ck ak) => C typ
where valdef1...valdefn
IB015 Neimperativní programování – 07 str. 20/47
Přetížení
Přetížení
Má-li třída více než jednu instanci, jsou její funkce přetíženy.
Přetížení operací
Jedna operace je pro několik různých typů operandů
definována obecně různým způsobem.
To, která definice operace se použije při výpočtu, závisí na
typu operandů, se kterými operace pracuje.
Srovnej s parametricky polymorfními operacemi, které jsou
definovány jednotně pro všechny typy operandů.
IB015 Neimperativní programování – 07 str. 21/47
Příklad přetížení operace
Typová třída Num
class (Eq a, Show a) => Num a where
(+), (-), (*) :: a -> a -> a
negate, abs, signum :: a -> a
Přetížení operací při deklaraci instancí
instance Num Int where
(+) = primPlusInt
...
instance Num Integer where
(+) = primPlusInteger
...
instance Num Float where
(+) = primPlusFloat
...
IB015 Neimperativní programování – 07 str. 22/47
Implicitní deklarace instance
Implicitní deklarace instance
V Haskellu lze deklarovat datový typ jako instanci typové třídy
(nebo více typových tříd) též implicitně, pomocí klausule
deriving v definici datového typu.
Při implicitní deklaraci instance se požadované funkce definují
automaticky podle způsobu zápisu hodnot definovaného typu
Funkce (==) se při implicitní deklaraci instance realizuje jako
syntaktická rovnost.
Příklad
data Nat = Zero | Succ Nat
deriving (Eq, Show)
IB015 Neimperativní programování – 07 str. 23/47
Hierarchie základních typových tříd
Eq
Ord
NumEnum Show
Read
Real
Integral
Fractional
Floating
IB015 Neimperativní programování – 07 str. 24/47
Definice typové třídy – příklad
Definice typové třídy
class Boolable a where getBool :: a -> Bool
Instanciace
instance Boolable Bool where
getBool x = x
instance Boolable Int where
getBool 0 = False
getBool _ = True
Použití
myIf :: Boolable a => a -> b -> b -> b
myIf x t f = if getBool x then t else f
myIf (3-3) “Pravda” “Nepravda” ∗ “Nepravda”
myIf (3-4) “Pravda” “Nepravda” ∗ “Pravda”
IB015 Neimperativní programování – 07 str. 25/47
Sekce
Časová složitost
IB015 Neimperativní programování – 07 str. 26/47
Časová složitost algoritmu
Podstata
Časová složitost funkce popisuje délku výpočtu v nejhorším
případě vzhledem k velikosti vstupních parametrů.
Délka výpočtu v nejhorším případě
Maximální počet redukčních kroků přes všechny možné
výpočty aplikace programu na vstupní parametry stejné
velikosti.
IB015 Neimperativní programování – 07 str. 27/47
Časová složitost algoritmu
Podstata
Časová složitost funkce popisuje délku výpočtu v nejhorším
případě vzhledem k velikosti vstupních parametrů.
Délka výpočtu v nejhorším případě
Maximální počet redukčních kroků přes všechny možné
výpočty aplikace programu na vstupní parametry stejné
velikosti.
Času je málo!
IB015 Neimperativní programování – 07 str. 27/47
Funkce pro reverzi seznamu
Reverze seznamu funkce reverse’
reverse’ :: [a] -> [a]
reverse’ [] = []
reverse’ (x:s) = reverse’ s ++ [x]
(++) :: [a] -> [a] -> [a]
[] ++ t = t
(x:s) ++ t = x : (s++t)
Reverze seznamu funkce reverse
reverse :: [a] -> [a]
reverse = rev []
where rev s [] = s
rev s (x:t) = rev (x:s) t
IB015 Neimperativní programování – 07 str. 28/47
Reverze seznamu funkcí reverse’
reverse’ :: [a] -> [a]
reverse’ [] = []
reverse’ (x:s) = reverse’ s ++ [x]
(++) :: [a] -> [a] -> [a]
[] ++ t = t
(x:s) ++ t = x : (s++t)
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1]) ≡ [3,2,1]
IB015 Neimperativní programování – 07 str. 29/47
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 30/47
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 30/47
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1 + 2
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 30/47
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1 + 2 + 3 + ... + n
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 30/47
Reverze seznamu funkcí reverse’
Délka výpočtu funkce při aplikaci na seznam délky n.
n+1 + 1 + 2 + 3 + ... + n
reverse’ [1,2,3]
reverse’ [2,3] ++ [1]
(reverse’ [3] ++ [2]) ++ [1]
((reverse’ [] ++ [3]) ++ [2]) ++ [1]
(([] ++ [3]) ++ [2]) ++ [1]
([3] ++ [2]) ++ [1]
(3 : ([] ++ [2])) ++ [1]
(3 : [2]) ++ [1]
3 : ([2] ++ [1])
3 : (2 : ([] ++ [1]))
3 : (2 : [1])
IB015 Neimperativní programování – 07 str. 30/47
Reverze seznamu funkcí reverse
reverse :: [a] -> [a]
reverse = rev []
where rev s [] = s
rev s (x:t) = rev (x:s) t
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 31/47
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 32/47
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1 + n
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 32/47
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1 + n + 1
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 32/47
Reverze seznamu funkcí reverse
Délka výpočtu funkce při aplikaci na seznam délky n.
1 + n + 1
reverse [1,2,3]
rev [] [1,2,3]
rev [1] [2,3]
rev [2,1] [3]
rev [3,2,1] []
[3,2,1]
IB015 Neimperativní programování – 07 str. 32/47
Asymptotický růst funkcí
Pozorování
Při určování časové složitosti algoritmů je nepraktické a často
i obtížné určovat tuto složitost přesně.
Funkce vyjadřující délku výpočtu vzhledem k velikosti
parametru klasifikujeme podle asymptotického chování.
Asymptotický růst funkcí
Při zápisu funkční hodnoty v proměnné n rozhoduje
nejrychleji rostoucí člen. U něj navíc zanedbáváme kladnou
multiplikativní konstantu.
Podle toho hovoříme o funkcích lineárních, kvadratických,
exponenciálních apod.
IB015 Neimperativní programování – 07 str. 33/47
Přehled asymptotických funkcí
t(n) růst funkce t
1, 20, 729, 264
konstantní
2 log n + 5, 3 log2 n + log2(log2 n) logaritmický
n, 2n + 1, n +
√
n lineární
n log n, 3n log n + 6n + 9 n log n
n2
, 3n2
+ 4n − 1, n2
+ 10 log n kvadratický
polynomiální
n3
, n3
+ 3n2
kubický
2n
1+
√
5
2
n
exponenciální
3n
IB015 Neimperativní programování – 07 str. 34/47
Asymptotická složitost reverse a reverse‘
reverse‘
Počet redukčních kroků výrazu reverse’ [x1,. . .,xn] na
každém seznamu délky n je
n + 1 + 1 + 2 + 3 + · · · + n =
n2 + 3n + 2
2
Složitost funkce reverse’ je kvadratická vzhledem k délce
obraceného seznamu.
reverse
Počet redukčních kroků výrazu reverse [x1,. . .,xn] na každém
seznamu délky n je
1 + n + 1 = n + 2
Složitost funkce reverse je lineární vzhledem k délce
obraceného seznamu.
IB015 Neimperativní programování – 07 str. 35/47
Časová složitost algoritmu a problému
Časová složitost algoritmu
Posuzuje konkrétní algoritmus.
Nevypovídá a jiných algoritmech pro řešení téhož problému.
Časová složitost problému
Daný problém je možné řešit různými algoritmy.
Složitost problému vypovídá a časové složitosti nejlepšího
možného algoritmu pro řešení problému.
Určovat složitost problému je výrazně obtížnější, než určování
složitosti algoritmu.
Bez znalosti složitosti problému nelze určit, zda daný
algoritmus pro řešení problému je optimální.
IB015 Neimperativní programování – 07 str. 36/47
Nejhorší případ 1/2
Pozor
Časová složitost popisuje délku výpočtu v nejhorším případě
pro danou velikost argumentu.
Příklad
Vyšetřujeme časovou složitost funkce ins vzhledem k jejímu
druhému parametru.
Funkce ins zařazuje prvek do seřazeného seznamu.
ins :: Int -> [Int] -> [Int]
ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t else y : ins x t
IB015 Neimperativní programování – 07 str. 37/47
Nejhorší případ 2/2
Různé délky výpočtu
Počet kroků při volání ins x [x1, ..., xn] je různý.
Nejkratší výpočet má délku 3:
ins 1 [2,4,6,8] 3
[1,2,4,6,8]
Nejdelší výpočet má délku 3n + 1:
ins 9 [2,4,6,8] 3∗4+1
[2,4,6,8,9]
Časová složitost
Časová složitost funkce ins je lineární vzhledem k velikosti
jejího druhého argumentu (tj. vzhledem k délce seznamu).
IB015 Neimperativní programování – 07 str. 38/47
Časová složitost a redukční strategie
Pozorování
Časová složitost závisí nejen na algoritmu (způsobu definování
funkce), ale také na redukční strategii.
Příklad
Uvažme funkcí pro uspořádání prvků v seznamu pomocí
postupného zařazování.
inssort :: Ord a => [a] -> [a]
inssort = foldr ins []
where ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t
else y : ins x t
Princip řazení funkcí inssort
inssort [x1, x2, ..., xn−1, xn]
foldr ins [] [x1, x2, ..., xn−1, xn]
n+1
ins x1 (ins x2 (...(ins xn−1 (ins xn []))...))
IB015 Neimperativní programování – 07 str. 39/47
Příklad závislosti časové složitosti na redukční strategii
Definice funkce
inssort :: Ord a => [a] -> [a]
inssort = foldr ins []
where ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t
else y : ins x t
minim = head . inssort
Striktní vyhodnocování (nejhorší případ – seznam je klesající)
minim [x1, ..., xn]
(head.inssort) [x1,...,xn]
head (inssort [x1,...,xn])
head (foldr ins [] [x1,...,xn])
n+1 head (ins x1 (...(ins xn−2 (ins xn−1 (ins xn[])))...))
3·0+1 head (ins x1 (...(ins xn−2 (ins xn−1 [xn]))...))
3·1+1 head (ins x1 (...(ins xn−2 [xn,xn−1])...) )
3·2+1 head (ins x1 (...[xn,xn−1,xn−2]...) )
...
3·(n−2)+1 head (ins x1 [xn,...,x2] )
3·(n−1)+1 head [xn,...,x1]
xn
IB015 Neimperativní programování – 07 str. 40/47
Příklad závislosti časové složitosti na redukční strategii
Definice funkce
inssort :: Ord a => [a] -> [a]
inssort = foldr ins []
where ins x [] = [x]
ins x (y:t) = if x <= y then x : y : t
else y : ins x t
minim = head . inssort
Líné vyhodnocování (nejhorší případ – nejmenší prvek na konci)
minim [x1,...,xn]
(head.inssort) [x1,...,xn]
head (inssort [x1,...,xn])
head (foldr ins [] [x1,...,xn])
n+1 head (ins x1 (...(ins xn−2 (ins xn−1 (ins xn [])))...) )
head (ins x1 (...(ins xn−2 (ins xn−1 (xn : [])))...) )
3 head (ins x1 (...(ins xn−2 (xn : (ins xn−1 [])))...) )
3 head (ins x1 (...(xn : (ins xn−2 (ins xn−1 [])))...) )
...
3 head (ins x1 (xn :(ins x2 (ins x3 (...(ins xn−1 [])...)))))
3 head ( xn : (ins x1 (ins x2 (... (ins xn−1 [])...))))
xn
IB015 Neimperativní programování – 07 str. 41/47
Příklad závislosti časové složitosti na redukční strategii
Striktní vyhodnocování
Počet redukčních kroků výrazu minim [x1,...,xn] je:
3 + n + 1 +
n−1
k=0
(3k + 1) + 1 =
3n2 + n + 10
2
Při striktním vyhodnocování má funkce kvadratickou časovou
složitost.
Líné vyhodnocování
Počet redukčních kroků výrazu minim [x1,...,xn] je:
3 + n + 1 + 1 + 3.(n − 1) + 1 = 4n + 3
Při líném vyhodnocování má funkce lineární časovou složitost.
IB015 Neimperativní programování – 07 str. 42/47
Vliv redukční strategie na časovou složitost
Pozorování
Není pravda, že časová složitost výpočtu se při líném a
striktním vyhodnocování vždy liší.
Pokud se časová složitost liší, může se lišit víc než o jeden
řádek ve zmiňované tabulce asymptotických růstů funkcí.
Příklady
Konstantní (líně) versus exponenciální (striktně):
f n = const n (fib’ n)
Lineární líně i striktně:
length [a1,...,an]
IB015 Neimperativní programování – 07 str. 43/47
Akumulátor
IB015 Neimperativní programování – 07 str. 44/47
Akumulátor a rekurze
Obecný princip
Vícenásobné nebo nevhodné použití rekurzivního volání v těle
rekurzivně definované funkce, může v obecné rovině vést na
časově neoptimální algoritmus.
Opakovanému rekurzivnímu volání pro tutéž hodnotu lze
zabránit uchováváním mezivýsledků rekurzivního volání.
Uchování výsledků se provádí přidáním parametru rekurzivní
funkce, tzv. akumulátoru.
Pozorování
Přímé použití rekurzivní funkce má tendenci být čitelnější.
IB015 Neimperativní programování – 07 str. 45/47
Výpočet Fibonacciho číselné řady
Definice funkcí
fib’ :: Integer -> Integer
fib’ 0 = 0
fib’ 1 = 1
fib’ n = fib’ (n-2) + fib’ (n-1)
fib :: Integer -> Integer
fib = f 0 1
where f a _ 0 = a
f a b k = f b (a+b) (k-1)
Složitost vzhledem k argumentu
Složitost funkce fib’ je exponenciální.
Složitost funkce fib je lineární.
IB015 Neimperativní programování – 07 str. 46/47
Checkpoint
Analyzujte časovou složitost
funkce map , vzhledem k délce seznamu.
funkce es (Eratosthenovo síto) vzhledem k délce seznamu.
Lineární vs. kvadratická
Vytvořte libovolnou funkci f1::a->[a] , která má
kvadratickou složitost.
Vytvořte libovolnou funkci f2::a->[a] , která má lineární
složitost.
Použijte obě funkce v kontextu funkce map na dlouhých
seznamech a pozorujte rozdíl.
IB015 Neimperativní programování – 07 str. 47/47