[TOC]

#Chestii simple

##Operatii

- `/=` diferit
- `==` egal
- `<=` si `>=`
- `rem` restul impartirii
- `div` impartire
- `*` inmultire
- `^` ridicare la putere
- `sqrt` radical

##Liste

Se adauga lista la alta lista cu `++`

```haskell
Prelude> [1,2,3] ++ [12]
[1,2,3,12]
```

Se iau elemente din lista cu `:`

```haskell
-- Double every second number in a list starting on the left.
doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther [x] = [x]
doubleEveryOther (x : y : ls) = x : 2 * y : doubleEveryOther(ls)
```

##Multimi

```haskell
-- Sa se determine toate sirurile s = xy obtinute dintr­-o lista xs
--  cu proprietatea ca x si y apartin listei xs si sirul s e palindom.
--   (ex. pal ["say", "on", "not", "to", "as"] = ["sayas","noton","tonot"])
pal :: [String] -> [String]
pal ls = [x ++ y | x <- ls, y <- ls, reverse(x ++ y) == x ++ y]
```

##Map

Aplica functie fiecarui element din lista `map functie lista`.
Merge apelata si ca `functie `map` lista`.

```haskell
Prelude Data.Char> map toUpper "teSt"
"TEST"

Prelude > map (\x -> x * x) [1, 2, 3, 4, 5]
[1, 4, 9, 16, 25]

Prelude Data.Char> toLower `map` "AbCCADAS"
"abccadas"

##Filter

Returneaza numai elementele ce trec prin filtru.

```haskell
Prelude> filter(/= 'a') "aAAbcsa"
"AAbcs"

Prelude> filter(== 1) [1, 12, 1, 14]
[1,1]

Prelude Data.Char>  filter(isLetter) "1a2b3c5d"
"abcd"
```

##Foldl si prietenii

```haskell
foldr functie element_initial (1:2:3:[]) = 1 `functie` (2 `functie` (3 `functie` element_initial))

Prelude> foldl (+) 0 [1,2,3,4,5]
15

foldl (-) 100 [1]         = 99 = ((100)-1)
foldl (-) 100 [1,2]       = 97 = (( 99)-2) = (((100)-1)-2)
foldl (-) 100 [1,2,3]     = 94 = (( 97)-3)
foldl (-) 100 [1,2,3,4]   = 90 = (( 94)-4)
foldl (-) 100 [1,2,3,4,5] = 85 = (( 90)-5)

Prelude> foldr (\x y -> concat ["(", x, "+", y, ")"]) "0" (map show [1..13])
"(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))"

Prelude> foldl (\x y -> concat ["(", x, "+", y, ")"]) "0" (map show [1..13])
"(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)"

Prelude> foldt (\x y -> concat ["(", x, "+", y, ")"]) "0" (map show [1..13])
"((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))"

Prelude> foldi (\x y -> concat ["(", x, "+", y, ")"]) "0" (map show [1..13])
"(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"
```

#Tipuri de date algebrice

Pot sa fie absolut orice.

```haskell
data Bool = False | True
data Season = Winter | Spring | Summer | Fall
data Shape = Circle Float | Rectangle Float Float
data List a = Nil | Cons a (List a)
data Nat = Zero | Succ Nat
data Exp = Lit Int | Add Exp Exp | Mul Exp Exp
data Tree a = Empty | Leaf a | Branch (Tree a) (Tree a) data Maybe a = Nothing | Just a
data Pair a b = Pair a b
data Either a b = Left a | Right b
```

##Anotimpuri

```haskell
data Season = Spring | Summer | Autumn | Winter

next :: Season -> Season
next Spring = Summer
next Summer = Autumn
next Autumn = Winter
next Winter = Spring

eqSeason :: Season -> Season -> Bool
eqSeason Spring Spring = True
eqSeason Summer Summer = True
eqSeason Autumn Autumn = True
eqSeason Winter Winter = True
eqSeason _      _      = False

showSeason :: Season -> String
Spring = " Spring "
Summer = " Summer "
Autumn = " Autumn "
Winter = " Winter "

data Season = Winter | Spring | Summer | Fall

toInt :: Season -> Int
toInt Winter = 0
toInt Spring = 1
toInt Summer = 2
toInt Fall   = 3

fromInt :: Int -> Season
fromInt 0 = Winter
fromInt 1 = Spring
fromInt 2 = Summer
fromInt 3 = Fall

next :: Season -> Season
next x = fromInt ((toInt x + 1) `mod` 4)
```

##Cercuri si dreptunghiuri

```haskell
type Radius = Float
type Width = Float
type Height = Float

data Shape = Curclr Radius
            | Rectangle Width Height

area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rectangle w h) = w * h

eqShape :: Shape -> Shape -> Bool
eqShape (Circle r) (Circle r2) = (r == r2)
eqShape (Rectangle w h) (Rectangle w2 h2) = (w == w2) && (h == h2)
eqShape _ _ = False

isCircle :: Shape -> Bool
isCircle ( Circle r ) = True
isCircle _            = False

isRectangle :: Shape -> Bool
isRectangle ( Rectangle w h ) = True
isRectangle _                 = False

radius :: Shape -> Float
radius (Circle r) = r

width :: Shape -> Float
width (Rectangle w h) = w

height :: Shape -> Float
height (Rectangle w h) = h

area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rectangle w h) = w * h

area :: Shape -> Float
area s =
        if isCircle s then
                let
                        r = radius s
                in
                        pi * r^2
        else if isRectangle s then
                let
                        w = width s
                        h = height s
                in
                        w * h
        else error " impossible "
```

##Expresii - curs

###Expresii

```haskell
data Exp = Lit Int
          | Add Exp Exp
          | Mul Exp Exp


evalExp :: Exp -> String
evalExp (Lit n) = n
evalExp (Add e f) = evalExp e + evalExp f
evalExp (Mul e f) = evalExp e * evalExp f

showExp :: Exp -> String
showExp (Lit n) = show n
showExp (Add e f) = par (showExp e ++ "+" ++ showExp f)
showExp (Mul e f) = par (showExp e ++ "*" ++ showExp f)

par :: String -> String
par s = "(" ++ s ++ ")"
```

```haskell
e0, e1 :: Exp

e0 = Add (Lit 2) (Mul (Lit 3) (Lit 3))
e1 = Mul (Add (Lit 2) (Lit 3)) (Lit 3)

*Main> showExp e0
" (2+(3*3) ) "

* Main> evalExp e0
11

*Main> showExp e1
" ((2+3) *3) "

* Main> evalExp e1
15
```


###Expresii - forma infixata

```haskell
data Exp = Lit Int
          | Exp `Add` Exp
          | Exp `Mul` Exp

evalExp :: Exp -> Int
evalExp (Lit n) = n
evalExp (e ‘Add‘ f) = evalExp e + evalExp f
evalExp (e ‘Mul‘ f) = evalExp e * evalExp f

showExp :: Exp -> String
showExp (Lit n) = show n
showExp (e `Add` f) = par (showExp e ++ "+" ++ showExp f)
showExp (e `Mul` f) = par (showExp e ++ "*" ++ showExp f)

par :: String -> String
par s = "(" ++ s ++ ")"
```

```haskell
e0, e1 :: Exp

e0 = Lit 2 ‘Add‘ (Lit 3 ‘Mul‘ Lit 3)
e1 = (Lit 2 ‘Add‘ Lit 3) ‘Mul‘ Lit 3

*Main> showExp e0
" (2+(3*3) ) "

* Main> evalExp e0
11

*Main> showExp e1
" ((2+3) *3) "

* Main> evalExp e1
15
```



###Expresii - cu operatori
```haskell
data Exp = Lit Int
          | Exp :+: Exp
          | Exp :*: Exp

