--58. Ackermannfunktion (10 Punkte)
af 0 n=n+1
af m 0=2
af m n=af (m-1) (af m (n-1))

a 0 n= 2*n
a m 0=2
a m n=a (m-1) (a m (n-1))
{-
B1(n)=n+1
B2(n)=n+2
B3(n)=2^(2+n) -2
-}

--60. Wörterbuchoperationen Implementierung durch algebraischen Datentyp
data Wbuch a b =
   Einf (Wbuch a b) a b |
   Leer
   deriving Show

exa= Einf (Einf (Einf (Einf (Leer)  6 "Asaf") 5 "Kai") 3 "Chris") 1 "Jakob"
exb= Einf (Einf (Einf (Einf (Leer)  12 "Sebastian") 9 "VMax") 8 "Ani") 4 "Mi"

janzahl:: Wbuch a b -> Int
janzahl Leer=0
janzahl (Einf n a b)= 1+ (janzahl n)

--61. Datenstruktur
jdele Leer _= Leer
jdele (Einf n a b) x
    | x==a =jdele n x
    | otherwise =Einf (jdele n x) a b

--62. Vereinigung von Wörterbüchern
jmerge Leer Leer= Leer
jmerge Leer y = y
jmerge x Leer = x
jmerge (Einf n a b) (Einf m c d)
    |a<=c =Einf (jmerge n (Einf m c d)) a b
    |otherwise = Einf (jmerge (Einf n a b) m) c d
--63. Bäume

data (Ord a) => Suchbaum a b =
    Knoten a b (Suchbaum a b) (Suchbaum a b)
    | Nil
    deriving Show
exc = Knoten 8 "Chris" (Knoten 5 "Jakob" (Knoten 4 "Mia" (Nil) (Nil)) (Knoten 6 "Ilse" (Nil) (Nil)) ) (Knoten 9 "Kai" (Nil) (Nil))

--jdeepTree::
jdeepTree t=maximum (jdeepTree' t 0)
            where
            jdeepTree' Nil _ = [-1]
            jdeepTree' (Knoten a b x y) i= [i]++jdeepTree' x (i+1) ++ jdeepTree' y (i+1)

-- 64. Bäume
data BBaum a = BLeer | BKnoten a (BBaum a) (BBaum a)
    deriving Show
exd= BKnoten 7 (BKnoten 2 (BKnoten 9 (BLeer)(BLeer)) (BLeer)) (BKnoten 3 (BLeer) (BLeer))
jconvToDeepTree Nil _= BLeer
jconvToDeepTree (Knoten a b x y) i= BKnoten i (jconvToDeepTree x (i+1)) (jconvToDeepTree y (i+1))

-- Graveyard
jfind:: Eq a => Wbuch a b -> a -> Maybe b
jfind Leer _ = Nothing
jfind (Einf n a b) x
    |x==a =Just b
    |otherwise =jfind n x

jadd Leer a b =Einf Leer a b
jadd (Einf n a b) v c
    |v <= a = Einf (Einf n a b) v c
    |otherwise =Einf (jadd n v c) a b