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 13:16] 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ă ==== | ||
| Line 66: | 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 84: | 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 146: | 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 160: | 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 177: | 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 231: | Line 232: | ||
| <note important> | <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.\\ | 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. | + | |
| + | 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> | </note> | ||
| Line 246: | Line 248: | ||
| </code> | </code> | ||
| - | <note> | + | ===== Exerciții ===== |
| - | Pentru a vedea diferența dintre cele două implementări, puteți încerca următorul test: | + | |
| + | 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> | <code> | ||
| - | *Main> sum'' (take 15000000 (repeat 1)) | + | Prelude> :t (++) |
| - | *** Exception: stack overflow | + | (++) :: [a] -> [a] -> [a] |
| - | *Main> sum''' (take 15000000 (repeat 1)) | + | Prelude> [1, 2, 3] ++ [4, 5, 6] |
| - | 15000000 | + | [1,2,3,4,5,6] |
| </code> | </code> | ||
| - | </note> | ||
| + | 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. | ||
| - | ==== Exercitii ==== | + | <code> |
| - | * Determinarea factorialului unui numar (implementare fara restrictii + implementare tail-end) | + | Prelude> :t reverse |
| - | * Determinarea numarului n din sirul lui Fibbonacci (implementare fara restrictii + implementare tail-end) | + | reverse :: [a] -> [a] |
| - | * Concatenarea si inversarea unei liste | + | Prelude> reverse [1, 2, 3] |
| - | * Implementare Mergesort (folosind ''take'', ''drop'' si ''div'') | + | [3,2,1] |
| - | * Implementare Insertion sort | + | </code> |
| - | * Implementare Quicksort | + | |
| - | * Calculul inversiunilor dintr-o lista | + | |
| - | ==== Q & A === | ||
| - | * ! Aceasta zona poate fi editata de studenti | ||
| - | ==== Solutii laborator ==== | + | 4. Implementați o funcție care primește o listă și o sortează folosind algoritmul: |
| - | * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Solutii laborator 1]] | + | |
| - | * Puteti, alternativ, sa folositi urmatorul [[https://github.com/Programming-Paradigms/Labs.git|repository git]] pentru a descarca solutiile si le sincroniza, ulterior. | + | a) [[https://en.wikipedia.org/wiki/Merge_sort|merge sort]]. Ajutați-vă, în implementare, de metodele ''take'', ''drop'' și ''div''. |
| - | * Git si GitHub [[https://try.github.io| - tutorial]]. | + | |
| + | 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> | ||
| + | |||
| + | ==== Referințe ==== | ||
| + | * [[http://learnyouahaskell.com/|Learn you a Haskell for Great Good]] | ||
| + | * [[http://worrydream.com/refs/Hughes-WhyFunctionalProgrammingMatters.pdf|Why Functional Programming Matters]] | ||
| + | * [[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.1456571771.txt.gz · Last modified: 2016/02/27 13:16 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
