haskell lecture 4.hs

-- Priklady resene v ramci cviceni c. 4
-- ====================================
-- 
-- 1) Vyhledani maximalni hodnoty ve stromu
--    Implementujte pro tri varianty stromu uvedene na prednasce
--    funkci, ktera vrati nejvyssi hodnotu obsazenou v uzlech stromu.
--    Uvazujte strom s nejobecnejsim moznym typem prvku (tj. ne pouze Int).

data Tree1 a = Leaf1 a
            | Branch1 (Tree1 a) (Tree1 a)

t1 = Branch1 ( Branch1 (Leaf1 1) (Leaf1 2)) (Leaf1 3)

max_dvojice :: Ord a=> a -> a -> a
max_dvojice a b
      | a > b  = a
      | otherwise = b


max1 (Leaf1 a) = a
max1 (Branch1 l p) = max_dvojice (max1 l) (max1 p)
                    



            
data Tree2 a = Leaf2 a
            | Branch2 a (Tree2 a) (Tree2 a)
            
t2 = Branch2 1234 (Leaf2 100) (Branch2 2 (Leaf2 200) (Leaf2 300))

max2 (Leaf2 a) = a
max2 (Branch2 x l p) = max_dvojice x (max_dvojice (max2 l) (max2 p))
                                
            
            
data Tree3 a = Null
            | Branch3 a (Tree3 a) (Tree3 a)


-- 
-- 2) Reprezentace aritmetickeho vyrazu uzivatelskym datovym typem
--    Vytvorte datovy typ Expr popisujici uzly stromu reprezentujiciho vyrazy
--    s operatory scitani, odcitani, nasobeni, deleni, zmeny znamenka 
--    a s celociselnymi konstantami.

data Expr = Num Integer
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          | Var Char
--          deriving Show 
          
          
eval :: Expr -> Integer
eval (Num a) = a 
eval (Add e1 e2) = (eval e1) + (eval e2) 
eval (Sub e1 e2) = (eval e1) - (eval e2) 
eval (Mul e1 e2) = (eval e1) * (eval e2) 
eval (Div e1 e2) = let x = (eval e2)
                   in if x == 0 
                    then error "Deleni nulou voe"
                    else div (eval e1) x

-- 
-- 3) Vyhodnoceni vyrazu ve stromove reprezentaci
--    Vytvorte funkci, ktera vyhodnoti vyraz reprezentovany typem Expr
--    z predchoziho prikladu.
-- 
-- 4) Prevod vyrazu ve stromove reprezentaci na retezec. Uvazujte i 
--    variantu, ktera generuje minimalni nutny pocet zavorek.

pp (Num a) = show a
pp (Var a) = [a]
pp (Add e1 e2) = pp e1 ++ " + " ++ (pp e2)
pp (Sub e1 e2) = pp e1 ++ " - " ++ (pp e2)
-- pp (Mul e1 e2) = pp e1 ++ " * " ++ (pp e2)
-- pp (Div e1 e2) = pp e1 ++ " / " ++ (pp e2)

pp (Mul e1 e2) = pp_inferior e1 ++ " * " ++ (pp_inferior e2)  
pp (Div e1 e2) = pp_inferior e1 ++ " / " ++ (pp_inferior e2)
  
pp_inferior (Add e1 e2) = "("++ (pp (Add e1 e2)) ++")"  
pp_inferior (Sub e1 e2) = "("++ (pp (Sub e1 e2)) ++")"  
pp_inferior e = pp e  


-- 
-- Priklady vyrazu:
-- 

ex1, ex2, ex3:: Expr
ex1 = Add (Mul (Num 2) (Num 3)) (Num 5)  --  2 * 3 + 5
ex2 = Add (Num 2) (Mul (Num 3) (Num 5))  --  2 + 3 * 5
ex3 = Mul (Add (Num 2) (Num 3)) (Num 5)  --  (2 + 3) * 5
ex4 = Add (Add (Num 2) (Num 3)) (Num 5)  --  2 + 3 + 5
ex5 = Add (Num 2) (Add (Num 3) (Num 5))  --   2 + (3 + 5)
ex6 = Div (Num 5) (Sub (Num 3) (Num 3))  --  5 / (3 - 3) = error




