-- Cristian Giumale - Note de curs
-- Ceea ce urmeaza este un modul de program valid in Haskell

module Curs1 where

instance Show (a -> b) where
     show f = "<function>"

{- 
   Caracteristici Haskell:
   - Sintaxa, indentare, operatori predefiniti si constructii 
     pt. controlul domeniului de valabilitate al variabilelor
   - Evaluare expresii
   - Sisemul de tipuri (sinteza de tip)
   - Tratarea OOP
   - Calcul monadic

   *** 1 **** Sintaxa (simplificata)
   <program> :: = <modul> ...
   <modul> ::= module <id> where { <decls> }

   <decls> ::= <decl>;...
   <decl> ::= <var> = <expr>
-}

ident = \x -> x

maplist = 
   \f lis -> case lis of {
                []   -> [];
                x:xs -> f x : maplist f xs 
                -- f x : maplist f xs este (cons (f x) (maplist f xs))
             }

{- Echivalent OCaml, Caml:

let rec maplist =
    fun f lis -> match lis with
                   []      -> []
                 | (x::xs) -> (f x)::(maplist f xs)

   *** Indentare ***
   
   Acoladele {,} si separatorul ; pot fi omise cf. urmatoarelor reguli:

   1) Daca { lipseste dupa where, let, of, do atunci 
       - Se deschide un nou paragraf de indentare
       - { este inserata automat
       - pozitia de inceput poz_0 a urmatoarei lexeme, fie ea lex0, este memorata.
         poz0 devine pozitia de aliniere a paragrafului curent de indentare.
         
   2) Daca lexema lex_i, i>0, incepe la pozitia poz_i > poz_0 pe o noua linie 
      atunci lex_i este considerata continuarea sintactica a lui lex_i-1
   3) Daca lexema lex_i, i>0, incepe la pozitia poz_i = poz_0 pe o noua linie 
      atunci se insereaza automat ; dupa lex_i-1
   4) Daca lex_i incepe la pozitia poz_i < poz_0 
       - se adauga automat } pentru fiecare paragraf de indentare cu pozitia de 
         aliniere > poz_i (deci si pentru paragraful curent)

   5) La sfirsitul programului se adauga }
-}

maplist1 = 
   \f lis -> case lis of 
           []   -> []
           x:xs -> f x : maplist1 f xs

-- Variante de scriere

maplist2 f lis =  case lis of 
                   []   -> []
                   x:xs -> f x : maplist2 f xs

maplist3 f [] = []
maplist3 f (x:xs) = f x : maplist3 f xs

-- Definitii locale

maplist4 f = let aux [] = []
                 aux (x:xs) = f x : aux xs
             in aux  

maplist5 f = aux where 
               aux [] = []
               aux (x:xs) = f x : aux xs

--  e where decls = let decls in e

