module Definitions where

data MyNum = Zero | Succ MyNum

instance Eq MyNum where
    Zero == Zero = True
    (Succ a) == (Succ b) = a == b
    _ == _ = False

instance Ord MyNum where
    _ <= Zero = False
    Zero <= _ = True
    (Succ a) <= (Succ b) = a <= b

instance Show MyNum where
    show Zero = show 0
    show (Succ a) = show (1 + read(show a) :: Int)

{-
Functie ce converteste un numar natural intr-un MyNum
-}
std2MyNum x
    | x == 0 = Zero
    | otherwise = (Succ (std2MyNum (x - 1)))


-------------------------------------------------------------------------------------------

{-
Arbore generic, polimorfic
Arbore in care fiecare nod poate avea oricati fii
-}
data Tree a = EmptyTree |
              Node { parent :: Maybe (Tree a),
                     value :: a,
                     children :: [(Tree a)]
                   } deriving Eq

{-
Clasa pentru containere generice pentru care se poate obtine lista valorilor. Observati
cum "container" este de fapt un constructor de tip. El primeste un alt tip
ca parametru "container a" si se obtine astfel un tip concret.
-}

class Listable container where
    toList :: container a -> [a]

{-
Inrolam tipul nostru arbore la clasa Listable. Pentru asta facem o parcurgere
de tipul "root first, children after"
-}

instance Listable Tree where
    toList EmptyTree = []
    toList (Node {value=v, children=cs}) = v : concatMap toList cs


{-
Functie ce intoarce adancimea la care se gaseste un nod
-}
getNodeDepth EmptyTree = error "Empty trees have no depth"
getNodeDepth (Node {parent = Nothing}) = 0
getNodeDepth (Node {parent = Just p}) = 1 + getNodeDepth p


{-
Vizualizarea arborelui ca String
-}
instance (Eq a, Show a) => Show (Tree a) where
    show EmptyTree = ""
    show t = showNode 0 t
        where
            showNode indent n =
                replicate indent '\t' ++
                show (value n) ++ "\n" ++
                concatMap (showNode (indent + 1)) (children n)


{- Pentru a putea valori de tip Tree, ne vom folosi de cateva functii ajutatoare -}

{- Functia node primeste ca prim parametru o valoare, o lista de functii care primesc ca parametru
un posibil parinte si intorc un nod care are drept parinte argumentul dat si un argument care specifica
parintele nodului si intoarce un nod cu valoarea data si cu parintele dat, si cu copii construiti pe
baza functiilor date -}
node :: a -> [Maybe (Tree a) -> Tree a] -> Maybe (Tree a) -> Tree a
node v fs parent =
    let self = Node parent v ([f (Just self) | f <- fs])
    in  self

{- O functie derivata din functia node, pentru noduri radacina, fara parinti -}
root :: a -> [Maybe (Tree a) -> Tree a] -> Tree a
root v fs = node v fs Nothing

{- O functie derivata din functia node, pentru noduri fara copii, de tip frunza -}
leaf :: a -> Maybe (Tree a) -> Tree a
leaf v parent = node v [] parent


-- Folosind functiile de mai sus si proprietatea functiilor Haskell de a fi curry, putem construi
-- arbori foarte simplu, ca mai jos
t =
    root (-2) [
        leaf 1,
        node 3 [
            leaf 3,
            leaf (-5)
        ]]