pp-cb

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Laborator 2 - Funcții recursive ======

Scopul acestui laborator este a de familiariza studenții cu limbajul Haskell.

===== Introducere =====

//TODO//

===== 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 (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>
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 lizbil 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)
Prelude> 

</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>
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 cotinuare 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ă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.

<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țională, 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 ====

//TODO//

<code haskell>
sum''' l = let
           sumAux [] acc = acc
           sumAux (x:xs) acc = sumAux xs (x + acc)
           in
           sumAux l 0
</code>

  * Cum rulam cod Haskell. Editor. Interpretor.
  * 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:
      * Exemplu: ''%%[1,2]:[3,4] = [[1,2],3,4]%%'' (de ce acest lucru nu este posibil in Haskell?)




==== Exercitii ====
  * 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 ===
  * ! Aceasta zona poate fi editata de studenti

==== Solutii laborator ====
  * [[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.
  * Git si GitHub [[https://try.github.io| - tutorial]].
pp-cb

User Tools

Site Tools

Page Tools
