23 - Haskell - lazy evaluation
středa 27. dubna 2016
15:44
Haskell - lazy evaluation (typy v jazyce včetně akcí, význam typových tříd, demonstrace lazy evaluation).
Funkcionální jazyk, který je case-sensitive. Ke všemu má ještě speciální pravidla pro první znaky literálů. Je nutné dodržovat při psaní programu tato pravidla:
Jména typů, typových tříd a datové konstruktory musejí mít velké počáteční písmeno.
Datové typy
Primitivní typy
Int - celá čísla (-2147483648 … 2147483647)
Word - celá čísla bez znaménka (45, 890)
Integer - celá čísla bez omezení rozsahu (není tak efektivní jako Int)
Char - znaky ('a', 'X')
Bool - reprezentace logických hodnot (True, False) ... jedná se o datové konstruktory, proto mají hodnoty velké počáteční písmeno
Float - desetinná čísla (3.141, 234.8), single precision
Double - double precision
Strukturované typy
Seznam - homogenní datová struktura, která nemá obecně žádné omezení rozměru. Konstruktorem je ":" a "[]". Kdy dvojtečka připojuje prvky do seznamu a závorky značí prázdný seznam. Zápis 1:2:3:[] je tedy konstrukce seznamu o třech prvcích. Alternativním a přirozenějším zápisem je [1,2,3]. Toto však není zcela čistý zápis v jazyce Haskell, ale překladač si ji interně přeloží na dříve zmíněnou sekvenci.
N-tice - heterogení datová struktura. Jejím konstruktorem je "," ve spojení s párem kulatých závorek. Například dvojice celých čísel (1,2)
Akce
Operace/typy se side effecty se nazývají akce. Vyznačují se tím, že jejich výsledek nezáleží pouze na jejich parametrech (jako je to u normální typů v haskellu), ale i na dalších faktorech. Takže tyto operace nejsou immutable.
Patří sem typicky IO operace (např. práce se soubory). 
Typy:
IO () - základní IO akce, bez specifikovaného konkrétnějšího návratového typu (pokud funkce nevrací žádnou zajímavou hodnotu - obdoba void v jiných jazycích)
IO Int  - provede IO operaci a vrátí integer
IO String, IO Char....
Akce se propojují pomocí operátoru >>= (nazývaný bind). Jelikož ale jeho použití není úplně příjemné, tak se používá synktaktický cukřík:
do umožňuje řadit příkazy za sebe (jako v procedurálních jazycích)
<- umožňuje navázat na proměnnou výsledek nějaké operace
Příklad:
Funkce return umí zabalit datový typ do IO operace (vytvořit z normálního typu akci) . Umožňuje vrátit výsledek ze sekvence akcí.
return :: a -> IO a
Nezapomenout, že data jsou v Haskellu by default immutable. Stav můžeme udržovat například pomocí Monád nebo Data.IORef.
[link]
K tomu se také váže problém, že přidávat data na konec listu je silně neefektivní.
Haskell je silně typovaný jazyk. Změna jednoho typu na druhý je možná pouze zavoláním převodní funkce a každá entita má přesně daný svůj typ. Pro popis typu vstupu a výstupu funkce se používá zápis (příklad konstruktoru seznamu):
(:) :: Int -> [Int] -> [Int]
Tento zápis říká asi toto: Funkce se jménem (:) jako jeden vstup bere celé číslo. Druhý vstupní parametr je seznam celých čísel. Poslední část potom říká, že výstupem bude zase seznam celých čísel. Jelikož se jedná o jazyk silně typovaný, tak aby pro každý vstup nemuselo existovat několik definicí stejného operátoru, tak se zavádějí typové proměnné. Ty nahrazují skutečné typy a při vyhodnocení jsou nahrazeny skutečnými typy. Zápis vypadá následovně:
(:) :: a -> [a] -> [a]
Za symbol a se potom na všechna místa potom přiřadí právě typ Int nebo třeba Float. Tento princip právě umožňuje vytváření seznamů jakéhokoliv typu.
Typová třída
Je druh rozhraní
typ, který je součástí typové třídy implementuje definované chování
Typ a je instancí třídy C, je-li pro něj definována vymezená množina operací
Interně je pro každou typovou třídu slovník, který pro jednotlivé datové typy ukazuje na funkce, které implementují operace požadované tou typovou třídou.
=> značí typové omezení (např. (==) :: (Eq a) => a -> a -> Bool)
Například typ pro funkci elem je: "elem :: (Eq a) => a -> [a] -> Bool"
např.:
Eq - typová třída pro testování rovnosti
Ord - typová třída podporující porovnávání
Show - instance této třídy může být převedena do řetězce (funkce show)
Instance typové třídy (přidání datového typu Int do třídy Eq - definicice operace požadované třídou (operace porovnání))
 instance Eq Int where
     x==y = intEq x y
            // metoda (definice operace)
