ULOHY
-------

1. Zavedte Nat (data Nat = Zero | Succ Nat) ako instanciu typovej triedy Enum:
   http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html#t:Enum
   Mozete predpokladat, ze je uz deklarovane ako instancia Ord.
   (netreba implementovat enumFromThen a enumFromThenTo)

2. V type data Ex = Con Float | X | Add Ex Ex | Sub ... | Mul ... | Div ...
   definujte funkciu derivative :: Ex -> Ex, ktora zderivuje zadany vyraz.

3. Definujte funkciu eval :: Expr -> Maybe Float, ktora vyhodnocuje
   symbolicke vyrazy deklarovane
   data Expr = Con Float | Add Expr Expr | Sub ... | Mul ... | Div ...,
   pricom v pripade, ze dojde niekde k pokusu o delenie nulou, eval vrati
   Nothing, v opacnom pripade vrati Just x, kde x bude vysledok vyhodnoteneho
   vyrazu (priklad zo slajdov z cvicenia).

data BT a = E | N a (BT a) (BT a)

4. Ktore z nasledujucich vyrazov su korektne?
a) E :: BT [Int]
b) N 1 (BT 1 E E) (N 2 E E)
c) N (N 0 E E) (N E E E) (N E E E), aky je typ tejto hodnoty?
d) let f = N 0 in f (f E E) (f E E)

5. Napiste funkciu, ktora zo zoznamu vytvori binarny strom tak, ze konstruktory
N sa budu vzdy nachadzat len ako pravi potomkovia. Pr.:
f [1,2,3] ~> N 1 E (N 2 E (N 3 E E))

6. Napiste funkciu, ktora
a) vrati pocet uzlov v strome rovnych danej hodnote (f :: a -> BT a -> Int,
   presnejsie f :: (Eq a) => a -> BT a -> Int)
b) pomocou tfold vrati pocet konstruktorov E v strome
c) pomocou treeiterate vrati nekonecny strom
          1
      2       3
    4   5   6   7
   . . . . . . . .
d) z daneho stromu vytvori zoznam obsahujuci vsetky hodnoty z uzlov (co sa tyka
   poradia, su tri rozumne a jednoduche moznosti: uzol-lavy-pravy,
   lavy-uzol-pravy, lavy-pravy-uzol, kde lavy/pravy predstavuje hodnoty v lavom
   a pravom podstrome pre dany uzol)



 RIESENIA
----------

1.
instance Enum Nat where
  succ = Succ
  pred (Succ x) = x
  -- pred nie je definovane pre Zero
  toEnum n = foldr (const Succ) Zero (repeat n ())
  -- vytvori zoznam s n (); v podstate je jedno, coho; pre kazdy prvok aplikuje
  -- na Zero vyraz (const Succ), ktory odignoruje hodnotu () a aplikuje Succ
  fromEnum Zero = 0
  fromEnum (Succ x) = 1 + fromEnum x
  -- jednoduchy katamorfizmus (ako foldr) na Nat
  enumFrom = iterate Succ
  enumFromTo a b = takeWhile (<=b) (enumFrom a)

2.
derive (Con _)   = Con 0
derive X         = Con 1
derive (Add u v) = Add (derive u) (derive v)
derive (Sub u v) = Sub (derive u) (derive v)
derive (Mul u v) = Add (Mul (derive u) v) (Mul u (derive v))
derive (Div u v) = Div (Sub (Mul (derive u) v) (Mul u (derive v))) (Mul v v)

3.
eval :: Expr -> Maybe Float
eval (Con c) = Just c
eval (Add u v) =
  if eu == Nothing || ev == Nothing then Nothing else Just (x + y) where
    eu = eval u
    ev = eval v
    Just x = eu
    Just y = ev
-- analogicky pre Sub, Mul
eval (Div u v) =
  if eu == Nothing || ev == Nothing || y == 0 then Nothing else Just (x + y)
    where
      eu = eval u
      ev = eval v
      Just x = eu
      Just y = ev

4.
a) ok - prazdny strom moze byt akehokolvek (korektneho) typu
b) nok - miesanie datovych a typovych konstruktorov; BT je typovy konstruktor,
   a preto sa nemoze vyskytnut vo vyraze na mieste datoveho
c) ok - hodnoty v tomto strome su (N 0 E E), E, E a typ, ktory vyhovuje vsetkym,
   je BT Int; a kedze su to hodnoty v strome, tak este pridame BT a dostaneme
   BT (BT Int)
d) ok - datovy konstruktor je mozne chapat aj ako funkciu; vyraz predstavuje
   strom s tromi uzlami (v kazdom je 0) a dvomi vetvami dlzky 1

5. f = foldr (\x t -> N x E t) E

6.
a) f _ E = 0
   f x (N y l r) = (if x == y then 1 else 0) + f x l + f x r
b) f = tfold (\_ l r -> l + r) 1
   alebo aj
   f = tfold (const (+)) 1
c) treeiterate (2*) ((+1) . (2*)) 1
d) tfold (\x l r -> x : l ++ r) []
   alebo aj
   f E = []
   f (N x l r) = x : f l ++ f r