evalExp :: Exp -> Int
evalExp (Lit n) = n
evalExp (e :+: f) = evalExp e + evalExp f
evalExp (e :*: f) = evalExp e * evalExp f

showExp :: Exp -> String
showExp (Lit n) = show n
showExp (e :+: f) = par (showExp e ++ "+" ++ showExp f)
showExp (e :*: f) = par (showExp e ++ "*" ++ showExp f)

par :: String -> String
par s = "(" ++ s ++ ")"
```

```haskell
e0, e1 :: Exp

e0 = Lit 2 :+: (Lit 3 :*: Lit 3)
e1 = (Lit 2 :+: Lit 3) :*: Lit 3

*Main> showExp e0
" (2+(3*3) ) "

* Main> evalExp e0
11

*Main> showExp e1
" ((2+3) *3) "

* Main> evalExp e1
15
```


##Exercitii

###Mere si portocale

```haskell
-- The datatype 'Fruit'
data Fruit = Apple(String, Bool)
           | Orange(String, Int)

-- Some example Fruit
apple, apple', orange :: Fruit
apple  = Apple("Granny Smith", False) -- a Granny Smith apple with no worm
apple' = Apple("Braeburn", True)      -- a Braeburn apple with a worm
orange = Orange("Sanguinello", 10)    -- a Sanguinello with 10 segments

fruits :: [Fruit]
fruits = [Orange("Seville", 12),
          Apple("Granny Smith", False),
          Apple("Braeburn", True),
          Orange("Sanguinello", 10)]

-- This allows us to print out Fruit in the same way we print out a list, an Int or a Bool.

instance Show Fruit where
  show (Apple(variety, hasWorm))   = "Apple("  ++ variety ++ ", " ++ show hasWorm  ++ ")"
  show (Orange(variety, segments)) = "Orange(" ++ variety ++ ", " ++ show segments ++ ")"


isBloodOrange :: Fruit -> Bool
isBloodOrange (Orange (b, c)) = if b `elem` ["Tarocco", "Moro", "Sanguinello"]
                       then True
                       else False
isBloodOrange _ = False

getNumberOfSlices :: Fruit -> Int
getNumberOfSlices (Apple (b, c)) = 0
getNumberOfSlices (Orange (b, c)) = c

bloodOrangeSegments :: [Fruit] -> Int
bloodOrangeSegments xs = foldl (+) 0 (getNumberOfSlices `map` (filter isBloodOrange xs))

-- [Orange("Seville", 12), Orange("Moro", 11), Apple("Granny Smith", False), Apple("Braeburn", True), Orange("Sanguinello", 10)]

isAppleWithWorm :: Fruit -> Bool
isAppleWithWorm (Apple (_, True)) = True
isAppleWithWorm _ = False

worms :: [Fruit] -> Int
worms xs = length (filter isAppleWithWorm xs)
```

###Expresii

The following data type represents arithmetic expressions over a single variable:

```haskell
data Expr = X                     -- variable
          | Const Int             -- integer constant
          | Expr :+: Expr         -- addition
          | Expr :-: Expr         -- substraction
          | Expr :*: Expr         -- multiplication
          | Expr :/: Expr         -- integer division
          | IfZero Expr Expr Expr -- conditional expression
```

`IfZero p q r` represents the expression that would be written in Haskell as if `p == 0 then q else r`.

1. Write a function `eval :: Expr -> Int -> Int`, which given an expression and the value of the variable `X` returns the value of the expression. For example:

```haskell
eval (X :+: (X :*: Const 2)) 3                      = 9
eval (X :/: Const 3) 7                              = 2
eval (IfZero (X :-: Const 3) (X:/:X) (Const 7)) 3   = 1
eval (IfZero (X :-: Const 3) (X:/:X) (Const 7)) 4   = 7
eval (Const 15 :-: (Const 7 :/: (X :-: Const 1))) 0 = 22
```

but both of the following should produce a divide-by-zero exception:

```haskell
eval (Const 15 :-: (Const 7 :/: (X :-: Const 1))) 1
eval (X :/: (X :-: X)) 2
```

2. Write a function `protect :: Expr -> Expr` that protects against divide-by-zero exceptions by "guarding" all uses of division with a test for a zero-valued denominator. In this case the result should be `maxBound` (the maximum value of type `Int`, which is platform dependent). Do not attempt to simplify the result by omitting tests that appear to be unnecessary. For example,

```haskell
protect (X :+: (X :*: Const 2))
                       = (X :+: (X :*: Const 2))

eval (protect (X :+: (X :*: Const 2))) 3 = 9
```

```haskell
protect (X :/: Const 3)
              = IfZero (Const 3) (Const maxBound) (X :/: Const 3)

eval (protect (X :/: Const 3)) 7 = 2
```

```haskell
eval (protect (X :/: (X :-: X))) 2 = maxBound
```
####Afisarea

```haskell
showExpr :: Expr -> String
showExpr X = "X"
showExpr (Const n) = show n
showExpr (p :+: q) = "(" ++ showExpr p ++ "+" ++ showExpr q ++ ")"
showExpr (p :-: q) = "(" ++ showExpr p ++ "-" ++ showExpr q ++ ")"
showExpr (p :*: q) = "(" ++ showExpr p ++ "*" ++ showExpr q ++ ")"
showExpr (p :/: q) = "(" ++ showExpr p ++ "/" ++ showExpr q ++ ")"
showExpr (IfZero p q r) = "(if " ++ showExpr p ++ " = 0 then "
                                 ++ showExpr q ++ "
                                 else "++ showExpr r ++ ")"
```

####Evaluarea

```haskell
eval :: Expr -> Int -> Int
eval X v = v
eval (Const n) _ = n
eval (p :+: q) v = (eval p v) + (eval q v)
eval (p :-: q) v = (eval p v) - (eval q v)
eval (p :*: q) v = (eval p v) * (eval q v)
eval (p :/: q) v = (eval p v) `div` (eval q v)
eval (IfZero p q r) v = if (eval p v) == 0 then eval q v else eval r v
```

####Protectie pentru impartirea la 0

```haskell
protect :: Expr -> Expr
protect X = X
protect (Const n) = (Const n)
protect (p :+: q) = (protect p) :+: (protect q)
protect (p :-: q) = (protect p) :-: (protect q)
protect (p :*: q) = (protect p) :*: (protect q)
protect (p :/: q) = IfZero (protect q) (Const maxBound) ((protect p) :/: (protect q))
protect (IfZero p q r) = IfZero (protect p) (protect q) (protect r)
```

###Arbori

Consider binary trees with `Int`-labelled nodes and leaves, defined as follows:

```haskell
data Tree = Empty
          | Leaf Int
          | Node Tree Int Tree
```

and the following example of a tree:

```
t = Node (Node (Node (Leaf 1)
                2
                Empty)
        3
        (Leaf 4))
5
(Node Empty
        6
        (Node (Leaf 7)
                8
                (Leaf 9)))
