laboratoare:01-functii-recursive
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
laboratoare:01-functii-recursive [2016/02/27 12:15] mihai.dumitru2201 |
laboratoare:01-functii-recursive [2016/02/29 23:45] (current) calin.cruceru [Tail recursion] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Laborator 2 - Funcții recursive ====== | + | ====== Haskell: Introducere ====== |
| + | |||
| + | * 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. | Scopul acestui laborator este a de familiariza studenții cu limbajul Haskell. | ||
| Line 5: | Line 7: | ||
| ===== Introducere ===== | ===== Introducere ===== | ||
| - | //TODO// | + | 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 ===== | ===== Platforma Haskell ===== | ||
| Line 30: | Line 32: | ||
| ===== Tipuri de date în Haskell ===== | ===== 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//. | + | 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. |
| ==== Tipuri de bază ==== | ==== Tipuri de bază ==== | ||
| - | Haskell are tipuri asemănătoare celor din alte limbaje studiate până acum, ca C, Java etc: Int, Integer (dimensiune arbitrară), Float, Double, Char (cu apostrofuri, e.g. 'a'), Bool. | + | 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. |
| - | + | ||
| - | <note>Numele tipurilor și al constantelor (e.g. True) sunt scrise cu literă mare.</note> | + | |
| <code> | <code> | ||
| Line 68: | Line 68: | ||
| <note> | <note> | ||
| Pentru a reprezenta șiruri de caractere, putem folosi tipul ''String'' care este un alias peste ''[Char]''.\\ | Pentru a reprezenta șiruri de caractere, putem folosi tipul ''String'' care este un alias peste ''[Char]''.\\ | ||
| - | Astfel, ''"String"'' este doar un mod mai lizbil de a scrie\\ | + | 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']'', care, la rândul său, este un mod mai lizibil de a scrie\\ | ||
| '''S':'t':'r':'i':'n':'g':[]'' | '''S':'t':'r':'i':'n':'g':[]'' | ||
| Line 86: | Line 86: | ||
| Prelude> :t ("sir", True, False) | Prelude> :t ("sir", True, False) | ||
| ("sir", True, False) :: ([Char], Bool, Bool) | ("sir", True, False) :: ([Char], Bool, Bool) | ||
| - | Prelude> | ||
| - | |||
| </code> | </code> | ||
| + | |||
| ===== Funcții în Haskell ===== | ===== Funcții în Haskell ===== | ||
| Line 148: | Line 147: | ||
| </code> | </code> | ||
| - | <note> | + | <note tip> |
| Pentru a defini o funcție direct în ghci, folosiți cuvântul cheie "let": | Pentru a defini o funcție direct în ghci, folosiți cuvântul cheie "let": | ||
| <code> | <code> | ||
| Line 162: | Line 161: | ||
| </code> | </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 cotinuare la PP. | + | 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> | <note> | ||
| Line 179: | Line 178: | ||
| ==== Pattern matching ==== | ==== Pattern matching ==== | ||
| - | Vom scrie acum o altă funcție prin care ne propunem să calculămm, în mod recursiv, suma tuturor elementelor dintr-o listă. Pentru o listă vidă aceasta este 0, altfel este capul listei plus suma celorlalte elemente. | + | 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> | <code haskell> | ||
| Line 196: | Line 195: | ||
| </code> | </code> | ||
| - | Deși funcțională, implementarea de mai sus nu este foarte elegantă. Putem să ne folosim de pattern matching (ca la TDA-uri). | + | 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> | <code haskell> | ||
| Line 203: | Line 202: | ||
| </code> | </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> | + | <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. | 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. | ||
| Line 210: | Line 211: | ||
| ==== Tail recursion ==== | ==== Tail recursion ==== | ||
| - | //TODO// | + | 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.\\ | ||
| + | |||
| + | 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. | ||
| + | </note> | ||
| <code haskell> | <code haskell> | ||
| + | -- Folosim sintaxa "let ... in" pentru a ascunde functia | ||
| + | -- auxiliara folosita si a pastra forma functiei sum (un singur | ||
| + | -- argument) | ||
| sum''' l = let | sum''' l = let | ||
| sumAux [] acc = acc | sumAux [] acc = acc | ||
| Line 220: | Line 248: | ||
| </code> | </code> | ||
| - | * Cum rulam cod Haskell. Editor. Interpretor. | + | ===== Exerciții ===== |
| - | * Definitia unei functii in Haskell. Specificarea parametrilor. | + | |
| - | * Apelul unei functii in Haskell. Folosirea parantezelor. | + | |
| - | * Pattern matching pe liste in Haskell. Ordinea specificarii pattern-urilor. | + | |
| - | * Despre tipuri in Haskell: | + | 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. |
| - | * Exemplu: ''%%[1,2]:[3,4] = [[1,2],3,4]%%'' (de ce acest lucru nu este posibil in Haskell?) | + | |
| + | 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. | ||
| - | ==== Exercitii ==== | + | 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. |
| - | * Determinarea factorialului unui numar (implementare fara restrictii + implementare tail-end) | + | |
| - | * Determinarea numarului n din sirul lui Fibbonacci (implementare fara restrictii + implementare tail-end) | + | |
| - | * Concatenarea si inversarea unei liste | + | |
| - | * Implementare Mergesort (folosind ''take'', ''drop'' si ''div'') | + | |
| - | * Implementare Insertion sort | + | |
| - | * Implementare Quicksort | + | |
| - | * Calculul inversiunilor dintr-o lista | + | |
| - | ==== Q & A === | + | <code> |
| - | * ! Aceasta zona poate fi editata de studenti | + | 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> | ||
| - | ==== Solutii laborator ==== | + | ==== Referințe ==== |
| - | * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Solutii laborator 1]] | + | * [[http://learnyouahaskell.com/|Learn you a Haskell for Great Good]] |
| - | * Puteti, alternativ, sa folositi urmatorul [[https://github.com/Programming-Paradigms/Labs.git|repository git]] pentru a descarca solutiile si le sincroniza, ulterior. | + | * [[http://worrydream.com/refs/Hughes-WhyFunctionalProgrammingMatters.pdf|Why Functional Programming Matters]] |
| - | * Git si GitHub [[https://try.github.io| - tutorial]]. | + | * [[https://wiki.haskell.org/Why_Haskell_matters|Why Haskell Matters]] |
| + | * [[http://book.realworldhaskell.org/|Real World Haskell]] | ||
| + | ==== 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]]. | ||
laboratoare/01-functii-recursive.1456568149.txt.gz · Last modified: 2016/02/27 12:15 by mihai.dumitru2201
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