{- 
   *** Operatori si constructii utile ***
       - compozitia functionala: este predefinit f . g = \x -> f (g x)
       - fixitate si precedenta: 
            - orice operator infixat # are forma prefixata (#)
            - orice functie binara si prefixata f poate fi aplicata infixat _ `f` _
              ex. f `maplist5` l
       - sectiuni: fie (#) x y = corp o functie binara infixata si e o expresie
                   (e #) = \y -> e # y  este sectiunea stinga a lui #
                   (# e) = \x -> x # e este sectiunea dreapta a lui #
         ex. (+1) = succ sau (1+) = succ
-}

l = (+1) `maplist5` [1,2,3]
doi_x_plus_1 = (+1) . (* 2)


{- 
   *** Evaluare lenesa ***
   In Haskell orice expresie este evaluata o singura data si doar atunci cand 
   ii este folosita valoarea. Valoarea este salvata intr-o variabila cache 
   (invizibila) si este folosita ori de cate ori expresia trebuie evaluata din 
   nou (similar cu delay si force din Scheme). 
     
   De exemplu, pentru apelul (flux 2 succ) expresia (flux (succ 2) succ) din
   corpul functiei nu este evaluata decit o data si doar atunci cand trebuie. 
-}

flux t0 f = t0 : flux (f t0) f
naturale = flux 0 succ 

fibo = 0 : 1 : (fibo `plus` (tail fibo))


-- Nu tipariti naturale: evident, tiparirea nu se termina (teoretic)
-- Incercati (take 10 naturale) sau (take 10 (drop 20 naturale))

{- 
   *** Implicatii ale evaluarii lenese ***

   - Domeniul de valabilitate al variabilelor este intotdeauna intregul bloc
     in care sunt definite
   - Lucrul cu structuri infinite sau calcule care nu se termina devine foarte comod.
     (ex. fluxurile sunt liste infinite)
   - Programele se apropie mai mult de o specificatie a problemei rezolvate
-}


-- Functiile mutual recursive pot fi definite in orice ordine,
-- datorita domeniului de valabilitate al variabilelor, domeniu
-- extins la un intreg bloc where (in particular modul) let 

par 0 = True
par (n+1) = impar n

impar 0 = False
impar (n+1) = par n

{- 
   *** Constructii predefinite pt. liste infinite ***
   In cazuri particulare, fluxul construit de functia flux poate fi
   specificat mult mai simplu. Sunt predefinite constructiile 

           [t0 ..] = [t0, t0+1, t0+2, ...]
           [t0,t1 ..] = [t0, t1, t0+q, t0+2q, ...] unde q = t1-t0

   Astfel fluxurile numerelor pare si impare sunt:
-}

impare = [1,3 ..]
pare = [2,4 ..]


-- Sa ne jucam putin mai mult cu fluxuri

nr_prime = cerne candidati 
       where
           candidati = [2 ..]
           cerne (x:xs) = x : cerne (candidati_fara_multipli_ai_lui_x xs)
             where
                candidati_fara_multipli_ai_lui_x (y:ys) =
                   if y `mod` x == 0 then candidati_fara_multipli_ai_lui_x ys
                   else y : (candidati_fara_multipli_ai_lui_x ys)

primele_20 = take 20 nr_prime

-- Cum scriem mai frumos?
{- 
   * List comprehensions *

   Fie expresia LC =def [e | q_1, ..., q_n] unde q_i poate fi  
     - un "generator" v_i <- lista_i, unde v_i este o variabila libera din e
     - o "expresie de garda" p_i, unde p_i este un predicat ce foloseste
       variabilele libere din e 

   Expresia LC sta pentru o lista formata cf. specificatiei:

   {orice v_1 in lista_1, v_2 in lista_2, ..., v_r in lista_r | 
          (p_1 v_1 ... v_n) ... && ... (p_m v_1 ... v_n) . e}
         
  
   Domeniul lexical al v_i este e si zona din LC care urmeaza generatorului
   lui v_i.
-}

nr_prime1 = cerne candidati 
     where
        candidati = [2 ..]
        cerne (x:xs) = x : cerne candidati_fara_multipli_ai_lui_x
           where
              candidati_fara_multipli_ai_lui_x = [y | y <- xs, y `mod` x /= 0]
 
-- Mai compact: 
nr_prime2 = cerne [2 ..] where
    cerne (a:x) = a : (cerne [y | y <- x , y `mod` a /= 0])

-- Si exact ca specificatia numerelor prime: 
-- prime = {orice n in {2,3,...} | (nu exista d in {2,...,n/2} . n divizibil prin d)}

nr_prime3 = [n | n <- [2 ..], not (any (\d -> n `mod` d == 0) [2 .. (n `div` 2)])]

-- Numerele lui Fibonacci
fibo = 0 : 1 : (plus fibo (tail fibo)) where
       plus (x:la) (y:lb) = (x+y):(plus la lb)

-- Aproximare pi
serie_pi = 
    make_pi 0 1 where
        make_pi s k = s : (make_pi (s+4/k) (if k < 0 then 2-k else 0-k-2))

pi = (serie_pi !!)
-- Apelul pi 2000 calculeaza pi folosind 2000 de termeni


-- Produs cartezian 
-- Varianta 1 clasica:
--      vid x b = vid
--      ({x} U a) x b  = {orice y in b . (x,y)} U (a x b)

cartez1 [] _ = []
cartez1 (x:xs) b = map (\y -> (x,y)) b ++ cartez1 xs b

-- Varainta 2 folosind list comprehension
cartez2 a b = [(x,y) | x <- a, y <- b]

-- Varianta 3, rezulta din translatarea list comprehension
-- cf. ecuatiilor:
--     [x | x <- l] = l
--     [f x | x <- l] = map f l
--     [e | x <- l, ...] = concat [[e | ...] | x <- l]
--     [e | x <- l, p x, ...] = [e | x <- (filter p l), ...]
-- sau

-- [e | True] = [e]
-- [e | qualifier ] = [ e | qualifier,True] , qualifier <> True
-- [e | predicate, Rest] = if predicate then [e|Rest] else []
-- [e | pattern <- list , Rest] = concatMap (\pattern -> [e | Rest]) list

{-

cartez2 a b = [(x,y) | x <- a, y <- b]
cartez2 a b = concatMap (\x -> [(x,y) | Y <- b]) a 
cartez2 a b = concatMap (\x -> [(x,y) | Y <- b, True]) a
cartez2 a b = concatMap (\x -> concatMap (\y -> [(x,y) | True]) b) a 
cartez2 a b = concatMap (\x -> concatMap (\y -> [(x,y)]) b) a

-}

cartez2' a b = concatMap (\x -> concatMap (\y -> [(x,y)]) b) a


cartez3 a b =
  concat (map (\x -> map (\y -> (x,y)) b) a)

-- concat este predefinit si are comportarea:
concat1 [] = []
concat1 (x:xs) = x++(concat1 xs)

-- sau mai concis
concat2 = foldl (++) [] 

-- Produsul cartezian dintre numerele prime si multimea ["a","b"]
cartez_prime =  nr_prime2 `cartez2` ["a","b"]

{-  Un graf finit cu 2 noduri si cu navigarea:

     rs a = a, rs b =b, ls a = b, ls b = a. Cheile din noduri sunt: k a = 1, k b =2

          |-->         <--|
       rs |  a <=====> b  | rs
          |__|    ls   |__|
-}

data G a = Nod a (G a) (G a) deriving (Eq,Show)

graf = a where 
            a = Nod 1 b a
            b = Nod 2 a b
ls (Nod _ l _) = l
rs (Nod _ _ r) = r
k  (Nod k _ _) = k


-- p::(Integer,Integer)
p=(1,2,3)

unitt=()
and2 = \x y -> if x then y else False


and21 x y = case (x,y) of {
                (False,False) -> False;
                (False,True) -> False;
                (True,False) -> False;
                (True,True)->True}
and22 x y = case (x,y) of 
    (True,True) -> True
    (_,_) -> False

and23 True y = y
and23 _ _ = False

pow y x = case x of
           0 -> 1
           n | (even n) -> let p= pow y (n `div` 2) in p*p
           (n+1) -> let p = pow y (n `div` 2) in p*p*y


pow1 _ 0 = 1
pow1 y x
      | even x = (let p = pow1 y (x `div` 2) in p*p)
      | otherwise = (let p = pow1 y ((x-1)`div`2) in p*p*y)