```

Each label in a tree can be given an "address": this is the path from the root to the label, consisting of a list of directions:

```haskell
data Direction = L | R
type Path = [Direction]
```

The empty path refers to the label at the root — in `t` above, the label `5`. A path beginning with L refers to a label in the left, or first, subtree, and a path beginning with R refers to the right, or second, subtree. Subsequent L/R directions in the list then refer to left/right subtrees of that subtree. So, for example, `[R,R,L]` is the address of the label 7 in `t`.

####Verifica daca exista calea in arbore

```haskell
present :: Path -> Tree -> Bool
present [] (Leaf n) = True
present [] (Node _ n _) = True
present (L:p) (Node t _ _) = present p t
present (R:p) (Node _ _ t) = present p t
present _ _ = False
```

####Returneaza valoarea unui nod din arbore

```haskell
label :: Path -> Tree -> Int
label [] (Leaf n) = n
label [] (Node _ n _) = n
label (L:p) (Node t _ _) = label p t
label (R:p) (Node _ _ t) = label p t
label _ _ = error "path absent"
```

####Convertire abore in drumuri

```haskell
toFTree' :: Tree -> FTree
toFTree' (Leaf n) [] = n
toFTree' (Node t1 n t2) [] = n
toFTree' (Node t1 n t2) (L:p) = toFTree' t1 p
toFTree' (Node t1 n t2) (R:p) = toFTree' t2 p
toFTree' _ _ = error "path absent"
```

####Construirea arborelui in oglinda

```haskell
mirrorTree :: Tree -> Tree
mirrorTree Empty = Empty
mirrorTree (Leaf n) = Leaf n
mirrorTree (Node t1 n t2) = Node (mirrorTree t2) n (mirrorTree t1)
```

####Evaluarea adancimii celei mai indepartate frunze din arbore

```haskell
leafdepth :: Tree -> Int
leafdepth Empty = 0
leafdepth (Leaf n) = 1
leafdepth (Node t t') | d == 0 && d' == 0 = 0
                      | otherwise         = 1 + max d d'
                where
                d = leafdepth t
                d' = leafdepth t'
```

####Cea mai indepartata frunza din arbore

```haskell
deepest2 :: Tree -> [Int]
deepest2 Empty = []
deepest2 (Leaf x) = [x]
deepest2 (Node t t') | d > d'    = deepest2 t
                     | d < d'    = deepest2 t'
                     | otherwise = deepest2 t ++ deepest2 t'
                where
                d = leafdepth t
                d' = leafdepth t'
```

###Alte surse


####Propoziti

```haskell
data Prop = X
          | F
          | T
          | Not Prop
          | Prop :|: Prop
```

#####Aproximarea expresiei

```haskell
showProp :: Prop -> String
showProp X = "X"
showProp F = "F"
showProp T = "T"
showProp (Not p)   = "(~" ++ showProp p ++ ")"
showProp (p :|: q) = "(" ++ showProp p ++ "|" ++ showProp q ++ ")"
```

#####Evaluarea expresiei

```haskell
eval :: Prop -> Bool -> Bool
eval X v = v
eval F _ = False
eval T _ = True
eval (Not p) v   = not (eval p v)
eval (p :|: q) v = (eval p v) || (eval q v)
```

#####Simplificarea expresiei

```haskell
simplify :: Prop -> Prop
simplify X = X
simplify F = F
simplify T = T
simplify (Not p) = negate (simplify p)
                        where
                                negate T = F
                                negate F = T
                                negate (Not p) = p
                                negate p = Not p
simplify (p :|: q) = disjoin (simplify p) (simplify q)
                        where
                                disjoin T p = T
                                disjoin F p = p
                                disjoin p T = T
                                disjoin p F = p
                                disjoin p q | p == q = p
                                            | otherwise = p :|: q


####Expresii

```haskell
data Expr = Var String
          | Expr :+: Expr
          | Expr :*: Expr
```

#####Este Norm daca expresia este suma

```haskell
isNorm :: Expr -> Bool
isNorm (a:+:b) = isNorm a && isNorm b
isNorm a = isTerm a
```

#####Este Term daca expresia este constanta sau produs

```haskell
isTerm :: Expr -> Bool
isTerm (Var x) = True
isTerm (a :+: b) = False
isTerm (a :*: b) = isTerm a && isTerm b
```

#####Este normala daca expresia are proprietatea de distributivitate

```haskell
norm :: Expr -> Expr
norm (Var v) = Var v
norm (a :+: b) = norm a :+: norm b
norm (a :*: b) = norm a *** norm b
                        where
                                (a :+: b) *** c = (a *** c) :+: (b *** c)
                                a *** (b :+: c) = ( a *** b) :+: (a *** c)
                                a *** b         = a :*: b
```

####Alte expresii

```haskell
data Expr = X
          | Const Int
          | Neg Expr
          | Expr :+: Expr
          | Expr :*: Expr
```

#####Transforma expresia intr-o aproximare matematica

```haskell
showExpr :: Expr -> String
showExpr X = "X"
showExpr (Const n) = show n
showExpr (Neg p) = "(-" ++ showExpr p ++ ")"
showExpr (p :+: q) = "(" ++ showExpr p ++ "+" ++ showExpr q ++ ")"
showExpr (p :*: q) = "(" ++ showExpr p ++ "*" ++ showExpr q ++ ")"
```

#####Evalueaza expresia dupa un X dat

```haskell
evalExpr :: Expr -> Int -> Int
evalExpr X v = v
evalExpr (Const n) _ = n
evalExpr (Neg p) v   = - (evalExpr p v)
evalExpr (p :+: q) v = (evalExpr p v) + (evalExpr q v)
evalExpr (p :*: q) v = (evalExpr p v) * (evalExpr q v)
```

#####Transforma expresia in Scriere Poloneza Inversa

```haskell
rpn :: Expr -> [String]
rpn X = ["X"]
rpn (Const n) = [show n]
rpn (Neg p) = rpn p ++ ["-"]
rpn (p :+: q) = rpn p ++ rpn q ++ ["+"]
rpn (p :*: q) = rpn p ++ rpn q ++ ["*"]
```
#####Evalueaza o expresie in Scriere Poloneza Inversa

```haskell
evalrpn :: [String] -> Int -> Int
evalrpn s n = the (foldl step [] s)
                where
                        step (x:y:ys) "+" = (y + x):ys
                        step (x:y:ys) "*" = (y * x):ys
                        step (x:ys)   "-" = (-x):ys
                        step ys "X"       = n:ys
                        step ys m | all (\c -> isDigit c || c == '-') m = (read m :: Int):ys
                                  | otherwise = error "ill-formed RPN"

                        the :: [a] -> a
                        the [x] = x
                        the xs  = error "ill-formed RPN"
```

####Vectori

```haskell
data Term = Vec Scalar Scalar
          | Add Term Term
          | Mul Scalar Term
```

#####Evaluarea expresiei

```haskell
eva :: Term -> Vector
eva (Vec x y) = (x,y)
eva (Add t u) = add (eva t) (eva u)
eva (Mul x t) = mul x (eva t)
```

#####Printare expresia ca pereche vector

```haskell
sho :: Term -> String
sho (Vec x y) = show (x,y)
sho (Add t u) = "(" ++ sho t ++ "+" ++ sho u ++ ")"
sho (Mul x t) = "(" ++ show x ++ "*" ++ sho t ++ ")"
```

####Puncte

```haskell
type Point = (Int,Int)
data Points = Rectangle Point Point
             | Union Points Points
             | Difference Points Points
```

#####Verificare daca un punct este intre 2 puncte

```haskell
inPoints :: Point -> Points -> Bool
inPoints (x,y) (Rectangle (left,top) (right,bottom)) = left <= x && x <= right && top <= y && y <= bottom
inPoints p (Union ps qs) = inPoints p ps || inPoints p qs
inPoints p (Difference ps qs) = inPoints p ps && not (inPoints p qs)
```

#####Desenare puncte

```haskell
showPoints :: Point -> Points -> [String]
showPoints (a,b) ps = [ makeline y | y <- [0..b] ]
                                where
                                        makeline y = [ if inPoints (x,y) ps then ’*’ else ’ ’ | x <- [0..a] ]
```

---

#Monads

```haskell
class Monad m where
        return :: a -> m a
        (>>=) :: m a -> (a -> m b) -> m b
```

unde:

- `m` este un constructor de tipuri
 `m a` — tipul computatiilor care produc rezultate de tip a
- tipul `a -> m b` este tipul continuarilor
Continuare: O functie care foloses,te un rezultat de tip `a` pentru a produce o computatie de tip `b`
- `(>>=)` este operatia de „secventiere” a computatiilor
- `return` este continuarea triviala
Pentru un `v` dat, produce computatia care va avea ca rezultat acel `v`.

Deci un monad in cod arata cam asa:

```haskell
instance Monad Parser where
     return x = Parser (\s -> [(x,s)])
     m >>= k  = Parser (\s -> [(y,u)|
                                 (x, t) <− apply m s,
                                 (y, u) <− apply (k x) t ])
```

##Monadul maybe

```
instance Monad Maybe where
    Just x  >>= k = k x
    Nothing >>= k = Nothing
    return x      = Just x
```

##MyIO

```haskell
-- How the IO monad works

module MyIO(MyIO, myPutChar, myGetChar, convert) where

type Input = String
type Remainder = String
type Output = String

data MyIO a  =  MyIO (Input -> (a, Remainder, Output))

apply :: MyIO a -> Input -> (a, Remainder, Output)
apply (MyIO f) inp  =  f inp

myPutChar :: Char -> MyIO ()
myPutChar ch  =  MyIO (\inp -> ((), inp, [ch]))

myGetChar :: MyIO Char
myGetChar =  MyIO (\(ch:rem) -> (ch, rem, []))

instance Monad MyIO where
return x  =  MyIO (\inp -> (x, inp, ""))
m >>= k   =  MyIO (\inp ->
                    let (x, rem1, out1) = apply m inp in
                    let (y, rem2, out2) = apply (k x) rem1 in
                    (y, rem2, out1++out2))

convert :: MyIO () -> IO ()
convert m  =  interact (\inp ->
                let (x, rem, out) = apply m inp in
                out)

```

##Parser

```haskell
module Parser(Parser,apply,parse,char,spot,
  token,star,plus,parseInt) where

import Data.Char
import Control.Monad

-- The type of parsers
newtype Parser a = Parser (String -> [(a, String)])

-- Apply a parser
apply :: Parser a -> String -> [(a, String)]
apply (Parser f) s = f s

-- Return parsed value, assuming at least one successful parse
parse :: Parser a -> String -> a
parse m s  =  one [ x | (x,t) <- apply m s, t == "" ]
                where
                one []                  =  error "no parse"
                one [x]                 =  x
                one xs | length xs > 1  =  error "ambiguous parse"

-- Parsers form a monad

--   class Monad m where
--     return :: a -> m a
--     (>>=) :: m a -> (a -> m b) -> m b

instance Monad Parser where
  return x  =  Parser (\s -> [(x,s)])
  m >>= k   =  Parser (\s ->
                 [ (y, u) |
                   (x, t) <- apply m s,
                   (y, u) <- apply (k x) t ])

-- Parsers form a monad with sums

--   class MonadPlus m where
--     mzero :: m a
--     mplus :: m a -> m a -> m a

instance MonadPlus Parser where
  mzero      =  Parser (\s -> [])
  mplus m n  =  Parser (\s -> apply m s ++ apply n s)

-- Parse one character
char :: Parser Char
char =  Parser f
  where
  f []     =  []
  f (c:s)  =  [(c,s)]

-- guard :: MonadPlus m => Bool -> m ()
-- guard False  =  mzero
-- guard True   =  return ()

-- Parse a character satisfying a predicate (e.g., isDigit)
spot :: (Char -> Bool) -> Parser Char
spot p  =  do { c <- char; guard (p c); return c }

-- Match a given character
token :: Char -> Parser Char
token c  =  spot (== c)

-- Perform a list of commands, returning a list of values
-- sequence :: Monad m => [m a] -> m [a]
-- sequence []
-- sequence (m:ms)  =  do {
--                       x <- m;
--                       xs <- sequence ms;
--                       return (x:xs)
--                     }

-- match a given string (defined two ways)
match :: String -> Parser String
match []      =  return []
match (x:xs)  =  do {
                   y <- token x;
                   ys <- match xs;
                   return (y:ys)
                 }

match' :: String -> Parser String
match' xs  =  sequence (map token xs)

-- match zero or more occurrences
star :: Parser a -> Parser [a]
star p  =  plus p `mplus` return []

-- match one or more occurrences
plus :: Parser a -> Parser [a]
plus p  =  do x <- p
              xs <- star p
              return (x:xs)

-- match a natural number
parseNat :: Parser Int
parseNat =  do s <- plus (spot isDigit)
               return (read s)

-- match a negative number
parseNeg :: Parser Int
parseNeg =  do token '-'
               n <- parseNat
               return (-n)

-- match an integer
parseInt :: Parser Int
parseInt =  parseNat `mplus` parseNeg

```

###Parser folosit in evaluare de expresii

```haskell
module Exp where

import Control.Monad
import Parser

data Exp = Lit Int
         | Exp :+: Exp
         | Exp :*: Exp
         deriving (Eq,Show)

evalExp :: Exp -> Int
evalExp (Lit n)    =  n
evalExp (e :+: f)  =  evalExp e + evalExp f
evalExp (e :*: f)  =  evalExp e * evalExp f

parseExp :: Parser Exp
parseExp  =  parseLit `mplus` parseAdd `mplus` parseMul
  where
  parseLit = do { n <- parseInt;
                  return (Lit n) }
  parseAdd = do { token '(';
                  d <- parseExp;
                  token '+';
                  e <- parseExp;
                  token ')';
                  return (d :+: e) }
  parseMul = do { token '(';
                  d <- parseExp;
                  token '*';
                  e <- parseExp;
                  token ')';
                  return (d :*: e) }

test  :: Bool
test  =
  parse parseExp "(1+(2*3))" == (Lit 1 :+: (Lit 2 :*: Lit 3)) &&
  parse parseExp "((1+2)*3)" == ((Lit 1 :+: Lit 2) :*: Lit 3)
```











LAB1

import Data.List

myInt = 5555555555555555555555555555555555555555555555555555555555555555555555555555555555555

double :: Integer -> Integer
double x = x+x

triple :: Integer -> Integer
triple x = x+x+x


maxim :: Integer -> Integer -> Integer
maxim x y =
    if (x > y)
        then x
        else y

maxim3 :: Integer -> Integer -> Integer -> Integer
maxim3 x y z =
    if (x > y)
        then
            if (x > z)
                then x
                else z
        else
            if (y > z)
                then y
                else z

max3 :: Integer -> Integer -> Integer -> Integer
max3 x y z =
    let
        u = maxim x y
    in
        maxim  u z

maxim4 :: Integer -> Integer -> Integer -> Integer -> Integer
maxim4 x y z w =
    let
        u = maxim x y
    in
        let
            v = maxim z w
        in
            maxim u v

testmaxim4 :: Integer -> Integer -> Integer -> Integer -> Bool
testmaxim4 x y z w =
    let
        r = maxim4 x y z w
    in
        if (r >= x && r >= y && r >= z && r >=w)
            then True
            else False


LAB2


-- la nevoie decomentati liniile urmatoare:

import Data.Char
import Data.List


---------------------------------------------
-------RECURSIE: FIBONACCI-------------------
---------------------------------------------

fibonacciCazuri :: Integer -> Integer
fibonacciCazuri n
  | n < 2     = n
  | otherwise = fibonacciCazuri (n - 1) + fibonacciCazuri (n - 2)

fibonacciEcuational :: Integer -> Integer
fibonacciEcuational 0 = 0
fibonacciEcuational 1 = 1
fibonacciEcuational n =
    fibonacciEcuational (n - 1) + fibonacciEcuational (n - 2)

fibonacciLiniar :: Integer -> Integer
fibonacciLiniar 0 = 0
fibonacciLiniar n = snd (fibonacciPereche n)
  where
    fibonacciPereche :: Integer -> (Integer, Integer)
    fibonacciPereche 1 = (0, 1)
    fibonacciPereche n =
        let
            pereche = fibonacciPereche(n - 1)
        in
            (snd(pereche), fst(pereche) + snd(pereche))



---------------------------------------------
----------RECURSIE PE LISTE -----------------
---------------------------------------------
semiPareRecDestr :: [Int] -> [Int]
semiPareRecDestr l
  | null l    = l
  | even h    = h `div` 2 : t'
  | otherwise = t'
  where
    h = head l
    t = tail l
    t' = semiPareRecDestr t

semiPareRecEq :: [Int] -> [Int]
semiPareRecEq [] = []
semiPareRecEq (h:t)
  | even h    = h `div` 2 : t'
  | otherwise = t'
  where t' = semiPareRecEq t

---------------------------------------------
----------DESCRIERI DE LISTE ----------------
---------------------------------------------
semiPareComp :: [Int] -> [Int]
semiPareComp l = [ x `div` 2 | x <- l, even x ]


-- L2.2
inIntervalRec :: Int -> Int -> [Int] -> [Int]
inIntervalRec lo hi [] = []
inIntervalRec lo hi (x:xs)
    | lo <= x && x <= hi = x : xs'
    | otherwise = xs'
    where xs' = inIntervalRec lo hi xs

inIntervalComp :: Int -> Int -> [Int] -> [Int]
inIntervalComp lo hi xs = [ x | x <- xs, lo <= x && x <= hi ]

-- L2.3

pozitiveRec :: [Int] -> Int
pozitiveRec [] = 0
pozitiveRec (h:t) =
    if (h > 0) then 1 + pozitiveRec t
    else pozitiveRec t


pozitiveComp :: [Int] -> Int
pozitiveComp l = sum [ 1 | x <- l, x > 0]

-- L2.4
pozitiiImpareRec :: [Int] -> Int -> [Int]
pozitiiImpareRec [] _ = []
pozitiiImpareRec (h:t) poz
    | odd h = poz : pozitiiImpareRec t (poz + 1)
    | otherwise = pozitiiImpareRec t (poz + 1)

pozitiiImpareComp :: [Int] -> [Int]
pozitiiImpareComp l = [i | (x, i) <- zip l [0..], odd x]


-- L2.5

multDigitsRec :: String -> Int
multDigitsRec [] = 1
multDigitsRec (h:t) =
    if (isDigit h) then digitToInt h * multDigitsRec t
    else multDigitsRec t

multDigitsComp :: String -> Int
multDigitsComp sir = product [digitToInt x | x <- sir, isDigit x]

-- L2.6

discountRec :: [Float] -> [Float]
discountRec [] = []
discountRec (h:t)
    | h - h * 0.25 < 200 = h - h * 0.25 : discountRec t
    | otherwise = discountRec t

discountComp :: [Float] -> [Float]
discountComp list = [h - h * 0.25 | h <- list, h - h * 0.25 < 200]


LAB3

import   Data.List

-- L3.1 Încercati sa gasiti valoarea expresiilor de mai jos si
-- verificati raspunsul gasit de voi în interpretor:
{-
[x^2 | x <- [1 .. 10], x `rem` 3 == 2]
[(x, y) | x <- [1 .. 5], y <- [x .. (x+2)]]
[(x, y) | x <- [1 .. 3], let k = x^2, y <- [1 .. k]]
[x | x <- "Facultatea de Matematica si Informatica", elem x ['A' .. 'Z']]
[[x .. y] | x <- [1 .. 5], y <- [1 .. 5], x < y ]

-}

factori :: Int -> [Int]
factori n = [x | x <- [1 .. n], n `rem` x == 0]

prim :: Int -> Bool
prim x =
    let
        u = factori x
    in
        if (length u == 2) then True
        else False

numerePrime :: Int -> [Int]
numerePrime x = [nr | nr <- [2..x], prim nr]

-- L3.2 Testati si sesizati diferenta:
-- [(x,y) | x <- [1..5], y <- [1..3]]
-- zip [1..5] [1..3]

myzip3 :: [Int] -> [Int] -> [Int] -> [(Int, Int, Int)]
myzip3 l1 l2 l3 = [(a, b, c) | (a, (b, c)) <- zip l1 (zip l2 l3)]


--------------------------------------------------------
----------FUNCTII DE NIVEL INALT -----------------------
--------------------------------------------------------
aplica2 :: (a -> a) -> a -> a
--aplica2 f x = f (f x)
--aplica2 f = f.f
--aplica2 f = \x -> f (f x)
aplica2  = \f x -> f (f x)

-- L3.3
{-

map (\ x -> 2 * x) [1 .. 10]
map (1 `elem` ) [[2, 3], [1, 2]]
map ( `elem` [2, 3] ) [1, 3, 4, 5]

-}

-- firstEl [ ('a', 3), ('b', 2), ('c', 1)]
firstEl l = map (\(a, b) -> a) l
-- firstEl l = map fst l

-- sumList [[1, 3],[2, 4, 5], [], [1, 3, 5, 6]]
sumList l = map (\x -> sum x) l
-- sumList l = map sum l

-- prel2 [2,4,5,6]
prel2 l = map (\x -> if (odd x) then 2 * x else x `div` 2) l

-- filter p xs = [ x | x <- xs , p x ]

filter1 :: Char -> [String] -> [String]
filter1 c l = filter (\x -> elem c x) l

filter2 :: [Int] -> [Int]
filter2 l = map (^2) (filter odd l)

filter3 :: [Int] -> [Int]
filter3 l = map (^2) [b | (a, b) <- zip [1..] l , odd a]

numaiVocale :: [String] -> [String]
numaiVocale l = map (filter (`elem` "aeiouAEIOU")) l

mymap f list = [f x | x <- list]
myfilter f list = [x | x<- list, f x]



LAB4


import Numeric.Natural

numerePrimeCiur :: Int -> [Int]
numerePrimeCiur n = numerePrimeCiurAux[2..n]

numerePrimeCiurAux [] = []
numerePrimeCiurAux (x : xs) = x : numerePrimeCiurAux(filter (\y -> mod y x /= 0) xs)

ordonataNat :: [Int] -> Bool
ordonataNat [] = True
ordonataNat [x] = True
ordonataNat (x:y:xs) = and [a <= b | (a, b) <- zip (x:xs) xs]


ordonataNat1 :: [Int] -> Bool
ordonataNat1 [] = True
ordonataNat1 [x] = True
ordonataNat1 (x:y:xs)
    | x <= y = and([True] ++ [ordonataNat1 (y:xs)])
    | otherwise = False
--ordonataNat1 (x:y:xs) = x <= y && ordonataNat1(y:xs)

ordonata :: [a] -> (a -> a -> Bool) -> Bool
ordonata [] _ = True
ordonata [x] _ = True
ordonata (x:y:xs) f = and [x `f` y, ordonata (y:xs) f]

(*<*) :: (Integer,Integer) -> (Integer,Integer) -> Bool
(a, b) *<* (c, d) = mod a 10 == 0 && mod c 10 == 0


compuneList :: (b -> c) -> [(a -> b)] -> [(a -> c)]
compuneList f gs = [f . g | g <- gs]

aplicaList :: a -> [(a -> b)] ->[b]
aplicaList x fs = [f x | f <- fs]

myzip3 :: [a] -> [b] -> [c] -> [(a,b,c)]
myzip3 x y z = map (\(a,(b,c)) -> (a,b,c)) (zip x (zip y z))



produsRec :: [Integer] -> Integer
produsRec [] = 1
produsRec (x:xs) = x * produsRec xs


produsFold :: [Integer] -> Integer
produsFold l = foldr (*) 1 l


andRec :: [Bool] -> Bool
andRec [] = True
andRec (x:xs) = x && andRec xs

andFold :: [Bool] -> Bool
andFold l = foldr (&&) True l

concatRec :: [[a]] -> [a]
concatRec [] = []
concatRec (x:xs) = x ++ concatRec xs


concatFold :: [[a]] -> [a]
concatFold l = foldr (++) [] l

rmChar :: Char -> String -> String
rmChar c str = filter (\cc -> cc /= c) str




rmCharsRec :: String -> String -> String
rmCharsRec [] str = str
rmCharsRec (x:xs) str = rmCharsRec xs (rmChar x str)

test_rmchars :: Bool
test_rmchars = rmCharsRec ['a'..'l'] "fotbal" == "ot"



rmCharsFold :: String -> String -> String
rmCharsFold str1 str2 = foldr rmChar str2 str1



logistic :: Num a => a -> a -> Natural -> a
logistic rate start = f
  where
    f 0 = start
    f n = rate * f (n - 1) * (1 - f (n - 1))




logistic0 :: Fractional a => Natural -> a
logistic0 = logistic 3.741 0.00079
ex1 :: Natural
ex1 = 500


ex20 :: Fractional a => [a]
ex20 = [1, logistic0 ex1, 3]

ex21 :: Fractional a => a
ex21 = head ex20

ex22 :: Fractional a => a
ex22 = ex20 !! 2

ex23 :: Fractional a => [a]
ex23 = drop 2 ex20

ex24 :: Fractional a => [a]
ex24 = tail ex20


ex31 :: Natural -> Bool
ex31 x = x < 7 || logistic0 (ex1 + x) > 2

ex32 :: Natural -> Bool
ex32 x = logistic0 (ex1 + x) > 2 || x < 7
ex33 :: Bool
ex33 = ex31 5

ex34 :: Bool
ex34 = ex31 7

ex35 :: Bool
ex35 = ex32 5

ex36 :: Bool
ex36 = ex32 7
findFirst :: (a -> Bool) -> [a] -> Maybe a
findFirst p [] = Nothing
findFirst p (x:xs) = if (p x) then Just x else (findFirst p xs)
findFirstNat :: (Natural -> Bool) -> Natural
findFirstNat p = n
  where Just n = findFirst p [0..]



ex4b :: Natural
ex4b = findFirstNat (\n -> n * n >= 12347)
inversa :: Ord a => (Natural -> a) -> (a -> Natural)
inversa = undefined


LAB5

-- http://www.inf.ed.ac.uk/teaching/courses/inf1/fp/



import Data.Char
import Data.List


-- 1.
rotate :: Int -> [Char] -> [Char]
rotate 0 list = list
rotate n (x:xs) = rotate (n-1) (xs ++ [x])

-- 2.
prop_rotate :: Int -> String -> Bool
prop_rotate k str = rotate (l - m) (rotate m str) == str
                        where l = length str
                              m = if l == 0 then 0 else k `mod` l

-- 3.
makeKey :: Int -> [(Char, Char)]
makeKey k = zip ['A'..'Z'] (rotate k ['A'..'Z'])

-- 4.
lookUp :: Char -> [(Char, Char)] -> Char
lookUp c [] = c
lookUp c ((key, value):lista) = if (c==key) then value else lookUp c lista

-- 5.
encipher :: Int -> Char -> Char
encipher k ch  = lookUp ch (makeKey k)

-- 6.
normalize :: String -> String
normalize [] = []
normalize (x:xs)
    | isLower x || isUpper x = [toUpper x] ++ normalize xs
    | isDigit x = [x] ++ normalize xs
    | otherwise = normalize xs

-- 7.
encipherStr :: Int -> String -> String
encipherStr k str = [encipher k ch | ch <- normalize str]

-- 8.
reverseKey :: [(Char, Char)] -> [(Char, Char)]
reverseKey list = [(b, a) | (a, b) <- list]

-- 9.
decipher :: Int -> Char -> Char
decipher k ch = lookUp ch (reverseKey (makeKey k))

decipherStr :: Int -> String -> String
decipherStr n str = [decipher n ch | ch <- normalize str]

-- 11.
contains :: String -> String -> Bool
contains [] _ = False
contains (x:xs) small = if isPrefixOf small (x:xs) then True else contains xs small

contains_the_and :: String -> Bool
contains_the_and str = contains str "THE" || contains str "AND"

-- 12.
candidates :: String -> [(Int, String)]
candidates str = [(n, decipherStr n str) | n <- [0..25], contains_the_and (decipherStr n str)]

LAB6

import Data.Char
import Data.List

prelStr strin = map toUpper strin
ioString = do
    strin <- getLine
    putStrLn $ "Intrare\n" ++ strin
    let strout = prelStr strin
    putStrLn $ "Iesire\n" ++ strout


prelNo noin = sqrt noin
ioNumber = do
    noin <- readLn :: IO Double
    putStrLn $ "Intrare\n" ++ (show noin)
    let noout = prelNo noin
    putStrLn $ "Iesire"
    print noout

inoutFile = do
    sin <- readFile "Input.txt"
    putStrLn $ "Intrare\n" ++ sin
    let sout = prelStr sin
    putStrLn $ "Iesire\n" ++ sout
    writeFile "Output.txt" sout


prelStr2 :: String -> String
prelStr2 [] = []
prelStr2 [x] = [toUpper x]
prelStr2 (x1:x2:xs) = [toUpper x1, toLower x2] ++ prelStr2(xs)

ioString2 = do
    strin <- getLine
    putStrLn $ "Intrare\n" ++ strin
    let strout = prelStr2 strin
    putStrLn $ "Iesire\n" ++ strout



citirePersoane 0 (varstaMax, numeMax) = print ("Persoana " ++ numeMax ++ " are varsta: " ++ show(varstaMax))
citirePersoane n (varstaMax, numeMax) = do
    nume <- getLine
    varsta <- readLn :: IO Int
    citirePersoane (n - 1) (if varstaMax < varsta then (varsta, nume) else (varstaMax, numeMax))
persoane = do
    n <- readLn :: IO Int
    citirePersoane n (0, "")


mySplit :: String -> Char -> String -> [String]
mySplit [] _ buf = [buf]
mySplit (x:xs) c buffer = if x == c then buffer:(mySplit xs c "") else mySplit xs c (buffer ++ [x])

auxEx2 :: [(String, Int)] -> (String, Int) -> String
auxEx2 [] (numeMax, varstaMax) = ("Persoana " ++ numeMax ++ " are varsta: " ++ show(varstaMax))
auxEx2 ((nume, varsta):xs) (numeMax, varstaMax) = auxEx2 xs (if varstaMax < varsta then (nume, varsta) else (numeMax, varstaMax))

ex2 = do
    continutFisier <- readFile "ex2.in"
    print continutFisier
    let listaPersoane = init (mySplit continutFisier '\n' "")
    print listaPersoane
    let listaPerechi = map (\x -> mySplit x ',' "") listaPersoane
    print listaPerechi
    let listaPerechiBune = map (\[nume, varsta] -> (nume, read varsta :: Int)) listaPerechi
    print listaPerechiBune
    print(auxEx2 listaPerechiBune ("",0))


LAB7

import Data.List (nub)
import Data.Maybe (fromJust)

data Fruct
    = Mar String Bool
    | Portocala String Int
      deriving(Show)


ionatanFaraVierme = Mar "Ionatan" False
goldenCuVierme = Mar "Golden Delicious" True
portocalaSicilia10 = Portocala "Sanguinello" 10
listaFructe = [Mar "Ionatan" False, Portocala "Sanguinello" 10, Portocala "Valencia" 22, Mar "Golden Delicious" True, Portocala "Sanguinello" 15, Portocala "Moro" 12, Portocala "Tarocco" 3, Portocala "Moro" 12, Portocala "Valencia" 2, Mar "Golden Delicious" False, Mar "Golden" False, Mar "Golden" True]


ePortocalaDeSicilia :: Fruct -> Bool
ePortocalaDeSicilia (Mar _ _) = False
ePortocalaDeSicilia (Portocala tip _) = tip `elem` ["Tarocco", "Moro", "Sanguinello"]

test_ePortocalaDeSicilia1 = ePortocalaDeSicilia (Portocala "Moro" 12) == True
test_ePortocalaDeSicilia2 = ePortocalaDeSicilia (Mar "Ionatan" True) == False

nrFeliiSicilia :: [Fruct] -> Int
nrFeliiSicilia [] = 0
nrFeliiSicilia (Mar _ _ : xs) = nrFeliiSicilia xs
nrFeliiSicilia (Portocala tip nr : xs) = if (tip `elem` ["Tarocco", "Moro", "Sanguinello"]) then nr + nrFeliiSicilia xs else nrFeliiSicilia xs
--nrFeliiSicilia lista = sum [nrFelii | Portocala tip nrFelii <- filter ePortocalaDeSicilia listaFructe]

test_nrFeliiSicilia = nrFeliiSicilia listaFructe == 52

nrMereViermi :: [Fruct] -> Int
nrMereViermi [] = 0
nrMereViermi (Mar _ viermi : xs) = if (viermi) then 1 + nrMereViermi xs else nrMereViermi xs
nrMereViermi (Portocala _ _ : xs) = nrMereViermi xs

test_nrMereViermi = nrMereViermi listaFructe == 2

type NumeA = String
type Rasa = String
data Animal = Pisica NumeA | Caine NumeA Rasa

vorbeste :: Animal -> String
vorbeste (Pisica _ ) = "Meow!"
vorbeste (Caine _ _) = "Woof!"

rasa :: Animal -> Maybe String
rasa (Pisica _ ) = Nothing
rasa (Caine _ rasa) = Just rasa

type Nume = String
data Prop
    = Var Nume
    | F
    | T
    | Not Prop
    | Prop :|: Prop
    | Prop :&: Prop
    deriving (Eq, Read)
infixr 2 :|:
infixr 3 :&:

p1 :: Prop
p1 = (Var "P" :|: Var "Q") :&: (Var "P" :&: Var "Q")

p2 :: Prop
p2 = undefined

p3 :: Prop
p3 = undefined

instance Show Prop where
    show F = "F"
    show T = "T"
    show (Var v) = v
    show (Not p) = "(~" ++ show p ++ ")"
    show(p :|: q) = "(" ++ show p ++ "|" ++ show q ++ ")"
    show(p :&: q) = "(" ++ show p ++ "&" ++ show q ++ ")"

test_ShowProp :: Bool
test_ShowProp = show (Not (Var "P") :&: Var "Q") == "((~P)&Q)"

type Env = [(Nume, Bool)]

impureLookup :: Eq a => a -> [(a,b)] -> b
impureLookup a = fromJust . lookup a

eval :: Prop -> Env -> Bool
eval F _ = False
eval T _ = True
eval (Var v) env = impureLookup v env
eval (Not p) env = not (eval p env)
eval (p :|: q) env = eval p env || eval q env
eval (p :&: q) env = eval p env && eval q env

test_eval = eval  (Var "P" :|: Var "Q") [("P", True), ("Q", False)] == True


variabile :: Prop -> [Nume]
variabile F = []
variabile T = []
variabile (Var v) = [v]
variabile (Not p) = nub (variabile p)
variabile (p :|: q) = nub (variabile p ++ variabile q)
variabile (p :&: q) = nub (variabile p ++ variabile q)

test_variabile = variabile (Not (Var "P") :&: Var "Q") == ["P", "Q"]

envs :: [Nume] -> [Env]
envs [x] = [[(x, False)], [(x, True)]]
envs (x:xs) = [(x, False):lista | lista <- envs xs] ++ [(x, True):lista | lista <- envs xs]

test_envs =
      envs ["P", "Q"]
      ==
      [ [ ("P",False)
        , ("Q",False)
        ]
      , [ ("P",False)
        , ("Q",True)
        ]
      , [ ("P",True)
        , ("Q",False)
        ]
      , [ ("P",True)
        , ("Q",True)
        ]
      ]

satisfiabila :: Prop -> Bool
satisfiabila p = or [eval p env| env <- envs $ variabile p]

test_satisfiabila1 = satisfiabila (Not (Var "P") :&: Var "Q") == True
test_satisfiabila2 = satisfiabila (Not (Var "P") :&: Var "P") == False

valida :: Prop -> Bool
--valida p = and [eval p env| env <- envs $ variabile p]
valida p = satisfiabila (Not p) == False

test_valida1 = valida (Not (Var "P") :&: Var "Q") == False
test_valida2 = valida (Not (Var "P") :|: Var "P") == True

auxHead :: Prop -> String
auxHead p = concat (variabile p) ++ "|" ++  show p

auxBody :: Prop -> [Env] -> IO()
auxBody p [] = print ""
auxBody p (env:envs) = do
    putStrLn $ (map (\(_, b) -> bool2String b) env) ++ "|" ++ [(bool2String (eval p env))]
    auxBody p envs

bool2String :: Bool -> Char
bool2String False  = 'F'
bool2String True  = 'T'

tabelaAdevar :: Prop -> IO ()
tabelaAdevar p = do
    putStrLn (auxHead p)
    putStrLn $ "---------------"
    auxBody p (envs $ variabile p)

echivalenta :: Prop -> Prop -> Bool
echivalenta = undefined

test_echivalenta1 = True == (Var "P" :&: Var "Q") `echivalenta` (Not (Not (Var "P") :|: Not (Var "Q")))
test_echivalenta2 = False == (Var "P") `echivalenta` (Var "Q")
test_echivalenta3 = True == (Var "R" :|: Not (Var "R")) `echivalenta` (Var "Q" :|: Not (Var "Q"))



MODEL




data Linie = L [ Int ]
data Matrice = M [ Linie ]

-- liniiN (M [L[1,2,3], L[4,5], L[2,3,6,8], L[8,5,3]]) 3
-- 	[L[1,2,3], L[8,5,3]]

-- doarPozN (M [L[1,2,3], L[4,5], L[2,3,6,8], L[8,5,3]]) 3
--	True

-- doarPozN (M [L[1,2,-3], L[4,5], L[2,3,6,8], L[8,5,3]]) 3
--	False

-- verifica (M[L[1,2,3], L[4,5], L[2,3,6,8], L[8,5,3]]) 10
--	False

-- verifica (M[L[2,20,3], L[4,21], L[2,3,6,8,6], L[8,5,3,9]]) 25
--	True


-- M[L[1,2,3], L[4,5], L[2,3,6,8], L[8,5,3]]
-- 1 2 3
-- 4 5
-- 2 3 6 8
-- 8 5 3

--ex 1
verifica1 :: Linie -> Int -> Bool
verifica1 (L x) n = if length x == n then True else False

liniiN :: Matrice -> Int -> [Linie]
liniiN (M x) n = if n > 0 then [l | l <- x, verifica1 l n] else error "n mai mic sau egal cu 0"

--ex 2
verifica2 :: Linie -> Bool
verifica2 (L []) = True
verifica2 (L (x : xs)) = if x > 0 then verifica2 (L xs) else False

doarPozN :: Matrice -> Int -> Bool
doarPozN (M []) n = True
doarPozN (M (x : xs)) n = if verifica1 x n then verifica2 x && doarPozN (M xs) n else doarPozN (M xs) n

--ex 3
verifica3 :: Linie -> Int -> Bool
verifica3 (L x) n = if sum x == n then True else False

verifica :: Matrice -> Int -> Bool
verifica (M []) n = True
verifica (M (x : xs)) n = verifica3 x n && verifica (M xs) n

--ex 4
instance Show Matrice where
    show (M []) = ""
    show (M (linie : linii)) = show linie ++ "\n" ++ show(M linii)

instance Show Linie where
    show (L []) = ""
    show (L (x : xs)) = show x ++ " " ++ show (L xs)



-- doarPozN mat n = and [all (> 0) x | L x <- liniiN mat n]
-- verifica (M mat) n = foldr (&&) True [foldr (+) 0 x == n | L x <- mat]

--instance Show Matrice where
--    show (M []) = ""
--    show (M ((L x) : linii)) = concat (map (\temp -> show temp ++ " ") x) ++ "\n" ++ show (M xs)




LAB10


data Expr = Const Int -- integer constant
          | Expr :+: Expr -- addition
          | Expr :*: Expr -- multiplication
           deriving Eq
showData :: Expr -> String
--showData x = show x
showData (Const x ) =show x
showData (e1 :*: e2) = "("++show e1 ++ " * " ++ show e2 ++")"
showData (e1 :+: e2) = "("++show e1 ++ " + " ++ show e2 ++")"

instance Show (Expr  )  where
  show=showData
--testare
evalExp :: Expr -> Int
evalExp (Const x) = x
evalExp ( ( e1) :+: ( e2) )= (evalExp e1) + (evalExp e2)
evalExp (( e1) :*: ( e2))=(evalExp e1) * (evalExp e2)

exp1 = ((Const 2 :*: Const 3) :+: (Const 0 :*: Const 5))
exp2 = (Const 2 :*: (Const 3 :+: Const 4))
exp3 = (Const 4 :+: (Const 3 :*: Const 3))
exp4 = (((Const 1 :*: Const 2) :*: (Const 3 :+: Const 1)) :*: Const 2)
test11 = evalExp exp1 == 6
test12 = evalExp exp2 == 14
test13 = evalExp exp3 == 13
test14 = evalExp exp4 == 16


data Operation = Add | Mult deriving (Eq, Show)
data Tree = Lf Int -- leaf
          | Node Operation Tree Tree -- branch
           deriving (Eq, Show)

--E2
evalArb :: Tree -> Int
evalArb (Lf x) = x
evalArb (Node Add tree1 tree2) = evalArb (tree1) + evalArb (tree2)
evalArb (Node Mult tree1 tree2) = evalArb (tree1) * evalArb (tree2)


--E3
expToArb :: Expr -> Tree
expToArb (Const x) = (Lf x)
expToArb (e1 :+: e2) = Node Add  (expToArb(e1) )  (expToArb(e2) )
expToArb (e1 :*: e2 )= Node Mult ( expToArb(e1) ) (expToArb(e2) )

--testare
arb1 = Node Add (Node Mult (Lf 2) (Lf 3)) (Node Mult (Lf 0)(Lf 5))
arb2 = Node Mult (Lf 2) (Node Add (Lf 3)(Lf 4))
arb3 = Node Add (Lf 4) (Node Mult (Lf 3)(Lf 3))
arb4 = Node Mult (Node Mult (Node Mult (Lf 1) (Lf 2)) (Node Add (Lf 3)(Lf 1))) (Lf 2)
test21 = evalArb arb1 == 6
test22 = evalArb arb2 == 14
test23 = evalArb arb3 == 13
test24 = evalArb arb4 == 16


--E4
class MySmallCheck a where
     smallValues :: [a]
     smallCheck :: ( a -> Bool ) -> Bool
     smallCheck prop = and [ prop x | x <- smallValues ]
instance MySmallCheck Expr where
    smallValues=[exp1, exp2, exp3, exp4]



checkExp :: Expr -> Bool




double :: Int -> Int
double = undefined
triple :: Int -> Int
triple = undefined
penta :: Int -> Int
penta = undefined
test x = (double x + triple x) == (penta x)
myLookUp :: Int -> [(Int,String)]-> Maybe String
myLookUp = undefined
testLookUp :: Int -> [(Int,String)] -> Bool
testLookUp = undefined
-- testLookUpCond :: Int -> [(Int,String)] -> Property
-- testLookUpCond n list = n > 0 && n `div` 5 == 0 ==> testLookUp n list
data ElemIS = I Int | S String
     deriving (Show,Eq)
myLookUpElem :: Int -> [(Int,ElemIS)]-> Maybe ElemIS
myLookUpElem = undefined
testLookUpElem :: Int -> [(Int,ElemIS)] -> Bool
testLookUpElem = undefined

-- categoria A - functii de baza
-- categoria B - functii din biblioteci (fara map, filter, fold)
-- categoria C - map, filter, fold

{- Catcgoria A. Functii de baza
div, mod :: Integral a => a -> a -> a
even, odd :: Integral a => a -> Bool
(+), (*), (-), (/) :: Num a => a -> a -> a
(<), (<=), (>), (>=) :: Ord => a -> a -> Bool
(==), (/=) :: Eq a => a -> a -> Bool
(&&), (||) :: Bool -> Bool -> Bool
not :: Bool -> Bool
max, min :: Ord a => a -> a -> a
isAlpha, isAlphaNum, isLower, isUpper, isDigit :: Char -> Bool
toLower, toUpper :: Char -> Char
digitToInt :: Char -> Int
ord :: Char -> Int
chr :: Int -> Char
Intervale
[first..], [first,second..], [first..last], [first,second..last]
-}

{- Categoria B. Functii din biblioteci
sum, product :: (Num a) => [a] -> a
sum [1.0,2.0,3.0] = 6.0
product [1,2,3,4] = 24

and, or :: [Bool] -> Bool
and [True,False,True] = False
or [True,False,True] = True

maximum, minimum :: (Ord a) => [a] -> a
maximum [3,1,4,2]  =  4
minimum [3,1,4,2]  =  1

reverse :: [a] -> [a]
reverse "goodbye" = "eybdoog"

concat :: [[a]] -> [a]
concat ["go","od","bye"]  =  "goodbye"

(++) :: [a] -> [a] -> [a]
"good" ++ "bye" = "goodbye"

(!!) :: [a] -> Int -> a
[9,7,5] !! 1  =  7

length :: [a] -> Int
length [9,7,5]  =  3

head :: [a] -> a
head "goodbye" = 'g'

tail :: [a] -> [a]
tail "goodbye" = "oodbye"

init :: [a] -> [a]
init "goodbye" = "goodby"

last :: [a] -> a
last "goodbye" = 'e'

takeWhile :: (a->Bool) -> [a] -> [a]
takeWhile isLower "goodBye" = "good"

take :: Int -> [a] -> [a]
take 4 "goodbye" = "good"

dropWhile :: (a->Bool) -> [a] -> [a]
dropWhile isLower "goodBye" = "Bye"

drop :: Int -> [a] -> [a]
drop 4 "goodbye" = "bye"

elem :: (Eq a) => a -> [a] -> Bool
elem 'd' "goodbye" = True

replicate :: Int -> a -> [a]
replicate 5 '*' = "*****"

zip :: [a] -> [b] -> [(a,b)]
zip [1,2,3,4] [1,4,9] = [(1,1),(2,4),(3,9)
-}

{- Categoria C. Map, Filter, Fold
map :: (a -> b) -> [a] -> [b]
map (+3) [1,2] = [4,5]

filter :: (a -> Bool) -> [a] -> [a]
filter even [1,2,3,4] = [2,4]

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr max 0 [1,2,3,4] = 4

(.) :: (b -> c) -> (a -> b) -> a -> c
($) :: (a -> b) -> a -> b
(*2) . (+3) $ 7 = 20

flip :: (a -> b -> c) -> b -> a -> c
flip (-) 2 3 = 1
-}