Instance typové třídy (přidání datového typu který staví nad existujícím typem (tady seznam) do třídy Eq - definicice operace požadované třídou (operace porovnání))
instance (Eq a) => Eq [a] where
      []==[] = True
      (x:xs)==(y:ys) = x==y && xs==ys
       _==_ = False
Funkce
Funkce f má pro jeden vstupní parametr definován typ jako f :: a -> b. Tento zápis lze předefinovat a říci buď přesný typ a nebo které typy musejí být stejné, a tak podobně.
Funkce součtu dvou prvků a druhé mocniny vypadá následovně:
 add x y = x + y
 square x = x * x
Práci se seznamem jako parametrem ukazuje funkce, která počítá délku seznamu:
 length [] = 0
 length (x:xs) = 1 + length xs
Vyhodnocení funkcí probíhá od shora dolů, proto funkce, které popisují nadmnožinu ostatních případů, musejí být uvedeny jako poslední. První funkce se ztotožní s prázdným seznamem a vrací nulu. Když ne vstupu není prázdný seznam, tak se přistoupí ke druhé funkci. Tam se vzor chápe jako seznam, který má na začátku prvek zastoupený parametrem x a zbytek seznamu označený xs. Funkce potom rekurzivně přičte jedničku k délce zbytku seznamu.
Pojmenování části vzoru
Při spojování dvou seznamů nás nezajímá pouze hlavička a zbytek seznamu. Je potřeba pracovat s jedním parametrem jako celkem, proto si ho můžeme pojmenovat(viz jména l1 a l2).
 merge [] l2 = l2
 merge l1 [] = l1
 merge l1@(x:xs) l2@(y:ys) =
   if x<y then x:merge xs l2 else y:merge l1 ys
Anonymní proměnné
Funkce vrací hlavičku seznamu. Zbytek nás nezajímá, proto je pouze naznačeno, že by tam mělo něco být, ale nemá to konkrétní název.
 hd (x:_) = x
Jsou definované za klíčovým slovem where. Je důležité dodržovat odsazení tak jak je vidět. where je odsazeno od definice funkce a lokální definice by měly být odsazeny v něm.
 sumsqr x y = xx + yy
   where
     sqr a b = a*b
     xx = sqr x x
     yy = sqr y y
Jinou možností zápisu lokálních funkcí je využití konstrukce let in.
 sumsqr x y =
   let
     sqr a b = a*b
     xx = sqr x x
     yy = sqr y y
   in
     xx + yy
It is important to know that let ... in ... is an expression, that is, it can be written wherever expressions are allowed. In contrast, where is bound to a surrounding syntactic construct, like the pattern matching line of a function definition.
[link]
First, you must realise that Haskell uses a thing called a thunk for its values. A thunk is basically a value that has not yet been computed yet -- think of it as a function of 0 arguments. Whenever Haskell wants to, it can evaluate (or partly-evaluate) the thunk, turning it in to a real value. If it only partly evaluates a thunk, then the resulting value will have more thunks in it.
For example, consider the expression:
(2 + 3, 4)
In an ordinary language, this value would be stored in memory as (5, 4), but in Haskell, it is stored as (<thunk 2 + 3>, 4). If you ask for the second element of that tuple, it will tell you "4", without ever adding 2 and 3 together. Only if you ask for the first element of that tuple will it evaluate the thunk, and realise that it is 5.
Tato strategie vyhodnocení uvádí do absolutní perfekce strategii vyhodnocení označovanou, vyhodnocení v případě potřeby (call-by-need). Tento přístup vyhodnocuje určitý výraz pouze jednou a pouze tehdy, je-li potřeba. Hodnota výrazu taky zůstává zachována pro pozdější použití.
Příkladem, na kterém se nejčastěji ukazuje tato vlastnost Haskellu, je definice nekonečného seznamu :
 [1..]
