27 - Haskell - lazy evaluation (typy v jazyce včetně akcí, význam typových tříd, demonstrace lazy evaluation) Flashcards
Co je to haskell
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.
• Ostatní literály musejí mít písmeno malé.
• Silně typovaný
• Neexistuje sekvence (všechno je funkce)
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:[], alternativní zápis [1,2,3] (překladačem přeložet na ten první)
• 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)
Vlastní datové struktury ○ Jednoduché ○ Komplexní § ● Výčtové □ ○ data Color = Red | Green | Blue § ● Rozšířené □ ○ data Color’ = Red | Green | Blue | Grayscale Int § ● Parametrické □ ○ dataRGBColora=RGBcaaa □ data CMYColor a = CMYc a a a □ data Color a = RGB (RGBColor a) ® | CMY (CMYColor a) ® | Grayscale a § ● Rekurzviní □ ○ data Stack a = Top a (Stack a) ® | Bottom
Haskell typování
Nezapomenout, že data jsou v Haskellu by default immutable (neměnné). Stav můžeme udržovat například pomocí Monád nebo Data.IORef.
• 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] (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.)
Typové proměnné 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.
Haskell typové třídy
• 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í
=> značí typové omezení (např. (==) :: (Eq a) => a -> a -> Bool) • Například typ pro funkci elem je: "elem :: (Eq a) => a -> [a] -> Bool" (vyžadujeme, aby a bylo třídy Eq) • 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)
Příklady:
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 - definice operace požadované třídou (operace porovnání)) instance (Eq a) => Eq [a] where []==[] = True (x:xs)==(y:ys) = x==y && xs==ys _==_ = False
Definování vlastní typové třídy Typová třída Shape musí mít povinně operaci area (obsah útvaru). Instancí typové třídy je MyShape, což může být kruh nebo obdelník: class Shape s where area :: s -> Float data MyShape = Circle Float | Rectangle Float Float instance Shape MyShape where area (Circle r) = 3.145 * r area (Rectangle a b) = a * b
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 :: [a] -> Int
length [] = 0
length (_: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
Lokální funkce
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.
Haskell akce
V imperativních jazycích jsou programy tvořeny akcemi. Na rozdíl od běžných funkcí u akcí záleží na pořadí vykonávání. Musejí být tedy v rámci monád - bloku do apod.
Akce je v haskellu funkce s výsledkem typu IO a (např. IO Integer) - odtud “typy v jazyce včetně akcí”
● Haskell je funkcionalni , nema sekvenci
● Pro I/O se používají akce
● Tyto “funkce” = AKCE mají vlastní typ IO Integer , IO String etc = funkce v haskelu s výsledkem typu IO
● Např putStrLn
putStrLn::String->IO()
PutStrLn takes an argument, but it is not an action. It is a function that takes one argument (a string) and returns an action of type IO ().
● Možno dávat do “do” blocku a spojovat více akcí do jedné - pouzivej pouze pro IO
○ main ::IO() main =do
putStrLn”hello”
putStrLn”world”
Líné vyhodnocení
= 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í.
= call-by-need vyhodnocení
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í lazy evaluation pro efektivní vyhodnocení fibonnaciho řady se složitostí O(n)
Naivní implementace: fib :: Int -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)
fib :: Int -> Integer
fib n = fibs !! n – Vrat n-ty prvek z pole fibs
where
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
(Input: zipWith (+) [1,2,3] [3,2,1] Output: [4,4,4])
Thunk
First, you must realize 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 into 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 realize that it is 5.
Rekurze
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.
- volá sama sebe pouze jednou
• 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ů.
- posledním příkazem funkce je rekurzivní zavolání sebe sama
