Scopul acestui laborator este a de familiariza studenții cu limbajul Haskell.
Haskell este un limbaj de programare pur-funcțional. În limbajele imperative, programele sunt secvențe de instrucțiuni pe care calculatorul le execută ținând cont de stare, care se poate modifica în execuție. În limbajele funcționale nu există o stare, iar funcțiile nu au efecte secundare (e.g. nu pot modifica o variabilă globală), garantând că rezultatul depinde doar de argumentele date: aceeași funcție apelată de două ori cu aceleași argumente, întoarce același rezultat. Astfel, demonstrarea corectitudinii unui program este mai facilă.
Pentru început, avem nevoie de un mod de a compila cod. Puteți descărca platforma Haskell de aici (Windows/OS X/Linux) sau puteți instala pachetul “ghc”.
Vom lucra în modul interactiv, care ne permite să apelăm funcții din consolă și să vedem rezultatul lor. Putem să încărcăm și fișiere cu fragmente de cod din care să apelăm funcții definite de noi.
Pentru modul interactiv, rulați “ghci”. Ar trebui să vedeți ceva asemănător:
GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help Prelude>
| Comenzi folositoare în ghci: | |
|---|---|
| Comandă | Efect |
| :l filename | încarcă un fișier din directorul din care e rulat ghci |
| :r | reîncarcă ultimului fișier încărcat |
| :t expresie | afișează tipul expresiei |
| :? | afișează meniul de help cu comenzile disponibile |
| :q | închide ghci |
Haskell este un limbaj tipat static (statically typed) care poate face type inference. Asta înseamnă că tipul tuturor expresiilor este cunoscut la compilare; dacă nu este explicit, compilatorul îl deduce. Deasemenea, Haskell este tare tipat (strongly typed), ceea ce înseamnă că trebuie să existe conversii implicite între diferite tipuri de date.
Haskell are tipuri asemănătoare celor din alte limbaje studiate până acum, ca C, Java etc: Int, Integer (întregi de dimensiune arbitrară), Float, Double, Char (cu apostrofuri, e.g. 'a'), Bool.
Prelude> :t 'a' 'a' :: Char Prelude> :t True True :: Bool Prelude> :t 0 == 1 0 == 1 :: Bool Prelude> :t 42 42 :: Num a => a
Tipul lui 42 nu pare să fie ceva intuitiv, ca Int. Deocamdată e suficient să menționăm faptul că, în Haskell, constantele numerice pot să se comporte ca diferite tipuri, în funcție de context. 42 poate să fie considerat întreg, în expresii ca 42 + 1, sau numărul în virgulă mobilă 42.0 în expresii ca 42 * 3.14.
Listele sunt structuri de date omogene (i.e. pot conține doar elemente de același tip). O listă este delimitată de paranteze pătrate, cu elementele sale separate prin virgulă:
[1, 2, 3, 4]
Lista vidă este [].
Tipul unei liste este dat de tipul elementelor sale; o listă de întregi are tipul [Int]. Putem avea liste de liste de liste de liste … atâta timp cât respectăm condiția de a avea același tip.
[['H', 'a'], ['s'], ['k', 'e', 'l', 'l']] -- corect, are tipul [[Char]] [['N', 'u'], [True, False], ['a', 's', 'a']] -- greșit, conține și elemente de tipul [Bool] și de tipul [Char]
String care este un alias peste [Char].“String” este doar un mod mai lizibil de a scrie['S', 't', 'r', 'i', 'n', 'g'], care, la rândul său, este un mod mai lizibil de a scrie'S':'t':'r':'i':'n':'g':[]
Tuplurile sunt structuri de date eterogene (i.e. pot conține elemente de diferite tipuri). Un tuplu este delimitat de paranteze rotunde, cu elementele sale separate prin virgulă:
(1, 'a', True)
Tipul unui tuplu este dat de numărul, ordinea și tipul elementelor sale:
Prelude> :t (True, 'a')
(True, 'a') :: (Bool, Char)
Prelude> :t ('a', True)
('a', True) :: (Char, Bool)
Prelude> :t ("sir", True, False)
("sir", True, False) :: ([Char], Bool, Bool)
În Haskell, funcțiile pot fi prefixate sau infixate. Cele prefix sunt mai comune, au un nume format din caractere alfanumerice și sunt apelate prin numele lor și lista de argumente, toate separate prin spații (fără paranteze sau virgule):
<Prelude> max 1 2 2
Funcțiile infixate sunt cele cu nume formate din caractere speciale, de forma operand1 operator operand2
Prelude> 1 + 2 3
(). Astfel, următoarele expresii sunt echivalente:
3 * 23 (*) 3 23
Dacă o funcție are două argumente, putem să o infixăm cu operatorul `` (backticks - dacă nu aveți un layout exotic, ar trebui să fie pe tasta de dinainte de 1). Astfel, următoarele două expresii sunt echivalente:
mod 10 3 10 `mod` 3
Creați, în editorul de text preferat, un fișier cu extensia .hs în care vom defini prima funcție:
-- intoarce modulul dublului celui mai mare dintre cele doua argumente myFunc x y = abs (2 * max x y)
Puteți testa funcția din ghci:
Prelude> :l first.hs [1 of 1] Compiling Main ( first.hs, interpreted ) Ok, modules loaded: Main. *Main> myFunc 10 11 22 *Main> myFunc (-10) (-11) 20 *Main> myFunc 3.14 2.71 6.28
Prelude>let myFunc x y = abs (2 * max x y)
Observăm că funcția noastră merge și pentru numere întregi și pentru numere în virgulă mobilă. Am precizat mai devreme că orice expresie trebuie să aibă un tip, cunoscut la compilare. Cum noi nu am precizat tipul funcției noastre, compilatorul l-a dedus ca fiind:
Prelude> :t myFunc myFunc :: (Num a, Ord a) => a -> a -> a
Fără a intra în detalii, funcția noastră ia ca argumente două numere de același tip care pot fi ordonate și întoarce un rezultat de același tip. Metoda prin care se realizează această deducție va fi studiată în continuare la PP.
-- intoarce modulul dublului celui mai mare dintre cele doua argumente myFunc :: Int -> Int -> Int myFunc x y = abs (2 * max x y)
Observați că, acum, tipul arătat de :t este cel specificat și primiți o eroare dacă încercați să pasați ca argumente numere în virgulă mobilă.
Vom scrie acum o altă funcție prin care ne propunem să calculăm, în mod recursiv, suma tuturor elementelor dintr-o listă. Pentru o listă vidă aceasta este 0, altfel este capul listei plus suma celorlalte elemente.
{- - if este o expresie; cum toate expresiile - trebuie sa intoarca o valoare, ramura else - este necesara - - caracterul ' nu are nimic special si poate fi - folosit in numele unei functii. Il folosim - pentru ca exista o functie sum predefinita -} sum' l = if length l /= 0 then head l + sum' (tail l) else 0
Deși funcționează, implementarea de mai sus nu este foarte elegantă. Putem să ne folosim de pattern matching (ca la TDA-uri).
sum'' [] = 0 sum'' (x:xs) = x + sum'' xs
Dacă lista dată ca argument e vidă, atunci se face match pe primul pattern și rezultatul este 0. Altfel, se trece la pattern-ul următor; aici se fac două legări - capul listei este legat de numele x, iar restul de numele xs (parantezele din jurul x:xs sunt necesare) și este apelată funcția în mod recursiv.
Pentru a știi unde să întoarcă execuția după apelul unei funcții, un program ține adresele apelanților pe o stivă. Astfel, după ce execuția funcției se termină, programul se întoarce la apelant pentru a continua secvența de instrucțiuni.
În exemplul nostru, apelul sum'' [1, 2, 3, 4, 5] se va evalua în felul următor:
sum'' [1, 2, 3, 4, 5] 1 + sum'' [2, 3, 4, 5] 1 + (2 + sum'' [3, 4, 5]) 1 + (2 + (3 + sum'' [4, 5])) 1 + (2 + (3 + (4 + sum'' [5]))) 1 + (2 + (3 + (4 + (5 + sum'' [])))) 1 + (2 + (3 + (4 + (5 + 0)))) 15
Astfel, pentru a aduna capul listei la suma cozii, trebuie mai întâi calculată această sumă, iar apoi să se revină în funcția apelantă.
Putem folosi un acumulator transmis ca parametru la funcția apelată, eliminând nevoia de a mai ține pe stivă informați despre apelant.
Modul în care Haskell asigură tail-recursion o să fie mai clar când vom discuta despre modul de evaluare al funcțiilor. Tot atunci vom vedea și capcanele acestuia.
-- Folosim sintaxa "let ... in" pentru a ascunde functia -- auxiliara folosita si a pastra forma functiei sum (un singur -- argument) sum''' l = let sumAux [] acc = acc sumAux (x:xs) acc = sumAux xs (x + acc) in sumAux l 0
1. Scrieți o funcție cu care să determinați factorialul unui număr. Scrieți o implementare straight-forward, fără restricții, apoi încercați să o faceți tail-recursive.
2. Scrieți o funcție care primește un număr n și întoarce al n-lea număr din șirul lui Fibonacci (1, 1, 2, 3, 5… unde primul 1 are indexul 0). Scrieți o implementare straight-forward, fără restricții, apoi încercați să o faceți tail-recursive.
3. a) Scrieți o funcție cat care primește două liste de același tip și returnează concatenarea lor. Funcția ar trebui să funcționeze exact ca operatorul ++ deja existent în Haskell.
Prelude> :t (++) (++) :: [a] -> [a] -> [a] Prelude> [1, 2, 3] ++ [4, 5, 6] [1,2,3,4,5,6]
b) Scrieți o funcție inv care primește o listă și întoarce inversul ei. Funcția ar trebui să funcționeze exact ca funcția reverse deja existentă în Haskell.
Prelude> :t reverse reverse :: [a] -> [a] Prelude> reverse [1, 2, 3] [3,2,1]
4. Implementați o funcție care primește o listă și o sortează folosind algoritmul:
a) merge sort. Ajutați-vă, în implementare, de metodele take, drop și div.
b) insert sort.
c) quick sort.
5. Scrieți o funcție care întoarce numărul de inversiuni dintr-o listă.
L cu n elemente, o inversiune este o pereche de elemente (L[i], L[j]) astfel încât L[i] > L[j] ∧ i < j; i, j = [0, 1, … n-1]