27 - Haskell - lazy evaluation (typy v jazyce včetně akcí, význam typových tříd, demonstrace lazy evaluation) Flashcards

1
Q

Co je to haskell

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Datové typy

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Haskell typování

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Haskell typové třídy

A

• 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Funkce

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Haskell akce

A

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”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Líné vyhodnocení

A

= 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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Rekurze

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly