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/28 19:57] mihai.dumitru2201 [Exercitii] |
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 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 245: | Line 247: | ||
| sumAux l 0 | sumAux l 0 | ||
| </code> | </code> | ||
| - | |||
| - | <note> | ||
| - | Pentru a vedea diferența dintre cele două implementări, puteți încerca următorul test: | ||
| - | <code> | ||
| - | *Main> sum'' (take 15000000 (repeat 1)) | ||
| - | *** Exception: stack overflow | ||
| - | *Main> sum''' (take 15000000 (repeat 1)) | ||
| - | 15000000 | ||
| - | </code> | ||
| - | </note> | ||
| - | |||
| ===== Exerciții ===== | ===== Exerciții ===== | ||
| Line 299: | Line 290: | ||
| </note> | </note> | ||
| - | ==== Q & A === | + | ==== Referințe ==== |
| - | * ! Aceasta zona poate fi editata de studenti | + | * [[http://learnyouahaskell.com/|Learn you a Haskell for Great Good]] |
| - | + | * [[http://worrydream.com/refs/Hughes-WhyFunctionalProgrammingMatters.pdf|Why Functional Programming Matters]] | |
| - | ==== Solutii laborator ==== | + | * [[https://wiki.haskell.org/Why_Haskell_matters|Why Haskell Matters]] |
| - | * [[https://github.com/Programming-Paradigms/Labs/archive/master.zip|Solutii laborator 1]] | + | * [[http://book.realworldhaskell.org/|Real World Haskell]] |
| - | * Puteti, alternativ, sa folositi urmatorul [[https://github.com/Programming-Paradigms/Labs.git|repository git]] pentru a descarca solutiile si le sincroniza, ulterior. | + | ==== Soluții laborator ==== |
| - | * Git si GitHub [[https://try.github.io| - tutorial]]. | + | * [[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.1456682279.txt.gz · Last modified: 2016/02/28 19:57 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