Pokud by nebyl Haskell jazyk s líným vyhodnocením, tak kdekoliv by se tato konstrukce vyskytnula, tak by začal generovat pole, dokud by nedošla paměť a program neskončil chybou. Pokud ale máme správně napsaný program v Haskellu, tak není problém s takovýmto polem pracovat. V standardní knihovně existuje funkce take, která jako první parametr bere číslo n a druhý pole. Výsledkem je prvních n prvků pole. Vysledek použití je vidět za
 take 5 [1..] => [1,2,3,4,5]
 take 10 [-1,-3..] => [-1,-3,-5,-7,-9,-11,-13,-15,-17,-19]
Výsledek líného vyhodnocení může být použit přes výpočtovou sekvenci celé funkce.
Využití lazzy evaluation pro efektivní vyhodnocení fibonnaciho řady se složitostí O(n)
je to oblíbený příklad lazy evalution v Haskellu, dával ho i přímo Kolář na státnicích (zkuste si to vymyslet v těch nervech bez přípravy...)
podrobnější popis viz. [link])
Naivní implementace:
 fib :: Int -> Integer
 fib 0 = 0
 fib 1 = 1
 fib n = fib (n-1) + fib (n-2)
S pomocí nekonečného listu a lazy evalution:
[link]
 fib :: Int -> Integer
 fib n = fibs !! n   -- Vrat n-ty prvek z pole fibs
   where
     fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
V zásadě to je celkem jednoduché: "současná hodnota FIB je hodnota z původního FIB seznamu (i-1)+hodnota ve FIB seznamu, který je o jedno posunutý (tail FIB, tj. i-2)"
Rekurze
Zpětná rekurze - Pokud po návratu z rekurzivního volání probíhá ještě nějaký výpočet. f(x) = e(f(x))
Dopředná rekurze - Pokud rekurzivní volání je poslední část výpočtu. f(x) = f(e(x))
Lineární rekurze - Ve výpočtu rekurze je právě jedno rekurzivní volání funkce. Tento typ rekurze lze převést na cyklus.
Koncová rekurze - Dopředně lineární rekurze. Každou takovouto funkci lze převést na efektivní cyklus! Není potřeba uchovávat stav nedokončených výpočtů.
Notes
2. Otazka (předmět) (okruh): 23. Haskell – lazy evaluation
Kdo me primarne zkousel: Kolář
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Na papírku bylo specifikováno, ať se zaměřím pouze na lazy evaluation a ať řeknu, co to je, jaký to má v haskellu význam a předvedu nějakou typickou konstrukci, která se používá. Tak jsem řekl, že haskell je funkcionální jazyk, řekl jsem o tom lazy evaluation a nakonec jsem napsal výpočet fibonacciho posloupnosti pomocí nekonečného seznamu. Některé věci jsem opět pletl, ale spíš drobnosti stylu, že jsem řekl, že při lazy evaluation se vyhodnocuje právě jednou, ale je to maximálně jednou. V té chvíli mi to nedošlo. Nakonec se ještě kolář ptal na to, co je to když napíšeme konstrukci where a dole si dospecifikujeme nějakou fci. Hodnocení - C. Kdybych věděl, jak se jmenuje ta konstrukce where, tak jsem měl B. :/
From <[link]> 
1. Otazka (okruh): 28. Haskell – lazy evaluation (typy v jazyce, demonstrace lazy evaluation)
Kdo me primarne zkousel: Kolář
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Povykládal jsem o datových typech a lazy evaluation nějakou teorii, ale pak po mně chtěl zapsat v Haskellu nekonečný seznam s Fibonacciho posloupností a ukázat dva výrazy, jeden který skončí pádem s nedostatkem paměti a druhý, který projde. Tak to ze mně teda doloval, co jsem měl v podvědomí ještě z minulého roku.
From <[link]> 