pp-cb

This is an old revision of the document!

---

====== Laborator 1 - Funcții recursive ====== * Responsabili laborator: [[mihai.dumitru@cti.pub.ro|Dumitru Mihai-Valentin]], [[calin.cruceru@cti.pub.ro|Călin Cruceru]] Scopul acestui laborator este a de familiariza studenții cu limbajul Haskell. ===== Introducere ===== Haskell este un limbaj de programare [[https://en.wikipedia.org/wiki/Functional_programming|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ă. ===== Platforma Haskell ===== Pentru început, avem nevoie de un mod de a compila cod. Puteți descărca platforma Haskell de [[https://www.haskell.org/platform|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: <code> GHCi, version 7.10.3: http://www.haskell.org/ghc/ :? for help Prelude> </code> ^ 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 | ===== Tipuri de date în Haskell ===== Haskell este un limbaj tare-tipat (strongly-typed) care poate face type inference. Asta înseamnă că tipul tuturor expresiilor este cunoscut la **compilare**; dacă nu este explicit, compilatorul îl //deduce//. ==== Tipuri de bază ==== 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. <code> Prelude> :t 'a' 'a' :: Char Prelude> :t True True :: Bool Prelude> :t 0 == 1 0 == 1 :: Bool Prelude> :t 42 42 :: Num a => a </code> <note>"::" se citește ca "are tipul". Deci, de exemplu, "True are tipul Bool".</note> 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''. ==== Liste ==== 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ă: <code>[1, 2, 3, 4]</code> 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. <code> [['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] </code> <note> Pentru a reprezenta șiruri de caractere, putem folosi tipul ''String'' care este un alias peste ''[Char]''.\\ Astfel, ''"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':[]'' </note> ==== Tupluri ==== 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ă: <code>(1, 'a', True)</code> Tipul unui tuplu este dat de numărul, ordinea și tipul elementelor sale: <code> 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) </code> ===== Funcții în Haskell ===== ==== Apelare ==== Î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): <code> <Prelude> max 1 2 2 </code> Funcțiile infixate sunt cele cu nume formate din caractere speciale, de forma //operand1 operator operand2// <code> Prelude> 1 + 2 3 </code> <note> În anumite situații ne-am dori să schimbăm modul de afixare al funcțiilor (e.g. din motive de claritate).\\ Pentru a prefixa o funcție infixată, folosim operatorul ''()''. Astfel, următoarele expresii sunt echivalente: <code> 3 * 23 (*) 3 23 </code> 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: <code> mod 10 3 10 `mod` 3 </code> </note> ==== Definirea unei funcții ==== Creați, în editorul de text preferat, un fișier cu extensia ''.hs'' în care vom defini prima funcție: <code haskell> -- intoarce modulul dublului celui mai mare dintre cele doua argumente myFunc x y = abs (2 * max x y) </code> <note important> Rolul parantezelor aici este de a forța ordinea dorită de a efectua operațiilor. Altfel funcția ar înmulți 2 (modulul lui 2) cu cel mai mare dintre numere, pentru că aplicarea funcției are precedență mai mare. </note> Puteți testa funcția din ghci: <code> 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 </code> <note tip> Pentru a defini o funcție direct în ghci, folosiți cuvântul cheie "let": <code> Prelude>let myFunc x y = abs (2 * max x y) </code> </note> 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: <code> Prelude> :t myFunc myFunc :: (Num a, Ord a) => a -> a -> a </code> 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. <note> Deși nu e întotdeauna necesar, specificarea manuală a tipului unei funcții e considerată "good practice". Editați fișierul de mai devreme astfel încât să arate așa: <code haskell> -- intoarce modulul dublului celui mai mare dintre cele doua argumente myFunc :: Int -> Int -> Int myFunc x y = abs (2 * max x y) </code> 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ă. </note> ==== Pattern matching ==== 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. <code haskell> {- - 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 </code> Deși funcționează, implementarea de mai sus nu este foarte elegantă. Putem să ne folosim de pattern matching (ca la TDA-uri). <code haskell> sum'' [] = 0 sum'' (x:xs) = x + sum'' xs </code> <note important> Ordinea din fișier este importantă. Pattern-urile sunt evaluate de sus în jos și ar trebui scrise de la cel mai particular la cel mai general (ultimul fiind un "catch-all"). </note> 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. ==== Tail recursion ==== 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: <code> 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 </code> 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. <note important> Folosirea unui acumulator în acest scop este un tipar des întâlnit, util pentru că poate permite reducerea spațiului de stivă necesar de la O(n) la O(1). Unele limbaje (e.g. C) nu garantează această optimizare, care depinde de compilator.\\ Standardul Haskell garantează implementarea tail-recursion. </note> <code haskell> -- 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 </code> ===== Exerciții ===== 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. <code> Prelude> :t (++) (++) :: [a] -> [a] -> [a] Prelude> [1, 2, 3] ++ [4, 5, 6] [1,2,3,4,5,6] </code> 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. <code> Prelude> :t reverse reverse :: [a] -> [a] Prelude> reverse [1, 2, 3] [3,2,1] </code> 4. Implementați o funcție care primește o listă și o sortează folosind algoritmul: a) [[https://en.wikipedia.org/wiki/Merge_sort|merge sort]]. Ajutați-vă, în implementare, de metodele ''take'', ''drop'' și ''div''. b) [[https://en.wikipedia.org/wiki/Insertion_sort|insert sort]]. c) [[https://en.wikipedia.org/wiki/Quicksort|quick sort]]. 5. Scrieți o funcție care întoarce numărul de inversiuni dintr-o listă. <note tip> Într-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]'' </note> ==== Soluții laborator ==== * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Soluții laborator 1]] * Puteti, alternativ, să folosiți următorul [[https://github.com/Programming-Paradigms/Labs.git|repository git]] pentru a descărca soluțiile și a le sincroniza, ulterior. * Git și GitHub [[https://try.github.io| - tutorial]].