-- 
-- 5) Následující příklad demonstruje jak lze v Haskellu vytvořit typovou
--    třídu.
--  
class Visible a where 
   toString :: a -> String
   size     :: a -> Int

--    Instance typové třídy pro Char by pak mohla vypadat takto.
 

instance Visible Char where
   toString ch = [ch]
   size _      = 1

--    Rozšiřte příklad tak, aby šel vytisknou pomocí funkce print 
--    typ Bool.

instance Visible Bool where
   toString b
      | b == True = "True"
      | b == False = "False"
   size b      = length (toString b)

--    Následující funkce vytiskne na obrazovku reprezentaci prvku v 
--    typové tříde Visible.

print :: Visible a => a->String
print x = "("++ (show (size x))++","++(toString x) ++ ")"


-- 
-- 6) Rozšiřte příklad tak, aby šel vytisknou pomocí funkce print 
--    dříve definovaný typ Expr.

instance Visible Expr where
   toString e = pp e
   size e     = length (pp e)




-- 7) Rozšiřte typovou třídu Visible tak, aby šly tisknout pomocí funkce
--    print i seznamy hodnot, kde typ elementu je již v typové třídě Visible.


-- instance Visible a => Visible [a] where
--    toString (v:[]) = (toString v)
--    toString (v:sv) = (toString v) ++ "," ++ (toString sv)
--    size v     = length (toString v)

instance Visible a => Visible [a] where
   toString (v:sv) = (toString v) ++ "" ++ foldl (\x y-> x++";"++y) "" (map toString sv)
   size v     = length (toString v)




--    Pokud bychom chtěli rozšířit tisk pomocí funkce show i na dvojice
--    složené z "tisknutelných" typů (těch, které již jsou ve třídě Show), 
--    mohlo by to vypadat takto.
--   
--       instance (Show a, Show b)=> Show (a,b) where 
--        show (x,y) = "("++ show x ++ ","++ show y ++ ")" 
-- 
--    Tato definice je již součástí modulu Prelude.
-- 
-- 8) Rozšiřte typovou třídu Show tak, aby umožňovala tisk výrazu typu Expr.
--    jedno z řešení by bylo nechat Haskell, ať způsob tisku odvodí sám. Viz
--    následující příklad.
--    
-- > data Shape = Circle Float 
-- >            | Rectangle Float Float 
-- >              deriving (Eq, Ord, Show)
--                
--    My bychom ale chtěli využít již dříve definované funkce pro tisk 
--    výrazu Expr

instance Show Expr where
      show e = pp e

-- 
-- 9) Doplnte do typu Expr variantu reprezentujici pojmenovanou promennou a
--    implementujte funkci realizujici symbolickou derivaci vyrazu podle
--    zadane promenne.

der (Var x) char
  | x == char = Num 1
  | otherwise = Num 0
  
der (Add e1 e2) char = Add (der e1 char) (der e2 char)
der (Mul (Num n) (Var v)) char = (Mul (Num n) (der (Var v) char))
der (Mul (Var v) (Num n)) char = (Mul (der (Var v) char) (Num n))
der (Mul (Var v) (Var n)) char = (Mul (der (Var v) char) (Var v))
der (Mul (Num _) (Num _)) char = (Num 0)

simplify (Num n) = Num n
simplify (Var n) = Var n
simplify (Mul (Num 0) e) = Num 0
simplify (Mul e (Num 0)) = Num 0
simplify (Add (Num 0) e) = simplify e
simplify (Add e (Num 0)) = simplify e

-- der (Mul e1 e2) char = der_mul (Mul e1 e2)

-- der_mul (Mul e1 e2) char found
--     | snd (der_one e1) = fst (der_one e1) 
--     | snd (der_one e2) = fst (der_one e2) 
--     | otherwise = Num 0 

-- der_one (Num n) char found = ((Num n), found) 

-- der_one (Var v) char found
--     | found = ((Var v), True)
--     | char == v  = ((der (Var v)), found) 

soucet = (Add (Var 'x') (Var 'x'))

  
  

parabola = (Mul (Var 'x') (Var 'x'))





kolecko = (Add (Mul (Var 'x') (Var 'x')) (Mul (Var 'y') (Var 'y')))