-- Polymorphe Algebraische Datentypen

data Pair t = Pair t t
   deriving (Show, Eq, Ord, Read)

p1 = Pair 2 3 :: Pair Int
p2 = Pair [] [4] -- :: Pair [Int]
p3 = Pair [] []
p4 = Pair True False -- :: Pair Bool

type Paar t = (t,t)

p = (3,4) :: Paar Int
q = ([5],[6]) :: Paar [Int]

-- Test auf Gleichheit

equalPair :: Eq a => Pair a -> Bool
equalPair (Pair x y) = x == y

eqPaar :: Eq a => Paar a -> Bool
eqPaar (x,y) = x == y

-- Listen

data Liste t = Leer | Cons t (Liste t)
   deriving (Show, Eq, Ord, Read)

länge :: Liste t -> Int
länge Leer = 0
länge (Cons a l) = 1 + länge l

-- Binärbäume

data Tree a = Nil | Node a (Tree a) (Tree a)
   deriving (Show, Eq, Ord, Read)

t :: Tree Int
t = Node 12 (Node 34 Nil Nil) (Node 3 (Node 17 Nil Nil) Nil)

{- Konstruiere einen binären Suchbaum, der alle Elemente einer Liste enthält. 
Implementiere die Binärsuche, die Einfügeoperation und die sortierte Ausgabe.
-}

-- Konstruktion eines Suchbaums aus einer linearen Liste
makeTree :: Ord t => [t] -> Tree t
makeTree = foldr insert Nil

-- Die Einfügeoperation (Eingabe: Element und Suchbaum, Duplikate löschen)
insert :: Ord a => a -> Tree a -> Tree a
insert x Nil = Node x Nil Nil
insert x (Node y t1 t2) 
   | x < y  = Node y (insert x t1) t2
   | x == y = Node y t1 t2
   | x > y  = Node y t1 (insert x t2)

-- Die Binärsuche (Eingabe Element und Suchbaum)
search :: Eq a => a -> Tree a -> Bool
search x Nil = False
search x (Node y t1 t2) = x==y || search x t1 || search x t2

-- Die sortierte Liste aller Elemente eines Suchbaums (Eingabe Suchbaum)
inOrder :: Ord t => Tree t -> [t]
inOrder Nil = []
inOrder (Node x t1 t2) = inOrder t1 ++ [x] ++ inOrder t2

-- Sortiere eine Liste durch Erstellen eines Suchbaums
tSort :: Ord t => [t] -> [t]
tSort = inOrder . makeTree