Akumulační funkce

• Seznam je posloupnost oddělených prvků.
• Cíl = spojit jednotlivé prvky dohromady, akumulovat
• Akumulace se aplikuje pomocí binárního operátoru postupně
• foldl1 = aplikace se děje zleva
• foldr1 = aplikace se děje zprava (nejdřív předposlední a poslední prvek); ale ne obráceným směrem
• Funkce nejsou definované pro prázdný seznam.
• Na jednoprvkových seznamech je to identita s kontrolou typu.

foldl1 (-) [2,3,2] --> -3
foldr1 (-) [2,3,2] --> 1

foldl, foldr

• V případě, že akumulační funkce mají fungovat na prázdných seznamech potřebují iniciální hodnotu.

foldl (-) 0 [2,3,2] --> -7
foldr (-) 0 [2,3,2] --> 1 (2-0, 3-2, 2-1)

• Výsledek může být opět seznam! Vstupní prvek nemusí být stejného typu jako seznam.

foldr (:) [] "Coze?" --> "Coze?"
foldr (\x y->(x+1):y) [100] [1,2,3] --> [2,3,4,100]

• katamorfismus = nahrazení hodnotové konstruktory ve struktuře za f a z (list a foldr)
  • Výraz vzniklý nahrazením hodnotových konstruktorů v nějaké hodnotě algebraického typu jinými funkcemi vhodné arity.

Typové třídy

• monomorfní typy = nevystupují typové proměnné, např. no
• polymorfní typy = jsou zde typové proměnné, které nejsou nijak omezené, např. length,flip
• kvalifikované typy = typové proměnné jsou omezené, můžeme použít jsou-li omezené nějakou typovou třídou, :: Eq a => a -> a
• sdružují a identifikují typy se společnými vlastnostmi.
• typová kvalifikace - Ord,Nat,Eq,Show,Foldable, …

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 -- Hardwarove implementace jak porovnavat Int

instance (Eq a, Eq b) => Eq (a,b) where
  (x,y) == (u,v) = x == u && y == v

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

Přenos vlastností typu na složený typ

• instanciací lze přenést vlastnosti typu na složené typy.
• 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)

Přetížení

• Má-li třída více než jednu instanci, jsou její funkce přetíženy.
• 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.

Implicitní deklarace instance

• Datový typ lze deklarovat jako instanci typové třídy též implicitně, pomocí deriving v def. datového typu.
• Instance se definují automaticky podle způsobu zápisu hodnot definovaného typu.
• Funkce (==) se při implicitní deklaraci instance realizuje jako syntaktická rovnost.

data Nat = Zero | Succ Nat
  deriving (Eq, Show)

Časová složitost

• Časová složitost funkce popisuje délku výpočtu v nejhorším případě vzhledem k velikosti vstupních parametrů.
• Maximální počet redukčních kroků přes všechny možné výpočty aplikace programu na vstupní parametry stejné velikosti.

Asymptotický růst funkcí

• Nezajímají nás konstanty: +1, +2, …
• Funkce vyjadřující délku výpočtu vzhledem k velikosti parametru klasifikujeme podle asymptotického chování.
• 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.

Časová složitost algoritmu

• Posuzuje konkrétní algoritmus.
• Nevypovídá o 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á o č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í.

A redukční strategie

• Časová složitost závisí nejen na algoritmu (způsobu definování funkce), ale také na redukční strategii.
• 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í.
• Konstatní (líně) versus exponenciální (striktně): f n = const n (fib' n)
• Lineární líně i striktně: length [a1, ..., an]

Akumulátor

• 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átor.
• (Přímé použití rekurzivního funkce má tendenci být čitelnější.)

-- Exponenciální složitost
fib' :: Integer -> Integer
fib' 0 = 0
fib' 1 = 1
fib' n = fib' (n-2) + fib' (n-1)

-- Lineární složitost
fib :: Integer -> Integer
fib = f 0 1
    where f a _ 0 = a
          f a b k = f b (a+b) (k-1)